Linked list

Linked list

#pragma once

// 명시적으로 dummy nodes를 사용해서 처음과 끝 노드를 설정해준다. 
// 쉽게 생각하는 방법은 current state와 next state에 각 node들이 어떤 상태를 가질지 시각적으로 그려보고
// 이를 생각해서 coding 하기

template <typename T>
class CListNode
{
	// CLinkedList 클래스에서는 이 클래스의 private이나 protected에
	// 접근할 수 있게 한다.
	// template class에 대한 class friend 설정
	template <typename T>
	friend class CLinkedList;

private:
	CListNode()
	{
	}

	~CListNode()
	{
	}

private:
	T	mData;
	CListNode<T>* mNext = nullptr;	// 다음 노드의 주소를 저장하기 위한 변수
	CListNode<T>* mPrev = nullptr;	// 이전 노드의 주소를 저장하기 위한 변수
};

template <typename T>
class CLinkedList
{
public:
	CLinkedList()
	{
		mBegin = new Node;
		mEnd = new Node;

		// Begin과 End를 연결한다.
        // 생성자 부분에서 Begin, End 2개의 노드들만 생성하고 이 둘을 연결
		mBegin->mNext = mEnd;
		mEnd->mPrev = mBegin;

		// Begin과 End는 size에 포함시키지 않는다. 
		mSize = 0;
	}

	~CLinkedList()
	{
		Node* DeleteNode = mBegin;

		while (nullptr != DeleteNode)
		{
			// 먼저 지울 노드의 다음 노드를 저장한다.
			// 그 이유는 아래에서 노드를 제거하면 다음 노드의 메모리 주소를
			// 가져올 수 없기 때문이다.
			Node* NextNode = DeleteNode->mNext;

			delete DeleteNode;

			DeleteNode = NextNode;
		}
	}

private:
	// typedef : 타입을 재정의한다. CListNode<T> 대신에 Node라고만 작성하도
	// CListNode<T> 타입의 변수를 만들어낸다.
	typedef CListNode<T>	Node;

private:
	Node* mBegin;	// 리스트의 처음을 나타내는 노드
	Node* mEnd;		// 리스트의 끝을 나타내는 노드
	int	mSize;		// 실제 추가된 데이터의 수

public:
	void push_back(const T& data)
	{
		Node* NewNode = new Node;

		NewNode->mData = data;

		// End노드와 End의 이전노드 사이에 새로 생성한 노드를 추가한다.
		Node* Prev = mEnd->mPrev;

		Prev->mNext = NewNode;
		NewNode->mPrev = Prev;

		NewNode->mNext = mEnd;
		mEnd->mPrev = NewNode;

		++mSize;
	}

	void push_front(const T& data)
	{
		Node* NewNode = new Node;

		NewNode->mData = data;

		// Begin노드와 Begin의 다음노드 사이에 새로 생성한 노드를 추가한다.
		Node* Next = mBegin->mNext;

		Next->mPrev = NewNode;
		NewNode->mNext = Next;

		NewNode->mPrev = mBegin;
		mBegin->mNext = NewNode;

		++mSize;
	}

	void pop_back()
	{
		if (mSize == 0)
			return;

		// 지울 노드를 얻어온다.
		Node* DeleteNode = mEnd->mPrev;

		// 지울 노드의 이전노드의 다음노드로 End를 지정한다.
		// End의 이전노드로 지울노드의 이전노드를 지정한다.
		Node* Prev = DeleteNode->mPrev;

		Prev->mNext = mEnd;
		mEnd->mPrev = Prev;

		delete DeleteNode;

		--mSize;
	}

	void pop_front()
	{
		if (mSize == 0)
			return;

		// 지울 노드를 얻어온다.
		Node* DeleteNode = mBegin->mNext;

		// 지울 노드의 다음노드의 이전노드로 Begin을 지정한다.
		// Begin의 다음노드로 지울노드의 다음노드를 지정한다.
		Node* Next = DeleteNode->mNext;

		Next->mPrev = mBegin;
		mBegin->mNext = Next;

		delete DeleteNode;

		--mSize;
	}

	// 첫번째 노드의 값을 call-by-value의 parameter에 대입하기
	bool front(T& Data)	const
	{
		if (mSize == 0)
			return false;

		Data = mBegin->mNext->mData;

		return true;
	}

	bool back(T& Data)	const
	{
		if (mSize == 0)
			return false;

		Data = mEnd->mPrev->mData;

		return true;
	}

	int size()	const
	{
		return mSize;
	}

	bool empty()	const
	{
		return mSize == 0;
	}

	void clear()
	{
		Node* DeleteNode = mBegin->mNext;

		while (DeleteNode != mEnd)
		{
			Node* Next = DeleteNode->mNext;

			delete DeleteNode;

			DeleteNode = Next;
		}

		// Begin과 End를 연결하고 Size를 0으로 초기화한다.
		mBegin->mNext = mEnd;
		mEnd->mPrev = mBegin;

		mSize = 0;
	}
};

Iterator

template <typename T>
class CListIterator
{
	template <typename T>
	friend class CLinkedList;

public:
	CListIterator()
	{
	}

	~CListIterator()
	{
	}

private:
	CListNode<T>* mNode = nullptr;

public:
// Operator overloading을 해서 iterator class간에 연산이 가능하게 만들자. 

	bool operator == (const CListIterator<T>& iter)	const
	{
		return mNode == iter.mNode;
	}

	bool operator != (const CListIterator<T>& iter)	const
	{
		return mNode != iter.mNode;
	}

	// 전위연산
	void operator ++ ()
	{
		mNode = mNode->mNext;
	}

	// 후위연산
	void operator ++ (int)
	{
		mNode = mNode->mNext;
	}

	// 전위연산
	void operator -- ()
	{
		mNode = mNode->mPrev;
	}

	// 후위연산
	void operator -- (int)
	{
		mNode = mNode->mPrev;
	}

	// 역참조 재정의
	T& operator * ()
	{
		return mNode->mData;
	}

};

Iterator를 사용해 Linked list에서 관련 함수 구현하기

Iterator는 C++ STL 자료구조마다 존재한다. Iterator는 자료형에 무관하게 loop를 돌 수 있고 포인터 변수를 저장하고 있기 때문에 이를 이용해서 노드의 삽입/삭제, 조회를 간편하게 할 수 있다. Linked list에서 iterator를 만들고 이와 관련된 utility 함수들을 만들어보자.

template <typename T>
class CLinkedList
{

...

public:
	typedef CListIterator<T>	iterator;


public:
	
	// iterator에서 iter.begin()과 iter.end()를 다르게 설정하는 이유 : 반복문에서 더 직관적으로 사용하기 위해
    
	iterator& begin()	const
	{
		static iterator	iter;
		iter.mNode = mBegin->mNext;
		return iter;
	}

	iterator& end()	const
	{
		static iterator	iter;
		iter.mNode = mEnd;
		return iter;
	}

	// 지운 노드의 다음노드를 가지고 있는 iterator를 반환한다.
	iterator erase(const T& Data)
	{
		iterator	iter = begin();
		iterator	iterEnd = end();

		// iterEnd라는 변수를 만들어서 for문이 돌때 end()를 계속 불르는 overhead를 막자!
		for (; iter != iterEnd; ++iter)
		{
			if (*iter == Data)
				break;
		}

		if (iter == iterEnd)
			return iterEnd;

		return erase(iter);
	}

	iterator erase(iterator& iter)
	{
		Node* Prev = iter.mNode->mPrev;
		Node* Next = iter.mNode->mNext;

		Prev->mNext = Next;
		Next->mPrev = Prev;

		delete iter.mNode;

		iter.mNode = Next;

		return iter;
	}
};

추가 #1

반환형이 reference인것과 인자 타입이 reference인 것에 대해서 각각 명확히 알고 있어야 한다. 이를 화살표로 시각화해서 이해해보면 쉬운데

• 1. Call by reference로 인자를 받게 되면 받은 인자 자체를 함수 안에서 수정할 수 있기 때문에 들어오는 화살표 하나가 생성.
• 2. 반환형이 reference + call by reference를 하게 되면 이 함수의 결과를 받게 되는 reference 타입의 인자는 call by referenced 된 인자까지 access가 가능하게 된다. 이를 화살표 2개라 생각하자.

추가 #2

Const 함수의 특징은 다음과 같다.

• Member variable의 값을 바꿀 수 없다.
• Const가 아닌 member function을 호출 할 수 없다.
• Const로 만들어진 함수는 오직 Const type의 instance로만 호출이 가능하다.
• Const 함수를 정의할때 인자 괄호 뒤에다가 const를 붙여주어야 한다.