연결 리스트의 개념과 클래스 구현

이번 글에서는 연결 리스트(linked list)의 C++ 클래스 구현에 대해 알아보겠습니다.

목차

1. 단순 연결 리스트와 체인
- 개념
- 노드와 체인의 설계
- 템플릿 클래스 체인의 설계와 구현
2. 원형 리스트
- 개념
- 구현
3. 이중 연결 리스트
- 개념
- 구현

참고한 자료

C++ 자료구조론, Horowitz 외
http://www.yes24.com/Product/Goods/2656393

C++ 자료구조론 (2판) - YES24

---

단순 연결 리스트와 체인

개념

배열이나 스택, 큐와 같은 자료 구조들은 리스트 중간에 원소를 삽입하거나 삭제하는 작업이 어렵습니다. 지나치게 많은 원소들의 위치를 이동시켜야 하기 때문인데요, 이러한 순차(sequential) 표현의 문제점을 연결된(linked) 표현으로 잘 해결할 수 있습니다. 연결된 표현에서는 각 리스트 원소들이 그 다음 원소를 가리키는 포인터(pointer) 또는 링크(link)를 가지는데, 이렇게 데이터 필드와 링크 또는 포인터를 포함한 것을 노드(node)라고 부릅니다.

하나의 링크 필드를 가진 노드들을 순차적으로 연결한 구조를 단순 연결 리스트(singly linked list) 또는 체인(chain)이라고 합니다. 앞서 언급한 대로 연결 리스트는 임의의 위치에서의 삽입과 삭제가 용이하다는 것이 장점입니다. 예를 들어 원소 B를 A, C 사이에 삽입하려고 한다면 다음의 절차를 따르면 됩니다.

- 새로운 노드의 data 필드에 B를 설정하고 link 필드가 C를 저장하는 노드를 가리키도록 한다
- A를 저장하는 노드의 link 필드가 새로운 노드를 가리키도록 한다

노드와 체인의 설계

간단하게 문자열을 저장하는 노드를 생각해 봅시다. 이를 클래스로 정의하면 앞서 논의한 바에 의해 다음과 같습니다.

class Node
{
private:
    string data;
    Node* link;
};

다음으로 노드들을 개념적으로 포함하는 체인 클래스를 설계하는데, Node의 data와 link를 private로 선언했기 때문에 Chain을 Node의 friend로 선언할 것입니다.

class Chain; // 전방 선언

class Node
{
friend class Chain;
private:
    string data;
    Node* link;
};

class Chain
{
public:
    // 리스트 조작 연산
private:
    Node* first;
};

여기서 Chain은 개념적으로 여러 Node들을 포함하지만, 물리적으로는 첫 번째 노드(first)만 포함해도 충분합니다. friend로 선언되어 있어 다른 Node에도 접근이 가능하기 때문이지요. 또 Chain 클래스의 정의 안에서 Node 클래스를 정의하는 '중첩 클래스' 방법으로도 같은 구현이 가능하지만, Node를 여러 번 다른 클래스에 의하여 사용하기 좋도록 '복합 클래스' 방법을 사용하겠습니다.

 

Node의 생성자(constructor)는 다음과 같습니다.

Node(string element = "", Node* next = 0) {
    data = element;
    link = next;
}

x를 체인에 있는 임의의 노드에 대한 포인터라고 하고, data 필드에 임의의 문자열 str을 가진 노드를 x가 가리키는 노드 다음에 삽입하는 함수를 구현해 봅시다.

void Chain::Insert(Node* x, string str) {
    if (!first) {
        // 공백 리스트인 경우
        first = new Node(str);
    }
    else {
        // x 다음에 삽입
        x->link = new Node(str, x->link);
    }
}

다음으로는 x가 가리키는 노드를 체인으로부터 삭제하는 함수를 구현해 봅니다.

void Chain::Delete(Node* x) {
    if (x == first) {
        first = first->link;
    } else if (x->link) {
        Node* y = x->link;
        y->link = x->link;
    }
    delete x;
}

템플릿 클래스 체인의 설계와 구현

이번에는 앞서 살펴본 노드와 체인을 C++ 템플릿을 이용하여 구현해 보겠습니다. 노드와 체인 클래스의 템플릿 정의는 다음과 같습니다.

template <class T>
class Chain; // 전방 선언

template <class T>
class Node
{
friend class Chain<T>;
public:
    Node(T element) {
        data = element;
        link = 0;
    }
private:
    T data;
    Node<T>* link;
};

template <class T>
class Chain
{
public:
    Chain() {
        first = 0;
        last = 0;
    }
    // 체인 조작 연산들
private:
    Node<T>* first;
    Node<T>* last;
};

체인의 끝에 삽입하는 연산을 효율적으로 하기 위해 Chain의 private 멤버로 last를 추가했습니다. last를 이용하여 체인의 끝에 노드를 삽입하는 연산을 구현해 보겠습니다.

template <class T>
void Chain<T>::InsertBack(const T& e)
{
    if (first) {
        // 공백이 아닌 체인
        last->link = new Node<T>(e);
        last = last->link;
    } else {
        first = last = new Node<T>(e);
    }
}

다음으로, 두 체인을 접합(concatenate)하는 연산을 구현하면 다음과 같습니다.

template <class T>
void Chain<T>::Concatenate(Chain<T>& b) {
    if (first) {
        last->link = b.first;
        last = b.last;
    } else {
        first = b.first;
        last = b.last;
    }
    b.first = b.last = 0;
}

체인에 있는 원소의 순서를 역순으로 변환하는 연산을 구현해 보겠습니다. 원소의 이동 없이 포인터만 while 루프를 돌면서 변경하면 되기 때문에, 제자리에서(in-place) 연산이 수행되며 선형 시간 안에 연산이 가능합니다.

template <class T>
void Chain<T>::Reverse() {
    Node<T>* current = first;
    Node<T>* previous = 0; // current를 따라가는 포인터
    while (current) {
        Node<T>* r = previous; // previous를 따라가는 포인터
        previous = current;
        current = current->link; //  current는 다음 노드로 이동
        previous->link = r; // previous를 이전 노드와 연결
    }
    first = previous;
}

마지막으로, Chain 클래스의 완전한 구현을 보여드리겠습니다.

#include <iostream>
using namespace std;

template <class T>
class Chain; // 전방 선언

template <class T>
class Node
{
	friend class Chain<T>;
	template <class T>
	friend ostream& operator<<(ostream& os, Node<T>* n);
public:
	Node(T element) {
		data = element;
		link = 0;
	}
	Node<T>* Next() {
		return link;
	}
private:
	T data;
	Node<T>* link;
};

template <class T>
class Chain
{
public:
	// 생성자
	Chain() {
		first = 0;
		last = 0;
	}
	// 소멸자
	~Chain();
	// 반환하는 함수
	Node<T>* Front();
	Node<T>* Back();
	Node<T>* Get(int i);
	// 삽입하는 함수
	void InsertFront(const T& e);
	void InsertBack(const T& e);
	void Insert(int i, const T& e);
	// 삭제하는 함수
	void DeleteFront();
	void DeleteBack();
	void Delete(int i);
	// 체인 조작 연산들
	void Concatenate(Chain<T>& b);
	void Reverse();
	// 출력 연산자
	template <class T>
	friend ostream& operator<<(ostream& os, Chain<T>& c);
private:
	Node<T>* first;
	Node<T>* last;
};

template <class T>
Chain<T>::~Chain() {
	while (first != last) {
		Node<T>* temp = first;
		first = temp->link;
		delete temp;
	}
	delete first;
}

template <class T>
Node<T>* Chain<T>::Front() {
	return first;
}

template <class T>
Node<T>* Chain<T>::Back() {
	return last;
}

template <class T>
Node<T>* Chain<T>::Get(int num) {
	Node<T>* current = first;
	for (int i = 0; (i < num) && (current != 0); i++) {
		current = current->link;
	}
	if (current == 0) {
		throw "Out of bound";
	}
	return current;
}

template <class T>
void Chain<T>::InsertFront(const T& e) {
	if (first) {
		// 공백이 아닌 체인
		Node<T>* temp = first->link;
		first = new Node<T>(e);
		first->link = temp;
	}
	else {
		first = last = new Node<T>(e);
	}
}

template <class T>
void Chain<T>::InsertBack(const T& e) {
	if (first) {
		// 공백이 아닌 체인
		last->link = new Node<T>(e);
		last = last->link;
	}
	else {
		first = last = new Node<T>(e);
	}
}

template <class T>
void Chain<T>::Insert(int i, const T& e) {
	if (i == 0) {
		InsertFront(e);
	}
	else {
		Node<T>* previous = Get(i - 1);
		if (previous->link == 0) {
			InsertBack(e);
		}
		Node<T>* newNode = new Node<T>(e);
		newNode->link = previous->link;
		previous->link = newNode;
	}
}

template <class T>
void Chain<T>::DeleteFront() {
	if (first) {
		Node<T>* old = first;
		first = first->link;
		delete old;
	}
	else {
		throw "Nothing to delete";
	}
}

template <class T>
void Chain<T>::DeleteBack() {
	if (first) {
		Node<T>* current = first;
		int i = 0;
		for (i = 0; current != last; i++) {
			current = current->link;
		}
		if (i == 0) {
			DeleteFront();
		}
		Node<T>* previous = Get(i - 1);
		Node<T>* old = last;
		previous->link = 0;
		last = previous;
		delete old;
	}
	else {
		throw "Nothing to delete";
	}
}

template <class T>
void Chain<T>::Delete(int i) {
	if (i == 0) {
		DeleteFront();
	}
	else if (first) {
		Node<T>* previous = Get(i - 1);
		Node<T>* old = previous->link;
		previous->link = old->link;
		delete old;
	}
	else {
		throw "Nothing to delete";
	}
}

template <class T>
void Chain<T>::Concatenate(Chain<T>& b) {
	if (first) {
		last->link = b.first;
		last = b.last;
	}
	else {
		first = b.first;
		last = b.last;
	}
	b.first = b.last = 0;
}

template <class T>
void Chain<T>::Reverse() {
	Node<T>* current = first;
	Node<T>* previous = 0; // current를 따라가는 포인터
	while (current) {
		Node<T>* r = previous; // previous를 따라가는 포인터
		previous = current;
		current = current->link; //  current는 다음 노드로 이동
		previous->link = r; // previous를 이전 노드와 연결
	}
	first = previous;
}

template <class T>
ostream& operator<<(ostream& os, Node<T>* n) {
	os << n->data;
	return os;
}

template <class T>
ostream& operator<<(ostream& os, Chain<T>& c) {
	Node<T>* current = c.first;
	while (current != c.last) {
		os << current << " -> ";
		current = current->Next();
	}
	os << current << endl;
	return os;
}

int main()
{
	Chain<int> intChain;
	intChain.InsertFront(1); // 1
	intChain.InsertBack(4);  // 1 4
	intChain.Insert(1, 3);   // 1 3 4
	intChain.Insert(1, 2);   // 1 2 3 4
	intChain.InsertBack(5);  // 1 2 3 4 5
	intChain.DeleteFront();  // 2 3 4 5
	intChain.DeleteBack();   // 2 3 4
	intChain.Delete(1);      // 2 4
	intChain.InsertBack(6);  // 2 4 6
	cout << intChain;

	return 0;
}

위 main 함수의 실행 결과는 다음과 같습니다.

원형 리스트

개념

체인 마지막 노드의 link가 다시 첫 번째 노드를 가리키게 하면 원형 리스트(circular list)가 됩니다. 원형 리스트에서는 한 노드에서 다른 어떤 노드로든 접근할 수 있다는 것이 단순 연결 리스트(체인)에 비한 장점입니다.

구현

첫 번째 노드의 앞에 새 노드를 삽입한다면, 마지막 노드의 link를 변경해야 하는데 마지막 노드를 찾을 때까지 너무 많이 이동해야 합니다. 그래서 원형 리스트에 대한 접근 포인터는 첫 번째가 아닌 마지막 노드를 가리키도록 합니다.

다음은 원형 리스트를 구현한 템플릿 클래스 CircularList의 InsertFront 함수 구현 코드입니다.

template <class T>
void CircularList<T>::InsertFront(const T& e) {
    // last는 리스트 마지막 노드를 가리키는 포인터
    Node<T>* newNode = new Node<T>(e);
    if (last) {
        // 공백이 아닌 리스트
        newNode->link = last->link;
        last->link = newNode;
    } else {
        last = newNode;
        newNode->link = newNode;
    }
}

이중 연결 리스트

개념

앞서 단순 연결 리스트를 구현하면서, 한쪽 방향으로만 이동할 수 있기에 발생하는 어려움이 많이 보였습니다. 예를 들어특정 노드를 삭제해야 하는 경우 그 전 노드를 찾기 위해 처음부터 이동하는 방법밖에 없었죠. 이런 어려움을 해결하기 위해 하나는 앞쪽, 하나는 뒤쪽으로 연결하는 두 개의 링크 필드를 가지도록 이중 연결 리스트(doubly linked list)를 사용하는 것이 편리할 것입니다.

구현

이중 연결 리스트에 들어갈 노드는 data, left, right의 세 private 멤버를 가질 것이고, 리스트는 기존과 같이 하나의 노드에 대한 포인터만을 물리적으로 포함할 것입니다. 이때 그 하나의 노드는 헤더(header) 노드라고 부를 것이고, 헤더 노드의 앞뒤로 이동을 편하게 할 수 있도록 이중 연결 리스트를 원형으로 구현할 것입니다.

 

우선 클래스 정의는 다음과 같습니다.

template <class T>
class DblList;

template <class T>
class DblListNode
{
	friend class DblList<T>;
private:
	T data;
	DblListNode<T>* left;
	DblListNode<T>* right;
};

template <class T>
class DblList
{
public:
	// 리스트 조작 연산들
private:
	DblListNode<T>* first;
};

다음으로, 삽입과 삭제하는 함수는 다음과 같이 구현할 수 있습니다.

template <class T>
void DblList<T>::Insert(DblListNode<T>* p, DblListNode<T>* x) {
	// x의 오른쪽에 p 삽입
	p->left = x;
	p->right = x->right;
	x->right->left = p;
	x->right = p;
}

template <class T>
void DblList<T>::Delete(DblListNode<T>* x) {
	if (x == first) throw "헤더 노드 삭제는 허용되지 않습니다";
	else {
		x->left->right = x->right;
		x->right->left = x->left;
		delete x;
	}
}

이제 생성자, 소멸자와 출력 연산자를 포함하는 클래스의 완전한 구현을 살펴보겠습니다.

#include <iostream>
using namespace std;

template <class T>
class DblList;

template <class T>
class DblListNode
{
	friend class DblList<T>;
	template <class T>
	friend ostream& operator<<(ostream& os, DblListNode<T>* n);
public:
	DblListNode(T element) {
		data = element;
		left = right = this;
	}
	DblListNode<T>* Right() {
		return right;
	}
private:
	T data;
	DblListNode<T>* left;
	DblListNode<T>* right;
};

template <class T>
class DblList
{
public:
	// 생성자
	DblList() {
		first = new DblListNode<T>(0);
	}
	// 소멸자
	~DblList();
	// 헤더 접근
	DblListNode<T>* Header() {
		return first;
	}
	// 삽입하는 함수
	void Insert(DblListNode<T>* p, DblListNode<T>* x);
	// 삭제하는 함수
	void Delete(DblListNode<T>* x);
	// 출력 연산자
	template <class T>
	friend ostream& operator<<(ostream& os, DblList<T>& c);
private:
	DblListNode<T>* first;
};

template <class T>
DblList<T>::~DblList() {
	while (first->right != first) {
		DblListNode<T>* temp = first->right;
		first->right = temp->right;
		temp->right->left = first;
		delete temp;
	}
	delete first;
}

template <class T>
void DblList<T>::Insert(DblListNode<T>* p, DblListNode<T>* x) {
	// x의 오른쪽에 p 삽입
	p->left = x;
	p->right = x->right;
	x->right->left = p;
	x->right = p;
}

template <class T>
void DblList<T>::Delete(DblListNode<T>* x) {
	if (x == first) throw "헤더 노드 삭제는 허용되지 않습니다";
	else {
		x->left->right = x->right;
		x->right->left = x->left;
		delete x;
	}
}

template <class T>
ostream& operator<<(ostream& os, DblListNode<T>* n) {
	os << n->data;
	return os;
}

template <class T>
ostream& operator<<(ostream& os, DblList<T>& c) {
	DblListNode<T>* current = c.first;
	while (current->Right() != c.first) {
		current = current->Right();
		os << current << " <-> ";
	}
	return os;
}

int main()
{
	DblList<int> intList;
	DblListNode<int>* one = new DblListNode<int>(1);
	DblListNode<int>* two = new DblListNode<int>(2);
	DblListNode<int>* three = new DblListNode<int>(3);
	DblListNode<int>* four = new DblListNode<int>(4);

	intList.Insert(intList.Header(), one);
	intList.Insert(three, one);
	intList.Insert(two, one);
	intList.Delete(three);
	intList.Insert(four, two);

	cout << intList;

	return 0;
}

위의 main함수의 실행 결과는 다음과 같습니다.

---

다음 게시물에서는 오랜만에! BOJ 문제를 풀어보겠습니다.