템플릿 클래스를 이용한 리스트 구현

<main.cpp>

#include <iostream>
#include <stdio.h>
#include "practice.h"

using std::cout;
using std::endl;
using std::cin;

int main()
{
	// 1. 리스트 생성
	CList<int> myList;
	// 2. 노드 추가 ( fornt & back )
	for (int i = 0; i < 5; ++i)
	{
		myList.Push_Back(i + 1);
	} 
	for (int i = 0; i < 5; ++i)
	{
		myList.Push_Front((i + 1) * 100);
	}
	// 3. 리스트 출력 ( begin(), all )
	cout << "리스트 첫번째 노드 " << *(myList.begin()) << endl << endl;
	for (int i = 0; i < myList.size(); ++i)
	{
		cout << "리스트 " << i + 1 << " 번째 노드 값 = " << myList[i] << endl;
	}
	cout << endl;
	// 4. 리스트 reverse
	myList.reverse();
	// 5. 리스트 출력
	for (int i = 0; i < myList.size(); ++i)
	{
		cout << "reverse한 리스트 " << i + 1 << " 번째 노드 값 = " << myList[i] << endl;
	}
	cout << endl;
	// 6. 리스트 삭제
	// 6-1. HeadNode 삭제
	myList.erase(myList.begin());
	// 6-2. TailNode 삭제
	//CList<int>::iterator iter = myList.begin();
	//iter;;
	//iter = myList.end();
	//--iter;
	//myList.erase(iter);
	myList.erase(--myList.end());
	// 6-3. 리스트 삭제

	for (CList<int>::iterator iter = myList.begin(); iter != myList.end(); iter = myList.begin())
	{
		myList.erase(iter);
	}

	myList.Push_Back(111);

	for (int i = 0; i < myList.size(); ++i)
	{
		cout << myList[i] << endl;
	}

	return 0;
}

<practice.h>

#pragma once
#include <assert.h>

template<typename T>  // 하나의 노드에 대한 구조체
struct tListNode
{
	T	data;
	tListNode<T>* pNext;
	tListNode<T>* pPrev;

	tListNode()  // 인자 없이 선언만 했을 경우
		: pNext(nullptr)
		, pPrev(nullptr)
	{

	}

	tListNode(const T& _data, tListNode<T>* _pNext = nullptr, tListNode<T>* _pPrev = nullptr)  // 인자 있이 선언하는 경우
		: data(_data)
		, pNext(_pNext)
		, pPrev(_pPrev)
	{

	}
};

template <typename T>
class CList
{
private:
	tListNode<T>*	pHead;
	tListNode<T>*	pTail;
	int				iCurCount;

public:
	class iterator;  // 클래스 CList 의 내부 함수 iterator 선언
	iterator begin();  // iterator 에 대한 함수 선언
	iterator end();
	iterator erase(const iterator& _iter);

public:
	int		size() { return iCurCount; };
	void	Push_Back(const T& _data);
	void	Push_Front(const T& _data);
	void	reverse();
	void	Reverse(iterator _iter);

public:
	CList()
		: iCurCount(0)
		, pHead(nullptr)
		, pTail(nullptr)
	{

	}

	~CList()
	{
		// 할당된 메로리 해제 코드
		tListNode<T>* pNode = pHead;
		while (nullptr != pNode)
		{
			tListNode<T>* pNext = pNode->pNext;
			delete pNode;
			pNode = pNext;
		}
	}

	T& operator [](int _idx)
	{
		tListNode<T>* NextNode = this->pHead;
		for (int i = 0; i < _idx; ++i)
		{
			NextNode = NextNode->pNext;
		}
		return NextNode->data;
	}

	class iterator  // Q. 위에 선언 하고 구현은 따로 하는 이유는 무엇인가?
	{
	private:  // iterator 는 자신이 어떤 배열(리스트)을 가리키는지 그리고 어떤 요소(노드)를 가리키는 지 이 두 가지가 필요하다. 이 두가지는 수정 되어서는 안된다.
		CList<T>* pList;
		tListNode<T>* pTargetNode;

	public:  // 오퍼레이터 모음 ==, !=, ++(전위, 후위), --(전위, 후위) , *
		bool operator == (const iterator& _otheriter) // 두 개의 iterator에 대해서
		{
			if (pList == _otheriter.pList && pTargetNode == _otheriter.pTargetNode)
			{
				return true;
			}

			return false;
		}

		bool operator != (const iterator& _otheriter)
		{
			/*if (pList != _otheriter.pList || tListNode != _otheriter.pTargetNode)
			{
				return false;
			}
			return true;*/  // 이 코드는 위의 operator == 의 역과 같다.
			return !((*this) == _otheriter);
		}

		iterator& operator ++ ()  // Q. 전위 증산연산자 // 왜 iterator 가 아니고 iterator& 인가
		{
			// end iterator 일 경우
			assert(pTargetNode);

			pTargetNode = pTargetNode->pNext;

			return *this;
		}

		iterator operator ++ (int)  // 후위 증산 연산자 // 왜 int 를 인자로 받고  iterator& 가 아니라 iterator 인가
		{
			iterator copy_iter(*this);

			++(*this);

			return copy_iter; // 실제로 iterator는 증산 했지만 증산 이전의 원래 값을 반환하여 후위 연산자 처럼 보이게 함
		}

		iterator operator --()
		{
			// 주어진 iterator 가 가리키는 노드가 pHead 일 경우
			assert(pTargetNode != pList->pHead);

			// 주어진 iterator 가 가리키는 노드가 pTail 일 경우
			if (nullptr == pTargetNode)
			{
				this->pTargetNode = this->pList->pTail;
			}

			// 주어진 iterator 가 가리키는 노드가 중간 노드인 경우
			else
			{
				this->pTargetNode = this->pTargetNode->pPrev;
			}

			return *this;
		}

		iterator operator --(int)
		{
			iterator  copy_iter(*this);

			--(*this);

			return copy_iter;
		}
		
		T& operator * ()
		{
			assert(pTargetNode);

			return pTargetNode->data;
		}

	public:  // iterator 생성자와 소멸자
		iterator()
			: pList(nullptr)
			, pTargetNode(nullptr)
		{

		}
		iterator(CList<T>* _pList, tListNode<T>* _pTargetNode)
			: pList(_pList)
			, pTargetNode(_pTargetNode)
		{

		}
		~iterator()
		{

		}

		template<typename T>
		friend class CList;
	};
};

template<typename T>
void CList<T>::Push_Back(const T& _data)
{
	tListNode<T>* newNode = new tListNode<T>(_data); // 새로운 노드의 메모리를 동적 할당 한다 // tListNode 의 인자 있이 선언 하는 경우로 new 을 사용하여 동적할당한다.

	if (nullptr == this->pHead)
	{
		pHead = newNode;
		pTail = newNode;
	}
	else
	{
		pTail->pNext = newNode;
		newNode->pPrev = pTail;
		pTail = newNode;
	}

	++(this->iCurCount);
}

template<typename T>
void CList<T>::Push_Front(const T& _data)
{
	tListNode<T>* newNode = new tListNode<T>(_data);

	if (nullptr == pHead)
	{
		pHead = newNode;
		pTail = newNode;
	}
	else
	{
		pHead->pPrev = newNode;
		newNode->pNext = pHead;
		pHead = newNode;
	}
	++(this->iCurCount);
}

template<typename T> // inner class 가 템플릿에서 반환값으로 지정된 경우 앞에 typename키워드(대상이 inner class 타입임을 알려주는 역할)를 적어 주어야 한다.
typename CList<T>::iterator CList<T>::begin()
{
	return iterator(this,pHead);
}

template<typename T>
typename CList<T>::iterator CList<T>::end()
{
	return iterator(this, nullptr); // end() 함수는 마지막 노드인 pTail 의 다음 노드
}

template<typename T>
typename CList<T>::iterator CList<T>::erase(const iterator& _iter)
{
	// 반환할 iterator
	iterator NextIter;

	// 삭제하는 노드가 첫번째 노드인 경우
	if (pHead == _iter.pTargetNode)
	{
		// 해당 노드의 다음 노드를 알아낸다.
		tListNode<T>* pNode = _iter.pTargetNode->pNext;

		// 다음 노드를 첫번째(헤드) 노드로 지정한다.
		pHead = pNode;

		// 데이터가 2개 이상일 경우. ( pHead == pTail 일 경우 (데이터가 한 개일 경우) pHead->pPrev 는 존재 하지 않으므로 )
		if (nullptr != pHead)
		{
			pHead->pPrev = nullptr;
		}
		// 다음 노드가 존재하지 않았다. (데이터가 1개 있는 상태일 경우)
		else
		{
			pTail = nullptr;
		}

		// 새로운 헤드노드가 곧 삭제된 다음 노드이다.
		NextIter.pTargetNode = pHead;
	}

	// 삭제하는 노드가 마지막 노드인 경우
	else if (pTail == _iter.pTargetNode)
	{
		// 해당 노드의 이전 노드를 알아낸다.
		tListNode<T>* pNode = _iter.pTargetNode->pPrev;
		
		// 이전 노드를 마지막 노드로 지정한다.
		pTail = pNode;

		// 노드의 마지막은 다음 노드가 없으므로 마지막 노드의 다음 노드 가리키는 부분을 null 처리한다.
		if (nullptr != pTail)
		{
			pTail->pNext = nullptr;
		}
		else
		{
			pHead = nullptr;
		}

		// 삭제 대상의 다음 노드를 반환해야 하나 삭제 대상이었던 노드는 pTail이었으므로 end iterator 을 반환하기 위해 nextIter의 pTargetNode를 null 처리 한다.
		NextIter.pTargetNode = nullptr;
	}

	// 삭제되는 노드가 중간의 노드인 경우
	else
	{
		// 삭제 대상 노드를 중심으로 앞 뒤 노드를 연결
		_iter.pTargetNode->pPrev->pNext = _iter.pTargetNode->pNext;
		_iter.pTargetNode->pNext->pPrev = _iter.pTargetNode->pPrev;

		// 반환할 iterator를 삭제 대상 노드의 다음 노드를 가리키는 iterator로 대입한다.
		NextIter.pTargetNode = _iter.pTargetNode->pNext;
	}

	// iterator가 가리키는 노드를 삭제한다.
	delete _iter.pTargetNode;

	// 하나의 노드가 삭제 되었으므로 노드의 개수도 하나 줄여야 한다.
	--iCurCount;

	return NextIter;
}

// 재귀함수로 reverse 구현
// 각 노드의 pNext 와 pPrev를 바꾼다.
template<typename T>
void CList<T>::Reverse(iterator _iter)
{
	tListNode<T>* NextNode = _iter.pTargetNode->pNext;
	_iter.pTargetNode->pNext = _iter.pTargetNode->pPrev;
	_iter.pTargetNode->pPrev = NextNode;
	iterator nextIter(this,_iter.pTargetNode->pNext);
	if (nullptr == nextIter.pTargetNode)
	{
		return;
	}
	Reverse(nextIter);
}

template<typename T> 
void CList<T>::reverse()
{
	// 해당 리스트의  pTail 과 pHead를 바꾼다.
	tListNode<T>* newHead = this->pTail;
	this->pTail = this->pHead;
	this->pHead = newHead;

	// this의 Head를 인자로 주어야 한다.
	iterator firstIter(this, pHead);
	Reverse(firstIter);
}