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

단일 링크드 리스트 구현

• 일반적인 단일 링크드 리스트는 SLinkedList라고 불린다.
• C++의 템플릿 매커니즘을 통해 string이 아닌 다른 타입들도 받을 수 있도록 한다.
• 따라서 링크드 리스트를 구성하는 노드(SNode)도 템플릿으로 작성된다.

#pragma once

// SLinkedList를 구성하는 노드
template<typename E>
class SNode
{
private:
	E elem;			// 노드가 가진 값
	SNode<E>* next; // 다음 요소를 가리키는 포인터

	friend class SLinkedList<E>;
};

// 일반화된 단일 링크드 리스트
template<typename E>
class SLinkedList
{
public:
	SLinkedList();
	~SLinkedList();

	bool empty() const;			// 리스트가 비었는지 확인
	const E& front() const;		// 맨 앞의 원소를 반환한다.
	
	void addFront(const E& e);	// 리스트의 앞에 요소 추가하기
	void removeFront();			// 리스트의 앞에서 요소 제거하기

private:
	SNode<E>* head;				// 헤드 노드를 가리키는 포인터
};

• SLinkedList.h
• 멤버 변수/함수 선언 부분

 

 

 

 

template<typename E>
inline SLinkedList<E>::SLinkedList()
	: head(nullptr)
{}

template<typename E>
inline SLinkedList<E>::~SLinkedList()
{
	if (!empty())
	{
		while (!empty())
			removeFront();
	}
}

template<typename E>
inline bool SLinkedList<E>::empty() const
{
	return head == nullptr;
}

template<typename E>
inline const E& SLinkedList<E>::front() const
{
	return head->elem;
}

template<typename E>
inline void SLinkedList<E>::addFront(const E& e)
{
	SNode<E>* v = new SNode<E>;
	v->elem = e;
	v->next = head;			// 새로 추가된 노드의 다음 노드를 헤드로 바꾸고
	head = v;				// 헤드를 추가된 노드로 변경

	// 기차의 앞칸 쪽으로 추가되는 방식
}

template<typename E>
inline void SLinkedList<E>::removeFront()
{
	SNode<E>* old = head;
	head = old->next;		// 현재 헤드의 다음 요소를 헤드로 바꿈
	delete old;				// 기존 헤드를 삭제
}

• SLinkedList.h
• 멤버 함수 정의 부분

 

#include "pch.h"
#include "SLinkedList.h"
using namespace std;


int main()
{
	SLinkedList<string> sl;

	sl.addFront("Hello?");
	sl.addFront("Hello1");
	sl.addFront("Hello2");
	sl.addFront("Hello3");
	sl.addFront("Hello4");

	for (int i = 0; i < 5; i++)
	{
		cout << sl.front() << endl;
		sl.removeFront();
	}
    
    
    
}

Hello4
Hello3
Hello2
Hello1
Hello?

 

 

 

 

 

 

 

 

 

---

이중 링크드 리스트

• 단일 링크드 리스트의 경우 후미에서 원소를 지우는게 쉽지 않았다.
• (구현하지 않았지만 구현한다 해도 O(N) 시간이 걸릴 것이다)
• 지우려는 노드의 바로 이전 노드로 이동하는 빠른 방법이 없기 때문
• 이중 링크드 리스트로 그 단점을 해결할 수 있다.

 

이중 링크드 리스트의 특징

1. 노드는 원소 멤버 이외에 리스트의 다음 노드와 이전 노드를 가리키는 멤버가 있다. (prev, next)
2. 이중 링크드 리스트는 양 끝(앞과 뒤) 각각을 가리키는 head, tail 포인터변수가 있다.
3. 프로그래밍의 간결함을 위해 head 앞에 헤더 노드와 후미 다음에 트레일러 노드를 추가하는 것이 좋다.
4. 헤더 노드와 트레일러 노드는 어떤 원소도 저장하지 않고 head와 tail에 빠른 접근을 제공.
5. 헤더 노드와 트레일러 노드를 더미 또는 센티널이라고 부른다.

(헤더노드 -> head -> ... -> ... -> tail -> 트레일러노드)

※ 더미 노드는 아무 원소도 저장하지 않음

 

 

 

 

 

 

---

이중 링크드 리스트 요소 삽입하기

• 이중 링크 구조이기 때문에 어떤 방향에서든 노드를 삽입할 수 있다.
• v = 이중 링크드 리스트의 노드
• z = v 바로 다음에 삽입하기 위한 새 노드
• w = v를 뒤따르는 노드 (v->next)

          z
v     <----     w (v->next)

 

v 다음에 새 노드 z를 삽입하기 위해서는?

1. z의 prev 링크는 v를 가리킴
2. z의 next 링크는 w를 가리킴
3. w의 prev는 z를 가리킴
4. v의 next 링크는 z를 가리킴

void DLinkedList::add(DNode* w, const Elem& e)
{
	DNode* z = new DNode;
	z->elem = e;
	z->next = w;
	z->prev = w->prev; // (w->prev == v)

	w->prev = z;
	z->prev->next = z;
}

 

 

 

 

 

---

이중 링크드 리스트 요소 삭제하기

• 이중 링크드 리스트에서 특정 노드를 제거하는 것은 쉽다.
• v = 삭제할 대상 노드
• u = v의 바로 앞 노드 (v->prev)
• w = v의 바로 다음 노드 (v->next)
• u와 w가 서로를 가리키도록 만들면 됨

u <---- v <---- w

 

v 노드 삭제 순서는?

1. w의 prev 노드가 u를 가리키도록 만든다
2. u의 next 노드가 w를 가리키도록 만든다.
3. v를 삭제한다. 

void DLinkedList::remove(DNode* v)
{
	DNode* u = v->prev;
	DNode* w = v->next;

	u->next = w;
	w->prev = u;

	delete v;
}

 

 

 

 

---

이중 링크드 리스트 구현

#pragma once

// 사용 용도에 따라 string이 아닌 다른 타입으로 정의할 수도 있음
typedef string Elem;

class DLinkedList;

class DNode
{
	Elem elem;
	DNode* prev;
	DNode* next;

	friend class DLinkedList; // 노드의 private 멤버에 접근 가능하도록 설정
};

class DLinkedList
{
public:
	DLinkedList();
	~DLinkedList();

	bool empty() const;			// 리스트가 비었는지 확인
	const Elem& front() const;		// 맨 앞 값 반환
	const Elem& back() const;		// 맨 뒤 값 반환

	void addFront(const Elem& e);	// 앞에서 추가
	void addBack(const Elem& e);	// 뒤에서 추가

	void removeFront();			// 앞에서 삭제
	void removeBack();			// 뒤에서 삭제

private:
	DNode* header;		//값을 가지지 않는 더미 노드
	DNode* trailer;		//값을 가지지 않는 더미 노드

protected:
	void add(DNode* v, const Elem& e); 	   // v의 prev 위치에 새로운 노드 삽입
	void remove(DNode* v);			   // v 노드 제거
};

• DLinkedList.h

 

 

 

 

 

#include "pch.h"
#include "DLinkedList.h"

DLinkedList::DLinkedList()
{
	header = new DNode;
	trailer = new DNode;
	header->next = trailer;
	trailer->prev = header;
}

DLinkedList::~DLinkedList()
{
	while (!empty())
		removeFront();

	delete header;
	delete trailer;
}

bool DLinkedList::empty() const
{
	return (header->next == trailer);
}

const Elem& DLinkedList::front() const
{
	return header->next->elem;
}

const Elem& DLinkedList::back() const
{
	return trailer->prev->elem;
}

// 리스트가 비었을지라도 header와 trailer가 있기 때문에 작동한다.
void DLinkedList::addFront(const Elem& e)
{
	add(header->next, e);
}

void DLinkedList::addBack(const Elem& e)
{
	add(trailer, e);
}

void DLinkedList::removeFront()
{
	remove(header->next);
}

void DLinkedList::removeBack()
{
	remove(trailer->prev);
}

// 두 함수는 protected 멤버로 외부에서 호출할 수 없다.
void DLinkedList::add(DNode* w, const Elem& e)
{
	DNode* z = new DNode;
	z->elem = e;
	z->next = w;
	z->prev = w->prev; // (w->prev == v)

	w->prev = z;
	z->prev->next = z;
}

void DLinkedList::remove(DNode* v)
{
	DNode* u = v->prev;
	DNode* w = v->next;

	u->next = w;
	w->prev = u;

	delete v;
}

• DLinkedList.cpp

 

 

 

 

 

 

 

 

 

 

 

 

---

환형 링크드 리스트 구현

• 단일 링크드 리스트와 같은 종류의 노드를 가짐
• head와 tail 을 갖는 대신 노드가 하나의 원형으로 연결되어 있다.
• 환형 링크드 리스트는 탐색 시 모든 노드를 방문하고 처음으로 되돌아 온다.
• 시작과 끝을 딱히 갖고 있지 않음, 대신 커서라는 노드가 있음 (탐색할 때 시작 지점 지정)
• 주목할만한 두 개의 위치가 있는데 하나는 front, 하나는 back이다.
• front는 back 바로 다음 원소이다.
• 커서에 의해 환형 링크드 리스트가 유지되고 이게 없으면 단일 링크드 리스트와 동일

#pragma once

typedef string Elem;

class CNode
{
private:
	Elem elem;
	CNode* next;

	friend class CLinkedList;
};

class CLinkedList
{
public:
	CLinkedList();
	~CLinkedList();

	bool empty() const;
	const Elem& front() const;
	const Elem& back() const;

	void advance();
	void add(const Elem& e);
	void remove();

private:
	CNode* cursor;
};

• CLinkedList.h

 

 

 

#include "pch.h"
#include "CLinkedList.h"

CLinkedList::CLinkedList()
	: cursor(nullptr)
{ }

CLinkedList::~CLinkedList()
{
	while (!empty())
		remove();
}

bool CLinkedList::empty() const
{
	return cursor == nullptr;
}

const Elem& CLinkedList::front() const
{
	return cursor->next->elem;
}

const Elem& CLinkedList::back() const
{
	return cursor->elem;
}

void CLinkedList::advance()
{
	cursor = cursor->next;
}

// 환형 링크드 리스트에 대한 삽입은 커서의 '다음'에서 발생한다.
void CLinkedList::add(const Elem& e)
{
	CNode* v = new CNode;
	v->elem = e;

	if (cursor == nullptr)
	{
		v->next = v;			// v는 자기 자신을 가리킨다.
		cursor = v;				// 커서는 v를 가리킨다.
	}

	else
	{
		//            front
		v->next = cursor->next;	// v를 커서의 뒤에 연결
		cursor->next = v;
		//  front    = v ( 새 노드 )
	}

	// cursor		= back
	// cursor->next = front
}

void CLinkedList::remove()
{
	// old == front
	CNode* old = cursor->next;

	if (old == cursor)		// old가 cursor인 경우?
	{
		cursor = nullptr;	
		// 커서가 가진 값을 nullptr로 수정
		// 아래서 old를 삭제할 건데 삭제된 주소를 가리키면 안되니까
	}

	else
	{				// cursor->next->next
		cursor->next = old->next;
		// old가 지워지므로 old의 다음 요소를 front에 넣어준다.
		// 
	}

	delete old;
}

• CLinkedList.cpp