220407~220411_자료구조_링크드 리스트 구현 (Linked List)

#pragma once

//경고메시지를 띄우기 위한 헤더
#include <assert.h>


/*
자료구조 : 데이터를 관리하는 방법.

* 완벽한 자료구조는 없다. 상황마다 적합하고 효율적인 자료구조가 다르다.
	그것을 적재적소에 활용하는 것이 중요하다.

* 대표적인 자료구조 = 배열, 리스트
일반적으로 이론에서 만드는 자료구조는 실용성이 없다. 특정 자료형만 저장할 수 있기 때문이다.
실전에서 사용하려면 어떤 자료형이던 저장할 수 있게 만드는 것이 중요하다.
-> 직전에 오퍼레이터와 템플릿을 배운 이유.

* 자료구조는 대부분 STL(Standard Template Library)에 저장되어 있어서,
  편하게 가져다 쓸 수 있다.
  물론 그 전에 원리를 알아야 하므로 직접 만들어 볼 예정이다.

* 링크드리스트 : 데이터를 저장하기 위한 노드를 만들고 노드를
서로 연결시켜주어서 다음노드로 이동할 수 있게 만들어주고 데이터가
추가될때마다 노드를 생성하여 연결시켜주는 자료구조이다.

* 싱글 : 한쪽 방향으로만 이동 가능
* 더블 : 양쪽 방향으로 이동 가능 - 우리는 더블링크드리스트만 할 예정(가장 많이 쓰임)
	- 하나의 노드에 저장할 데이터와, 이전 공간의 주소, 그리고 다음 공간의 주소를 저장해 놓는다.

* 링크드리스트의 장점과 단점
	<장점>
	- 노드를 생성해서 연결하면 되기 때문에 개수제한이 없다.
	배열에 비해 상대적으로 중간에 삽입하거나 중간에 삭제하는 속도가
	빠르다.
		-> 길이 1만 짜리의 배열이 있는데 중간 5000번째 데이터를 삭제 또는 추가한다고 생각하면,
		첫 번째 데이터를 삭제하고 4999개 데이터를 하나하나 앞으로 땡겨주어야 한다.
		매우 비효율적이다.
		->반면, 링크드 리스트는 중간에 데이터를 지우면, 앞뒤 노드들의 주소를 연결시켜 주고,
		지우거나 더하면 되기 때문에 더 효율적이다.

	<단점>
	- 매번 할당을 해서 추가를 하기 때문에 new delete비용이
	발생한다.(속도가 썩 좋은 편은 아니다)
	배열같은 경우 공간이 남아있으면 뒷 공간에 추가를 하면 된다.
		->유일하게 링크드리스트가 이기는 경우는 배열이 꽉 찼을 때이다.
		더 큰 배열을 동적할당 해주고, 거기에 복사한 뒤 기존 배열을 삭제해야하는 과정이 필요하기 때문이다.
	- 선형 탐색: 리스트는 무조건 첫번째나 마지막부터 차례로 다음노드로 이동하여 노드를 찾아가야 한다.
	반면, 배열은 인덱스를 통해 바로 접근할 수 있다.(랜덤 액세스 속도가 매우 빠르다)
	물론, 원하는 값을 찾는 것은 둘 다 느리다.
	** 탐색 전문 자료구조 = 이진 트리, 해쉬 



	*** 이처럼 자료구조의 특성을 정확히 알고 있어야 상황에 적합한 자료구조를 빠르게 찾을 수 있다.
	*** 실제로 데이터 관련 자료구조를 하나 잘못선택 했다고 프레임이 크게 떨어지는 상황이 많다.

*/



//클래스 템플릿을 이용할 때에는 헤더에 선언과 정의를 모두 구현해야 한다.
//헤더와 cpp파일로 분리가 불가능하다   -> List.h에 전부 구현해야 한다.


/*
리스트 노드는 리스트의 기능을 구현하고 데이터를 저장하기 위한
용도로 사용이 된다.
리스트의 사용자는 이 노드를 모르더라도 쉽게 사용이 가능해야 한다.
노드는 이 안에서 리스트의 기능을 구현할 목적으로 사용을 할
것이므로 외부에서는 생성자체가 불가능하게 작업한다.(외부에 공개할 필요가 없다.)
*/
//다 틀어막아 버리고 내가 원하는 통로 하나만 열어둘 예정.
template <typename T>
class CListNode
{

/*
class A
{
	// friend로 지정된 클래스는 A클래스의 private에
	// 접근이 가능해진다.
	// --> B는 private로 숨겨져 있는 A의 생성자와 소멸자에 접근이 가능해진다.
	// * 반대로는 불가능. A가 B에는 접근할 수 없다.
	friend class B;
};
class B
{};
*/
	//리스트 관리자 클래스인
	//CList에서 private 항목에 접근할 수 있도록 만들어줌.
	template <typename T>
	friend class CList;
	

	//이터레이터에서도 노드에 접근할 수 있도록 해 주어야 함
	template <typename T>
	friend class CListIterator;
	template <typename T>
	friend class CListReverseIterator;
	

private:
	CListNode() :
		m_Next(nullptr),
		m_Prev(nullptr)
	{
	}

	~CListNode()
	{
	}

private:
	T		m_Data;			//데이터
	CListNode<T>* m_Next;	//다음 노드의 주소
	CListNode<T>* m_Prev;	//이전 노드의 주소
	//* 포인터를 생성했으면? -> 바로 nullptr 초기화
};


//노드를 자유롭게 왔다갔다 할 수 있는 기능. '반복자'
//키보드의 커서 비슷한 기능을 구현하는것이라 생각하면 될 듯 함.
template <typename T>
class CListIterator
{
	//마찬가지로 리스트 관리자에서 자유롭게 접근할 수 있게 해준다.
	template <typename T>
	friend class CList;
	


//외부에서 쓸 기능이므로 생성자를 public으로 작성해 주었다.
public:
	CListIterator() :
		m_Node(nullptr)
	{
	}

	~CListIterator()
	{
	}


private:
	//노드의 주소를 받아올 변수
	CListNode<T>* m_Node;

public:
	//몇몇 오퍼레이터 재정의를 통하여 편의 기능을 만든다.
	//iterator가 같은지 다른지를 비교하는 것은 가지고 있는 노드의 주소가
	//서로 같은 주소인지 다른 주소인지를 판단하는 것이다.
	bool operator == (const CListIterator<T>& iter) const
	{
		//' == '뒤에 온 레퍼런스 주소가 앞의 주소와 같은지,
		return m_Node == iter.m_Node;
	}

	bool operator != (const CListIterator<T>& iter) const
	{
		//' == '뒤에 온 레퍼런스 주소가 앞의 주소와 다른지, 
		return m_Node != iter.m_Node;
	}

	bool operator == (const CListNode<T>* Node)	const
	{
		return m_Node == Node;
	}

	bool operator != (const CListNode<T>* Node)	const
	{
		return m_Node != Node;
	}

	//전위연산
	void operator ++ ()
	{
		m_Node = m_Node->m_Next;
	}
	void operator -- ()
	{
		m_Node = m_Node->m_Prev;
	}


	//후위연산
	void operator ++ (int)
	{
		m_Node = m_Node->m_Next;
	}
	void operator -- (int)
	{
		m_Node = m_Node->m_Prev;
	}

	//역참조: 노드가 가지고 있는 데이터를 반환해준다.
	T& operator * ()
	{
		return m_Node->m_Data;
	}
};

//거꾸로 가는 이터레이터.
template <typename T>
class CListReverseIterator
{
	template <typename T>
	friend class CList;

public:
	CListReverseIterator() :
		m_Node(nullptr)
	{
	}

	~CListReverseIterator()
	{
	}

private:
	CListNode<T>* m_Node;

public:
	bool operator == (const CListReverseIterator<T>& iter) const
	{
		return m_Node == iter.m_Node;
	}
	bool operator != (const CListReverseIterator<T>& iter) const
	{
		return m_Node != iter.m_Node;
	}
	void operator ++ ()
	{
		m_Node = m_Node->m_Prev;
	}
	void operator -- ()
	{
		m_Node = m_Node->m_Next;
	}
	void operator ++ (int)
	{
		m_Node = m_Node->m_Prev;
	}
	void operator -- (int)
	{
		m_Node = m_Node->m_Next;
	}
	T& operator * ()
	{
		return m_Node->m_Data;
	}
};



//리스트 관리자 클래스
template <typename T>
class CList
{
public:
	CList() :
		m_Size(0)
	{
		m_Begin = new NODE;
		m_End = new NODE;

		//생성자에서 시작하자마자 Begin, End 노드 주소를 등록해놓는다.
		m_Begin->m_Next = m_End;
		m_End->m_Prev = m_Begin;
	}

	~CList()
	{
		//소멸자 --> Begin과 End 모두 삭제해야 함.
		PNODE Node = m_Begin;

		//End의 다음 노드는 nullptr이므로 End까지 모두 지워주기 위해서
		//nullptr이 아닐 경우에만 동작시킨다.
		while (Node != nullptr) 
		{
			PNODE Next = Node->m_Next;
			delete Node;
			Node = Next;
		}


	}

private:
	//매번 CListNode<T>를 적으면 너무 번거로우므로 typedef를 이용하여 길이를 줄여준다.
	typedef CListNode<T>	NODE;
	typedef CListNode<T>*	PNODE;

public:
	//위의 iterator 클래스가 너무 기니까 줄여서 쓸 수 있도록 바꾼다.
	typedef CListIterator<T>		iterator;
	typedef CListReverseIterator<T>	reverse_iterator;




private:
	//시작과 끝 노드를 명시적으로 만들어 놓고 그 사이에 노드들을 추가할 수 있도록 만들어 줄 예정.
	PNODE	m_Begin;
	PNODE	m_End;
	int		m_Size;  

//기본적인 리스트 관리 함수 구현 부분
public:
	// 뒤에 추가를 하는 함수이다 . 뒤에 추가이기 때문에
	// End노드와 End노드의 이전노드 사이에 추가를 해준다.
	void push_back(const T& Data)
	{
		// 데이터를 저장하기 위한 노드를 생성한다.
		PNODE	Node = new NODE;

		Node->m_Data = Data;

		// End와 End이전 사이에 새로 생성된 노드를 추가하므로
		// End의 이전 노드를 받아둔다.
		PNODE	Prev = m_End->m_Prev;

		// End이전노드의 다음은 End로 되어있는데 이를 새로
		// 생성한 노드로 변경한다.
		Prev->m_Next = Node;

		// 새로 생성한 노드의 이전노드로 End의 이전노드를
		// 지정해준다.
		Node->m_Prev = Prev;

		// 새로 생성한 노드의 다음노드로 End를 지정한다.
		Node->m_Next = m_End;

		// End의 이전노드로 새로 생성한 노드를 지정한다.
		m_End->m_Prev = Node;

		++m_Size;
	}

	// 앞에 추가하는 기능
	void push_front(const T& Data)
	{

		//새 노드 공간 생성.
		PNODE	Node = new NODE;

		//데이터 저장
		Node->m_Data = Data;

		//시작 노드 다음에 넣을 것이므로 이전 주소는 m_Begin
		Node->m_Prev = m_Begin;

		//새로 만든 노드의 다음 노드 = 기존 시작 노드에 저장돼 있던 m_Next
		Node->m_Next = m_Begin->m_Next;
		
		//m_Begin 뒤에 새로운 노드를 끼워넣었으므로 m_Begin의 다음 주소 = 이 노드의 주소
		m_Begin->m_Next = Node;
		//선생님은 새로운 변수 PNODE에 변수를 저장하고 파일을 옮겼지만 나는 바로 옮겼다.

		//뒷 노드에 저장된 앞 노드의 주소도 끼워넣은 이 노드의 주소로 변경.
		Node->m_Next->m_Prev = Node;

		++m_Size;
		
	}

	//노드가 추가된 적이 없다 -> 비어있다.
	bool empty()	const
	{
		return m_Size == 0;
	}

	//링크드리스트의 사이즈를 확인하는 함수
	int size() const
	{
		return m_Size;
	}
	

	//begin 노드와 end 노드 이외의 모든 노드들을 제거
	void clear()
	{

		PNODE Node = m_Begin->m_Next;

		while (Node != m_End)
		{
			//먼저 지울 노드의 다음 주소를 저장해놓고
			PNODE Next = Node->m_Next;

			//노드를 제거
			delete Node;

			//다음 노드를 Node에 넣어놓으면 다음 루프에서 삭제될 것이다.
			Node = Next;
		}

		//시작노드와 끝 노드를 연결
		m_Begin->m_Next = m_End;
		m_End->m_Prev = m_Begin;

		//사이즈를 0으로 설정
		m_Size = 0;
		
	}



	//가장 처음에 배치되어 있는 노드의 데이터를 반환한다.
	T front() const
	{
		if (empty())
		{
			assert(false);
		}

		//begin의 다음 노드가 가지고 있는 data
		return m_Begin->m_Next->m_Data;
	}

	//가장 마지막에 배치되어 있는 노드의 데이터를 반환한다.
	T back() const
	{
		if (empty())
		{
			assert(false);
		}

		return m_End->m_Prev->m_Data;
	}

	//가장 처음에 배치되어 있는 노드를 제거한다.
	void pop_front()
	{
		if (empty())
		{
			assert(false);
		}

		//삭제할 노드를 먼저 얻어놓는다.
		PNODE DeleteNode = m_Begin->m_Next;

		//삭제할 노드의 다음 노드를 얻어온다.
		PNODE Next = DeleteNode->m_Next;

		//삭제할 노드 다음 노드의 m_Prev값은 m_Begin이 된다.
		Next->m_Prev = m_Begin;
		//m_Begin의 m_Next 값은 위의 Next 변수가 된다.
		m_Begin->m_Next = Next;

		//이제 지울 노드를 삭제한다.
		delete DeleteNode;

		//마지막으로, 사이즈를 하나 줄인다.
		--m_Size;

	}


	//가장 마지막에 배치되어 있는 노드를 제거한다.
	void pop_back()
	{
		if (empty())
		{
			assert(false);
		}

		//삭제할 노드를 먼저 얻어놓는다.
		PNODE DeleteNode = m_End->m_Prev;

		//삭제할 노드의 이전 노드를 얻어온다.
		PNODE Prev = DeleteNode->m_Prev;

		//삭제할 노드 이전 노드의 m_Next값은 m_End가 된다.
		Prev->m_Next = m_End;
		//m_End의 m_Prev 값은 Prev가 된다.
		m_End->m_Prev = Prev;

		//이제 지울 노드를 삭제한다.
		delete DeleteNode;

		//마지막으로, 사이즈를 하나 줄인다.
		--m_Size;

	}

	//Begin의 다음 노드를 iterator의 노드로 주고 반환한다.
	//즉, 처음 추가된 노드가 들어가거나 아무것도 없을 경우라면 End가 들어가서
	//iterator 가 반환되게 된다.
	/*
	쉽게 설명 - 만약 우리가 노드를 집어넣은 적이 있다면 해당 노드가 반환될 것이고
	노드를 집어넣은 적이 없다면 begin을 넣던, end를 넣던 end가 반환된다.
	-> 값을 안 넣었으면 begin()을 쓰던, end()를 쓰던, end가 반환된다.
	*/
	iterator begin() const
	{
		iterator	iter;
		iter.m_Node = m_Begin->m_Next;
		return iter;
	}

	iterator end() const
	{
		iterator	iter;
		iter.m_Node = m_End;
		return iter;
	}

	reverse_iterator rbegin() const
	{
		reverse_iterator	iter;
		iter.m_Node = m_End->m_Prev;
		return iter;
	}

	reverse_iterator rend() const
	{
		reverse_iterator	iter;
		iter.m_Node = m_Begin;
		return iter;
	}


	//삭제 기능을 제작한다. 삭제를 하게 되면 삭제한 노드의 다음 노드를
	//iterator에 넣어서 반환해주도록 한다.
	iterator erase(const T& Data)
	{
		iterator	iter;
		iterator	iterEnd = end();

		for (iter = begin(); iter != iterEnd; ++iter)
		{
			if (*iter == Data)
			{
				return erase(iter);
			}
		}

		return end();
	}

	//오버로딩해서 원하는 함수로 지울 수 있게 해준다.
	iterator erase(const iterator& iter)
	{
		//만약 빈 리스트일 경우 end()를 반환.
		if (empty())
			return end();


		//삭제할 노드의 앞뒤 노드 주소를 저장
		PNODE Prev = iter.m_Node->m_Prev;
		PNODE Next = iter.m_Node->m_Next;

		//앞뒤 노드를 연결
		Prev->m_Next = Next;
		Next->m_Prev = Prev;

		//삭제할 노드 제거
		delete iter.m_Node;
		
		//노드를 삭제하였으므로 사이즈 감소
		--m_Size;

		//위치를 반환해 줄 이터레이터 변수 생성, 위치를 담아서 반환
		iterator result;
		result.m_Node = Next;
		return result;
	}

	//Start와 End 사이를 제거한다. End는 Start보다 더 뒤에 있어야 한다.
	iterator erase(const iterator& Start, const iterator& End)
	{
		iterator start = Start;
		iterator end = End;

		//반복문으로, 제거 시작 지점인 Start부터 리스트 시작 지점인 begin까지 돌려서
		//End와 같은 주소를 만나면 순서가 뒤집어져 있는 것이다.
		//이 경우에 대한 예외 처리를 해 준다.
		for (iterator i = Start; i != m_Begin; --i)
		{
			if (i == end)
			{
				start = End;
				end = Start;
			}
		}

		//예외 처리가 완료되면 노드를 삭제한다.
		PNODE Prev = start.m_Node->m_Prev;
		PNODE Next = end.m_Node->m_Next;
		PNODE Node = start.m_Node;
		while (Node != Next)
		{
			//지우기 전 지울 노드의 다음 주소 받아놓고
			PNODE temp = Node->m_Next;

			//노드 지우고
			delete Node;

			//다음 지울 주소를 저장
			Node = temp;

			//노드 하나가 줄었으므로 사이즈 하나 감소
			m_Size--;
		}


		//노드를 서로 연결해 준다.
		Prev->m_Next = Next;
		Next->m_Prev = Prev;


		//삭제가 완료되면 삭제되 다음 노드를 반복자에 담아서 반환.
		iterator iter;
		iter.m_Node = Next;
		return iter;
	}

	/*
	* 정렬 기능
		- main에서 만든 ListSort 함수의 주소를 인자로 받아오면,
		이 함수 안에서 ListSort 함수를 사용할 수 있다.
		ListSort에 int a, int b 값을 받으면 true or false가 리턴된다
		리턴되는 값에 따라서, 오름차순으로 정렬할지 
		내림차순으로 정렬할 지를 결정한다.
		ListSort가 오름차순을 true로 반환하면 -> 오름차순 정렬
		ListSort가 내림차순을 true로 반환하면 -> 내림차순 정렬

		- 클래스 내부의 Sort 함수에서는 인자가 어떤 자료형으로 들어올 지 
		알 수 없으므로바깥의 함수가 컨트롤할 수 있게 해주는 것이다.

		- 쉽게 생각해서, 만약 T 타입에 클래스가 들어온다면, 
		리스트 클래스 내부에서는 이 클래스들의 대소 관계를 알 방법이 없다.
		
		- 그러므로 함수를 main 함수로 빼서, 만들어질 리스트 클래스들의
		대소 관계 규칙을 정의해서 정렬 함수로 반환해주는 것이다.
		(대소판단을 외부의 함수가 대신해준다고 생각하면 될듯)
	
		cf)노드 자체의 주소를 서로 바꿀 필요 없이
		역참조해서 노드 안의 값만 서로 바꾸면 된다.
		(노드의 m_Data 값만 서로 교환)
		- 나도 처음에 노드의 포인터를 받아서 사용할 경우 m_Data가 바뀌면
		에러가 나지 않을까 생각했지만,
			->노드 자체의 주소는 바깥에서 접근할 수 없데 설계되어 있다.

		- 정렬 방식은 예전에 했던 방식을 사용한다.
		- 여기서도 똑같이 밑을 참고하여 이중 포문 방식으로 구현하면 된다.
		for (int i = 0; i < 9; ++i)
		{
			for (int j = i + 1; j < 10; ++j)
			{
				if (Array[i] > Array[j])
				{
					int	Temp = Array[i];
					Array[i] = Array[j];
					Array[j] = Temp;
				}
			}
		}
	}
	*/
	 
	void Sort(bool (*Func)(const T&, const T&))
	{
		//시작점과 끝점을 받는다.
		iterator iter = begin();
		iterator iterEnd = end();

		//i는 j 하나 전까지 비교
		--iterEnd;

		for (; iter != iterEnd; ++iter)
		{
			iterator iter1 = iter;
			++iter1;


			iterator iter1End = end();
			for (; iter1 != iter1End; ++iter1)
			{
				if (Func(*iter, *iter1))
				{
					T temp = *iter;
					*iter = *iter1;
					*iter1 = temp;
				}
			}

		}

	}

};

/*
* 직접 만들어보기!
1.리스트를 관리하고 개별 노드를 연결해주는 CList 클래스
	1-1. 기본적인 데이터 관리 기능.(앞에 추가, 뒤에 추가, 중간 추가, 중간 삭제 등)
2.실제 데이터와 이전 / 다음 정보가 들어가는 CListNode 클래스
3.리스트 사이를 돌아다니며 위치를 확인할 수 있는 iterator 클래스
3 - 1. iterator 간 연산이 가능한 연산자들(전위연산, 후위연산, 역참조 등)
*/