[자료구조] 연결 리스트(linked list)

연결 리스트는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조다. 사용자가 어떤 애플리케이션에서 배열을 사용 중이라면 아마도 배열 대신 연결 리스트를 쓰고 있을 가능성이 크다. 연결 리스트는 나란히 이어진 메모리 셀 묶음이 아니다. 서로 인접하지 않음 메모리 셀 묶음으로 이뤄진다. 컴퓨터 메모리 전체에 걸쳐 여러 셀에 퍼져 있을 수 있다. 서로 인접하지 않은 이러한 셀을 노드라 부른다.

 

각 노드는 노드에 저장된 데이터뿐만 아니라 연결 리스트 내에 다음 노드의 메모리 주소도 저장해야 한다.

위 그림을 보면 연결 리스트에 "a", "b", "c", "d", 4개의 데이터가 있다. 하지만 데이터를 저장하는 데 각 노드마다 메모리 셀 두 개씩, 총 메모리 셀 여덟 개를 사용한다. 연결 리스트를 다루는 코드는 항상 첫 번째 노드가 메모리 어디에 시작하는지 알아야 한다. 각 노드에는 다음 노드의 링크가 들어 있으므로 애플리케이션에 연결 리스트의 첫 번째 노드를 제공하면 링크를 따라서 나머지 리스트를 조합할 수 있다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

class CNode
{
public:
	CNode(string _data) { data = _data; }

	string data;
	CNode* nextNode;
};

int main()
{
	CNode* node_1 = new CNode("once");
	CNode* node_2 = new CNode("upon");
	node_1->nextNode = node_2;
	CNode* node_3 = new CNode("a");
	node_2->nextNode = node_3;
	CNode* node_4 = new CNode("time");
	node_3->nextNode = node_4;

	return 0;
}

위 코드로 각각의 문자열을 포함하는 노드 네 개짜리 리스트를 생성했다. Node 클래스만 있어도 연결 리스트를 만들 수 있지만, 프로그램에게 연결 리스트에 대해 쉽게 알려주기 위해 LinkedList 클래스를 만들어 보자.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

class CNode
{
public:
	CNode(string _data) { data = _data; }

	string data;
	CNode* nextNode;
};

class CLinkedList
{
public:
	CLinkedList(CNode* first) { firstNode = first; }

	CNode* firstNode;
};

int main()
{
	CNode* node_1 = new CNode("once");
	CNode* node_2 = new CNode("upon");
	node_1->nextNode = node_2;
	CNode* node_3 = new CNode("a");
	node_2->nextNode = node_3;
	CNode* node_4 = new CNode("time");
	node_3->nextNode = node_4;

	CLinkedList* list = new CLinkedList(node_1);

	return 0;
}

CLinkedList는 연결 리스트의 첫 번째 노드를 가리키므로 연결 리스트에 대한 핸들처럼 동작한다. 연결 리스트가 무엇인지 알았으니 전형적인 배열과 성능을 비교해보자.

---

읽기

프로그램이 연결 리스트 인덱스 2에 있는 값을 읽을 때, 컴퓨터는 메모리 어디에서 찾아야 할지 바로 알 수 없으므로 한 단계로 찾을 수 없다. 연결 리스트의 각 노드는 메모리 어디든 있을 수 있기 때문이다. 프로그램은 연결 리스트의 첫 번째 노드의 메모리 주소만 알 뿐이다.

 

읽기 함수를 구현해 보자.

class CLinkedList
{
public:
	CLinkedList(CNode* first) { firstNode = first; }

	CNode* firstNode;

	string read(int index)
	{
		CNode* node = firstNode;
		int node_index = 0;

		while (node_index < index)
		{
			node = node->nextNode;
			node_index++;
			
			if (node == nullptr)
				return nullptr;
		}
		return node->data;
	}
};

	cout << list->read(3) << endl;

3번째 index를 읽어오면, "time"이 출력됨을 알 수 있다.

컴퓨터가 어떤 인덱스에 있는 값을 찾을 때 최악의 시나리오는 리스트의 마지막 인덱스를 찾아보는 것이다. 

---

검색

배열과 연결 리스트는 검색 효율성이 같다. 검색은 리스트 내에서 어떤 데이터를 찾고 그 인덱스를 얻는 것이다. 배열이든 연결 리스트든 프로그램은 검색하고 있는 값을 찾을 때까지 끝까지 확인해야 한다.

 

값의 인덱스를 구하는 함수를 구현해 보자.

	int index_of(string value)
	{
		CNode* node = firstNode;
		int node_index = 0;

		do {
			if (node->data == value)
				return node_index;

			node = node->nextNode;
			node_index++;
		} while (node != nullptr);
		return -1;
	}

---

삽입

연결 리스트가 배열에 비해 뚜렷한 장점을 보이는 연산이 바로 삽입이다. 배열 삽입에서 최악의 시나리오는 프로그램이 인덱스 0에 데이터를 삽입할 때였다. 반면 연결 리스트는 리스트 앞에 삽입하는 데 딱 한 단계만 걸린다.

 

새로운 노드를 만들고 연결만 새롭게 하면 된다. 만들어 보자.

	void insert_at_index(int index, string value)
	{
		CNode* node = firstNode;
		int node_index = 0;

		while (node_index < index - 1)
		{
			node = node->nextNode;
			node_index++;
		}

		CNode* newNode = new CNode(value);
		if (index == 0)
		{
			firstNode = newNode;
			newNode->nextNode = node;
		}
		else
		{
			newNode->nextNode = node->nextNode;
			node->nextNode = newNode;
		}
	}

---

삭제

효율성 면에서 삭제는 삽입과 매우 유사하다. 연결 리스트 앞에서 노드를 삭제하려면 한 단계면 가능하다. 이와 달리 배열은 첫 번째 원소를 삭제하면 나머지 데이터를 모두 한 셀씩 왼쪽으로 시프트 해야 하므로 효율성이 O(N)이다.

 

삭제를 구현해 보자.

	void delete_at_index(int index)
	{
		CNode* node = firstNode;
		int node_index = 0;

		while (node_index < index - 1)
		{
			node = node->nextNode;
			node_index++;
		}

		if (index == 0)
		{
			firstNode = node->nextNode;
			delete node;
		}
		else
		{
			CNode* delNode = node->nextNode;
			node->nextNode = node->nextNode->nextNode;
			delete delNode;
		}
	}

검색과 삽입, 삭제는 차이가 거의 없는 듯 보인다. 하지만 연결 리스트는 그 나름의 강점이 있다.

 

연결 리스트가 빛을 발하는 경우는 한 리스트를 검사해서 많은 원소를 삭제할 때다. 배열에서는 삭제할 때마다 빈 공간을 메꾸기 위해 나머지 데이터를 왼쪽으로 시프트 해야 하는 또 다른 O(N) 단계가 필요하지만 연결 리스트에서는 리스트 전체를 살펴보면서 삭제가 필요하면 그저 그 노드의 링크가 적절한 노드를 가리키도록 바꾸면 되므로 각 삭제마다 딱 한 단계가 걸린다. 

---

전체 코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;

class CNode
{
public:
	CNode(string _data) { data = _data; }

	string data;
	CNode* nextNode;
};

class CLinkedList
{
public:
	CLinkedList(CNode* first) { firstNode = first; }

	CNode* firstNode;

	string read(int index)
	{
		CNode* node = firstNode;
		int node_index = 0;

		while (node_index < index)
		{
			node = node->nextNode;
			node_index++;
			
			if (node == nullptr)
				return nullptr;
		}
		return node->data;
	}

	int index_of(string value)
	{
		CNode* node = firstNode;
		int node_index = 0;

		do {
			if (node->data == value)
				return node_index;

			node = node->nextNode;
			node_index++;
		} while (node != nullptr);
		return -1;
	}

	void insert_at_index(int index, string value)
	{
		CNode* node = firstNode;
		int node_index = 0;

		while (node_index < index - 1)
		{
			node = node->nextNode;
			node_index++;
		}

		CNode* newNode = new CNode(value);
		if (index == 0)
		{
			firstNode = newNode;
			newNode->nextNode = node;
		}
		else
		{
			newNode->nextNode = node->nextNode;
			node->nextNode = newNode;
		}
	}

	void delete_at_index(int index)
	{
		CNode* node = firstNode;
		int node_index = 0;

		while (node_index < index - 1)
		{
			node = node->nextNode;
			node_index++;
		}

		if (index == 0)
		{
			firstNode = node->nextNode;
			delete node;
		}
		else
		{
			CNode* delNode = node->nextNode;
			node->nextNode = node->nextNode->nextNode;
			delete delNode;
		}
	}
};

int main()
{
	CNode* node_1 = new CNode("once");
	CNode* node_2 = new CNode("upon");
	node_1->nextNode = node_2;
	CNode* node_3 = new CNode("a");
	node_2->nextNode = node_3;
	CNode* node_4 = new CNode("time");
	node_3->nextNode = node_4;

	CLinkedList* list = new CLinkedList(node_1);

	//cout << list->read(3) << endl;
	//cout << list->index_of("time") << endl;
	//list->insert_at_index(4, "insert");
	list->delete_at_index(1);
	cout << list->read(0) << endl;
	cout << list->read(1) << endl;
	cout << list->read(2) << endl;
	//cout << list->read(3) << endl;
	//cout << list->read(4) << endl;

	return 0;
}