[자료구조] 연결 리스트 (Linked List)

[자료구조] 연결 리스트 (Linked List)

---

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이며 선형자료구조에 속한다. 종류는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등이 있으며 자료의 추가/삭제에 대해 시간 복잡도 O(1)를 갖는다. 하지만 O(N)의 시간이 걸리는 특수한 경우도 존재한다.

일반적으로 리스트의 맨 앞 노드를 헤드(Head), 맨 뒤 노드를 테일(Tail)이라고 부른다. 

단일 연결 리스트 (Singly Linked List)

단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고 각 노드의 포인터는 다음 노드를 가리킨다.

즉, 단일 연결 리스트는 한 방향으로만 연결이 되어있으며 연결된 다음 노드는 알 수 있지만 내 이전 노드는 알 수 없다.

소스코드 구현 (C++)

#include <iostream>

using namespace std;

struct Node {
	int Data;
	Node* Next = NULL;
};

class LinkedList
{
public:
	LinkedList() { 
		Head = NULL;
		Tail = NULL;
		Size = 0;
	}
	~LinkedList() { }

	void Insert(Node* node) {
		if (Head == NULL)
		{
			Head = node;
			Tail = node;
			Size++;
		}
		else
		{
			Node* cNode = Head;
			while (cNode)
			{
				if (cNode->Next == NULL)
				{
					cNode->Next = node;
					Tail = cNode->Next;
					Size++;
					break;
				}
				cNode = cNode->Next;
			}
		}
	}
	void Delete(int index) {
		if (Size - 1 < index) return;
		//Case Head
		if (index == 0)
		{
			Node* temp = Head->Next;
			delete Head;
			Head = temp;
			Size--;
		}
		else
		{
			Node* cNode = Head;
			Node* Prev = NULL;
			Node* Next = NULL;
			for (int i = 0; i < index; i++)
			{
				Prev = cNode;
				cNode = cNode->Next;
				Next = cNode->Next;
			}
			if (cNode == Tail)
			{
				delete cNode;
				Tail = Prev;
				Tail->Next = NULL;
				Size--;
			}
			else
			{
				delete cNode;
				Prev->Next = Next;
				Size--;
			}
		}
	}

	int Search(Node* data) {
		Node* cNode = Head;
		int Count = 0;
		while (cNode)
		{
			if (cNode == data)
			{
				return Count;
			}
			cNode = cNode->Next;
			Count++;
		}
		return -1;
	}

	int GetSize() { return Size; }

	void PrintAll() {
		if (Size == 0) std::cout << "List is empty!!" << std::endl;
		else
		{
			std::cout << "Head[" << Head->Data << "],Tial[" << Tail->Data << "], Size[" << GetSize() << "] [";
			Node* head = Head;
			while (head)
			{
				std::cout << head->Data;
				if (head->Next != NULL)
				{
					std::cout << " - ";
				}
				head = head->Next;
			}
			std::cout << "]" << std::endl;
		}
	}
public:
	Node* Head;
	Node* Tail;
	int Size;
};

int main()
{
	LinkedList list;
	
	for (int i = 0; i < 10; i++)
	{
		Node* n = new Node();
		n->Data = i;
		list.Insert(n);
	}

	list.PrintAll();

	list.Delete(9);
	list.PrintAll();
	
	list.Delete(4);
	list.PrintAll();

	list.Delete(0);
	list.PrintAll();

	return 0;
}

출력 결과

---

연결 리스트 중에서 단일 연결 리스트를 알아보았다. 삭제를 하는 과정에서 이전 데이터로 돌아갈 수 없기 때문에 미리 이전 데이터를 저장해주는 과정이 필요했다.