CPP_1. AssortRock 14일차 오프라인 수업_220926

양방향 링크드리스트

• 첫 날에 시험 봤던 게 링크드리스트여서 이제는 좀 친숙하게 느껴진다.
• 이번 구현은 header와 trailer를 사용한 구현

 

namespace ya
{
	template <typename T>
	struct Node
	{
		Node() 
			: mData(NULL)
			, mNext(nullptr)
			, mPrev(nullptr)
		{

		}
		Node(const T data)
			: mData(data)
			, mNext(nullptr)
			, mPrev(nullptr)
		{
			
		}
		~Node()
		{

		}

		T mData;
		Node<T>* mNext;
		Node<T>* mPrev;
	};

	template <typename T>
	class list
	{
	public:


	private:
		size_t mCount;
		Node<T>* mfirst;
		Node<T>* mlast;
	};
}

 

• Node<T>* mfirst와 mlast는 header와 trailer에 해당하는 부분 (아래 링크 참고)

https://dev-treadmill.tistory.com/29?category=1122350 

3장-4. 일반적인 링크드 리스트 구현 (단일, 이중, 환형)

 

 

 

list()
{
	mfirst = new Node<T>();
	mlast = new Node<T>();

	mfirst->mNext = mlast;
	mfirst->mPrev = nullptr;

	mlast->mNext = nullptr;
	mlast->mPrev = mfirst;

	mCount = 0;
}

• 리스트의 생성자
• header와 trailer에 노드를 부여하고 서로 이어주는 부분이다.
• header와 trailer를 사용하면 Node의 끝을 만나는 순간 NULL 체크를 하는 수고를 덜 수 있다.
• 왜냐하면 노드의 첫 시작과 끝은 header와 trailer이기 때문
• (멤버의 범위는 header->next이고 멤버의 끝은 trailer->prev임)

 

iterator begin() const 
{
	return iterator(mfirst->mNext);
}

• begin문, 후술할 iterator를 반환하며 첫 번째 원소인 mfirst->mNext를 반환한다.

 

 

iterator end() const
{
	return iterator(mlast);
}

• 노드의 범위를 잡을 때 끝은 마지막 멤버의 바로 다음 요소여야 하므로, mlast를 반환해준다. 

 

 

void push_back(const T& data)
{
	Node<T>* newNode = new Node<T>(data);
	Node<T>* lastPrev = mlast->mPrev;

	lastPrev->mNext = newNode;
	newNode->mPrev = lastPrev;

	newNode->mNext = mlast;
	mlast->mPrev = newNode;

	mCount++;
}

• 새로운 노드를 만들어서 넣어주는 구간
• 요점부터 설명하자면 trailer->prev에 새로 만든 노드를 넣어주고 연결시키는 작업

 

 

void push_front(const T& data)
{
	//숙제
	Node<T>* newNode = new Node<T>(data);
	Node<T>* firstNext = mfirst->mNext;
                                     // first <-------------> firstNext

	firstNext->mPrev = newNode; //           newNode <-- firstNext
	newNode->mNext = firstNext; //           newNode --> firstNext
	newNode->mPrev = mfirst;    // first <-- newNode
	mfirst->mNext = newNode;    // first --> newNode

	mCount++;
}

• 숙제였던 push_front() 부분
• push_front는 newNode를 header의 앞에 넣어 주는 작업
• push_back과 마찬가지로 넣어주고 연결시키는 작업을 진행하면 됨

 

 

void pop_back()
{
	if (empty())
		return;

	Node<T>* to_delete = mlast->mPrev;

	mlast->mPrev = to_delete->mPrev;
	to_delete->mPrev->mNext = mlast;

	delete to_delete;
	to_delete = nullptr;

	mCount--;
}

• to_delete를 삭제할 노드로 두고(trailer->prev)
• 삭제할 노드 앞 뒤를 서로 연결해준 뒤 삭제해주는 작업

 

 

void pop_front()
{
	if (empty())
		return;

	Node<T>* to_delete = mfirst->mNext;

	mfirst->mNext = to_delete->mNext;
	to_delete->mNext->mPrev = mfirst;

	delete to_delete;
	to_delete = nullptr;

	mCount--;
}

• 이것 또한 어제 쌤이 내주신 숙제
• pop_back를 응용해서 푸니 쉽게 풀렸다

 

 

 

iterator erase(iterator iter)
{
	Node<T>* currNode = iter.getPtr();			
	Node<T>* nextNode = currNode->mNext;

	currNode->mPrev->mNext = nextNode;
	nextNode->mPrev = currNode->mPrev;

	delete currNode;
	currNode = nullptr;
	mCount--;

	return nextNode;
}

• 이것도 쌤이 어제 내주신 숙제
• 지정한 이터레이터가 가리키는 요소를 삭제하고 그 다음 요소를 가리키는 함수

 

 

 

이터레이터 구현

• 이터레이터 패턴을 구현한 클래스
• STL에서 제공하는 이터레이터를 사용하면 요소를 순회하는 코드를 일반화시킬 수 있다.
• ya::list를 지원하는 이터레이터를 만들어 보는 과정

 

class list
{
public:
	class iterator
	{
	public:


	private:
		Node<T>* mPtr;
	};
        
        .
        .
        .

• mPtr은 이터레이터가 가리키는 요소를 나타냄
• 이터레이터는 실질적으로 포인터와 비슷하게 작동하도록 설계됨
• 그래서 저 mPtr에 접근하려면 *iter와 같은 역참조 연산자를 재정의하여 사용함

 

 

iterator& operator++() // 전위
{
	if (mPtr != nullptr
		&& mPtr->mNext != nullptr)
	{
		mPtr = mPtr->mNext;
	}

	return *this;
}

iterator operator++(int) // 후위
{
	iterator temp(*this);
	if (mPtr != nullptr
		&& mPtr->mNext != nullptr)
	{
		mPtr = mPtr->mNext;
	}

	return temp;
}

• 전위/후위 증감 연산자 재정의
• 자신이 가리키는 요소와 증가될 다음 요소가 nullptr인지 체크한 후 넘어간다.

 

 

T& operator*()
{
	if (mPtr != nullptr)
		return mPtr->mData;
}

• 역참조 연산자 재정의
• 가리키는 값에 대해 NULL 체크한 후 mPtr을 반환한다.