이중 연결 리스트(Doubly Linked List)

1. 개요

일반적인 연결 리스트(linked list)의 노드들은 다음 노드를 가리키는 포인터만 포함하고 있기 때문에 한 방향으로만 탐색이 가능하다. 그러나 이중 연결 리스트(doubly linked list)의 노드는 아래의 그림과 같이 next와 prev라는 두 개의 포인터를 포함하고 있다.

노드의 next 포인터는 일반적인 연결 리스트와 같이 다음 노드를 가리키며, 이중 연결 리스트의 노드에 추가된 prev 포인터는 이전 노드를 가리킨다.

이중 연결 리스트의 가장 큰 장점은 일반적인 연결 리스트에 비해 효율적으로 탐색할 수 있다는 점이다. 예를 들어, 노드의 수가 $n$인 일반적인 연결 리스트에서는 $n-1$번째 노드에 접근하기 위해, 총 $n-2$번의 포인터 추적이 필요하다. 그러나 이중 연결 리스트에서는 tail이 가리키는 노드에서 prev 포인터를 추적하면, 단 한 번의 포인터 추적만으로도 $n-1$번째 노드에 접근할 수 있다. 이중 연결 리스트의 이러한 속성을 일반화하면, 노드의 수가 $n$인 이중 연결 리스트에서 $[\frac{n}{2}]$보다 작은 순서의 노드는 head에서부터 탐색하고, $[\frac{n}{2}]$보다 크거나 같은 순서의 노드는 tail에서부터 탐색하도록 구현하여 최대 탐색 시간을 일반적인 연결 리스트에 비해 반으로 줄일 수 있다.

그러나 이중 연결 리스트에는 일반적인 연결 리스트보다 포인터를 2배 더 많이 사용해야 하고, 구현이 복잡하다는 단점이 존재한다. 이러한 저장공간의 낭비에도 불구하고 최대 탐색 시간을 반으로 줄일 수 있다는 점 때문에 대부분의 연결 리스트는 이중 연결 리스트로 구현된다.

2. Class 정의

C++ 문법을 이용하여 이중 연결 리스트를 정의하면, 아래와 같이 정의할 수 있다.

이중 연결 리스트의 노드인 class Node는 데이터 필드와 다음, 이전 노드를 가리키는 포인터로 구성되어 있다. 또한, 이중 연결 리스트를 정의하는 class DoublyLinkedList에는 일반적인 insertion, deletion 연산이 정의되어 있으며, 추가적으로 탐색의 효율성을 향상시키기 위해, 찾으려는 노드의 위치에 따라 탐색의 방향을 변경하는 findNode 함수가 정의되어 있다.

3. findNode 함수

일반적인 연결 리스트는 항상 head 포인터에서 시작하여 각 노드의 next 포인터를 추적하면서 리스트를 탐색한다. 그러나 이중 연결 리스트는 탐색의 효율성을 향상시키기 위해 찾으려는 노드의 위치에 따라 탐색의 시작 위치와 탐색의 방향이 변경한다. 이중 연결 리스트의 findNode 함수는 찾으려는 노드의 위치에 따라 탐색의 시작 위치와 탐색의 방향을 변경하여 탐색을 수행하고, 찾고자 하는 위치의 이전 위치에 저장된 노드의 주소를 반환한다.

findNode 함수는 인자로 전달 받는 index가 $[\frac{n}{2}]$보다 작으면 head 포인터에서 시작하여 각 노드의 next 포인터를 추적하는 방향으로 탐색을 진행하고, index가 $[\frac{n}{2}]$보다 크거나 같으면 tail 포인터에서 시작하여 각 노드의 prev 포인터를 추적하는 방향으로 탐색을 진행한다. 동적으로 탐색의 시작 위치와 방향을 설정하는 findNode 함수를 통해 이중 연결 리스트는 최대 탐색 시간을 일반적인 연결 리스트의 반으로 줄일 수 있다.

4. Insertion 연산

이중 연결 리스트의 insertion 연산의 동작은 일반적인 연결 리스트의 insertion 연산과 매우 유사하다. 한 가지 다른 점은 노드의 next 포인터뿐만 아니라, prev 포인터까지 값을 설정해주어야 한다는 것이다. 아래의 그림은 insertion 연산의 동작을 나타낸다.

아래의 코드는 insertion 연산의 구현 코드이다.

5. Deletion 연산

Deletion 연산의 구현 코드는 아래와 같다.

6. 전체 소스 코드

위에서 정의한 이중 연결 리스트의 전체 소스 코드는 아래와 같다.

소스 파일: DoublyLinkedList.h

#ifndef D_LINKED_LIST
#define D_LINKED_LIST

#include <iostream>
using namespace std;

template <typename T>
class Node {
	template <typename T>
	friend class DoublyLinkedList;
public:
	Node(const T data);
private:
	Node *next;
	Node *prev;
	T data;
};

template <typename T>
class DoublyLinkedList {
public:
	DoublyLinkedList();
	~DoublyLinkedList();
	bool insert(const T data, const int index);
	bool remove(const int index);
	int size() const;
	void print(ostream & stream);
private:
	Node<T> *head;
	Node<T> *tail;
	int numNodes;
	void init();
	Node<T> *findNode(const int index);
};

template <typename T>
Node<T>::Node(const T data) {
	this->data = data;
	this->next = NULL;
	this->prev = NULL;
}

template <typename T>
DoublyLinkedList<T>::DoublyLinkedList() {
	init();
}

template <typename T>
DoublyLinkedList<T>::~DoublyLinkedList() {
	Node<T> *current = head;
	Node<T> *next = NULL;

while (current != NULL) {
		next = current->next;
		delete current;
		current = next;
	}
}

template <typename T>
bool DoublyLinkedList<T>::insert(const T data, const int index) {
	if (index < 0 || index > numNodes) {
		return false;
	}
	else {
		Node<T> *newNode = new Node<T>(data);

if (index == 0) {
			newNode->next = head;

if (numNodes == 0) {
				tail = newNode;
			}
			else {
				head->prev = newNode;
			}

head = newNode;
		}
		else if (index == numNodes) {
			newNode->prev = tail;
			tail->next = newNode;
			tail = newNode;
		}
		else {
			Node<T> *current = findNode(index);
			Node<T> *nextNode = current->next;

newNode->next = current->next;
			newNode->prev = current;
			current->next = newNode;
			nextNode->prev = newNode;
		}
		numNodes++;

return true;
	}
}

template <typename T>
bool DoublyLinkedList<T>::remove(const int index) {
	if (index < 0 || index >= numNodes) {
		return false;
	}
	else {
		Node<T> *current = NULL;

if (index == 0) {
			current = head;
			head = current->next;
			head->prev = NULL;
			delete current;
		}
		else {
			current = findNode(index);
			Node<T> *nextNode = current->next->next;

delete current->next;
			current->next = nextNode;
			
			if (index == numNodes - 1) {
				tail = current;
			}
			else {
				nextNode->prev = current;
			}
		}
		numNodes--;

return true;
	}
}

template <typename T>
int DoublyLinkedList<T>::size() const {
	return numNodes;
}

template <typename T>
void DoublyLinkedList<T>::print(ostream & stream) {
	Node<T> *current = head;

while (current != NULL) {
		stream << current->data << endl;
		current = current->next;
	}
}

template <typename T>
void DoublyLinkedList<T>::init() {
	head = NULL;
	tail = NULL;
	numNodes = 0;
}

template <typename T>
Node<T> *DoublyLinkedList<T>::findNode(const int index) {
	Node<T> *current = NULL;

if (index < numNodes / 2) {
		current = head;

for (int i = 1; i < index; i++) {
			current = current->next;
		}

return current;
	}
	else {
		current = tail;

for (int i = numNodes; i > index; i--) {
			current = current->prev;
		}

return current;
	}
}
#endif

저작자표시 비영리 변경금지

이중 연결 리스트(Doubly Linked List)

관련글

티스토리툴바