연결 리스트(Linked List)

1. 개요

선형 사상(sequential mapping)을 이용하는 배열, 큐와 같은 구조에서 insertion, deletion 연산은 매우 많은 비용이 소모된다. 아래의 그림은 배열에서 insertion 연산이 발생하는 경우, 연산이 실행되는 과정을 나타낸다.

선형 사상을 이용하는 배열과 같은 구조에서는 중간에 데이터를 추가하기 위해서는 해당 위치 다음에 저장된 모든 데이터를 일정 위치만큼씩 옮겨야한다. 이러한 shift 동작은 메모리 상에서도 많은 오버헤드가 발생하지만, 만약 하드디스크 상에서 shift 동작이 발생한다면 시스템이 감당할 수 없을 정도의 오버헤드가 발생할 수도 있다. 배열과 같은 선형 사상을 이용하는 구조의 또다른 문제점은 항상 고정된 크기를 갖기 때문에 예상한 것보다 데이터가 적게 저장되는 경우에는 저장 공간이 낭비된다는 것이다. 또한, 선형 사상 구조는 최대로 저장할 수 있는 데이터의 수가 고정되기 때문에 선형 사상 구조에는 처음에 설정한 최대 데이터의 수보다 많은 데이터를 입력할 수 없다. 즉, 배열이나 큐와 같은 선형 사상 구조는 유연하지 못하다는 단점이 존재한다.

선형 사상 구조의 문제점을 해결하기 위한 방법은 위의 그림과 같이 연결 구조 형태로 데이터를 저장하는 것이다. 이러한 구조에서는 insertion, deletion 연산이 발생하여도 다음 데이터를 가리키는 포인터 하나만 변경하면 된다. 또한, 예상한 것보다 데이터가 적게 저장되거나 많게 저장되는 경우에도 연결 구조에서는 데이터가 저장된 만큼만 저장 공간을 차지하기 때문에 선형 사상 구조에 비해 매우 유연하다.

2. Class 정의

C++ 문법을 이용하여 연결 리스트를 정의하면, 아래와 같이 정의할 수 있다. C++에는 delete라는 키워드가 정의되어 있으므로, deletion 연산에 대한 함수를 remove라고 정의하였다.

Node 클래스는 연결 리스트의 각 요소를 정의하기 위한 클래스이며, 실제 연결 리스트는 LinkedList 클래스로 정의된다. 위의 코드에는 연결 리스트의 가장 기본적인 연산인 append, insert, remove만 정의하였고, 부수적으로 연결 리스트의 크기를 반환하는 size 함수와 연결 리스트의 모든 내용을 출력하는 print 함수를 추가하였다. 또한, 연산의 효율성을 향상시키기 위해 연결 리스트의 가장 마지막 요소를 가리키는 tail 포인터를 추가하였다. 아래의 appending, insertion, deletion 연산에 대한 설명에서 tail 포인터의 이용을 자세하게 설명한다.

3. Appending 연산

연결 리스트의 appending 연산은 아래의 그림과 같이 연결 리스트의 가장 마지막 부분에 새로운 데이터를 추가하는 것이다.

연결 리스트의 가장 큰 단점은 각 요소를 탐색하기 위해서 반복적으로 포인터를 추적하는 작업을 해야 한다는 것이다. 산술적인 연산으로 주소를 계산하는 선형 사상 구조와 다르게 연결 리스트는 하나씩 포인터를 추적하면서 데이터를 접근해야 하기 때문에 $n$번째 데이터에 접근하기 위해 총 $n−1$번의 포인터 추적을 해야한다. 선형 사상 구조에서는 $n$번째 데이터를 접근하기 위해 단 한번의 산술적인 주소 계산만 필요로 하는 것에 비하면 연결 리스트의 데이터 접근 방식은 매우 비효율적이다. 연결 리스트의 마지막 부분에 데이터를 추가하는 appending 연산은 연결 리스트의 모든 데이터를 접근한 다음에 실행되기 때문에 오버헤드가 매우 큰 연산이다. 그러나 연결 리스트의 마지막 부분을 가리키는 tail 포인터를 추가하면, appending 연산은 단 한 번의 포인터 추적만으로도 실행이 가능하기 때문에 연결 리스트의 구현에 tail 포인터를 추가하였다.

4. Insertion 연산

연결 리스트의 appending 연산은 항상 연결 리스트의 마지막 부분에 데이터를 추가하는 반면, insertion 연산은 연결 리스트 내의 특정 위치에 새로운 데이터를 추가하는 연산이다. Insertion 연산의 동작은 아래의 그림과 같다.

Insertion 연산은 head 포인터부터 시작하여 인자로 전달받은 위치까지 포인터를 추적한 다음, 해당 위치에 새로운 데이터를 추가한다. 새로운 데이터가 추가되는 위치를 가리키는 노드는 새로운 데이터를 가리키고, 새로운 데이터는 해당 위치에 원래 존재하고 있었던 노드를 가리킨다. 아래의 그림은 이러한 과정을 나타낸다.

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

5. Deletion 연산

Deletion 연산은 연결 리스트의 특정 위치에 저장된 데이터를 제거한다. Deletion 연산의 동작은 아래의 그림과 같다.

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

6. 전체 소스 코드

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

소스 파일: LinkedList.h

#ifndef LINKED_LIST
#define LINKED_LIST

#include <iostream>
using namespace std;

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

template <typename T>
class LinkedList {
public:
	LinkedList();
	~LinkedList();
	void append(const T data);
	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();
};

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

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

template <typename T>
LinkedList<T>::~LinkedList() {
	Node<T> *current = head;
	Node<T> *next = NULL;
	while (current != NULL) {
		next = current->next;
		delete current;
		current = next;
	}
}

template <typename T>
void LinkedList<T>::append(const T data) {
	Node<T> *newNode = new Node<T>(data);

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

numNodes++;
}

template <typename T>
bool LinkedList<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;
			head = newNode;

if (numNodes == 0) {
				tail = newNode;
			}

numNodes++;
		}
		else if (index == numNodes) {
			append(data);
		}
		else {
			Node<T> *current = head;

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

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

return true;
	}
}

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

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

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

if (index == numNodes - 1) {
				tail = current;
			}

temp = current->next;
			current->next = temp->next;
			delete temp;
		}
		numNodes--;

return true;
	}
}

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

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

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

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

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

연결 리스트(Linked List)

관련글

티스토리툴바