[자료구조] 2. 선형 구조 - 리스트

리스트란?

data의 명단으로서 배열 또는 linked list에 저장하는 것이다. 배열은 저번 포스팅에서 다뤘으니 이번엔 Linked List에 대해 알아보겠다. Linked List의 종류는 다음 두가지로 나눌 수 있다.

• Singly Linked List (SLL)
• Doubly Linked List (DLL)

이 둘은 다음 노드를 포인터로 연결해 데이터를 관리한다.

 

C++ 은 STL에 list가 구현되어 있어 직접 구현하지 않고 간편하게 사용할 수 있다.

#include <list>
using namespace std;

int main()
{
	list<int> List1; //비어있는 int형 List
	list<double> List2; //비어있는 double형 List
}

 

Linked List의 구성요소는 다음과 같다.

• 노드 : Linked List의 기본 단위로서, 데이터와 다음 노드를 가리키는 포인터를 가지고 있다.
• 포인터 : 다음 노드 및 이전 노드의 정보를 가지고 있다.
• 헤드 : 가장 처음 위치하는 노드를 가리킨다.
• 테일 : 가장 마지막에 위치하는 노드를 가리킨다.

 

Singly Linked List(SLL)

SLL의 노드는 데이터와 다음 노드를 가리킬 포인터를 가지고 있다.

struct Node
{
	DataType Data;
	Node* Next;
}

 

SLL의 상태는 Node* Head 포인터가 NULL이라면 비어있는 리스트, NULL이 아니라면 비어있지 않은 리스트로 판단한다.

 

검색 (search)

검색 알고리즘은 선형검색으로 O(n)의 시간 복잡도를 가진다.

Node* P = Head;
while(P != NULL)
{
	if(P->data = key) Found Key
	P = P->Next;
}
-> Not Found Key

 

(*) 참고

• 선형검색 (linear search) → O(n)
  • data가 순차적 공간에 있거나 정렬이 안되어 있을 때
• 이진 검색 (binary search) → O(logN)
  • 배열 등의 RAM에 sorting 되어 저장 돼 있을 때

 

삽입 (insert)

삽입 알고리즘은 단순 포인터의 연결만 바꿔주면 되기 때문에 O(1)의 시간 복잡도를 가진다.

 

i) 맨 앞에 삽입할 때 (현재 삽입할 노드는 P)

1. P->Next = Head
2. Head = P

 

ii) 중간 / 끝에 삽입할 때 (Q 노드 다음에 삽입할 때)

1. P->Next = Q->Next
2. Q->Next = P

 

삭제 (delete)

삭제 알고리즘 또한 포인터의 연결만 바꿔주면 되기 때문에 O(1)의 시간 복잡도를 가진다.

if(P == Head) Head = P->Next //맨 앞의 노드를 삭제할 때
else Q->Next = P->Next //Q노드 다음 P노드를 삭제할 때

 

실제 C++ 코드로 구현해보면 다음과 같다.

template<typename T>
class SingleLinkedList
{
public:
	SingleLinkedList() : Head(nullptr), Tail(nullptr), Length(0) {}

	SingleLinkedList& Append(T Data)	//삽입
	{
		Node* NewNode = new Node(Data);
		if (!Head)
		{
			Head = Tail = NewNode;
			Length++;
			return *this;
		}
		else
		{
			Tail->Next = NewNode;
			Tail = NewNode;
		}
		Length++;
		return *this;
	}

	SingleLinkedList& Remove(T Data)	//삭제
	{
		Node* Current = Head;
		if (Search(Data))
		{
			while (Current->Next->Data != Data)
			{
				Current = Current->Next;
			}
			Node* Temp = Current->Next;
			Current->Next = Current->Next->Next;
			
			delete Temp;
			Length--;
			return *this;
		}
		return *this;
	}

	bool Search(T Data)		//검색
	{
		Node* Current = Head;
		if (Head->Data == Data) return true;

		while (Current->Next)
		{
			Current = Current->Next;
			if (Current->Data == Data) return true;
		}
		return false;
	}

	void Print()
	{
		Node* Current = Head;
		while (Current)
		{
			std::cout << Current->Data << " ";
			Current = Current->Next;
		}
	}

	int Size() { return Length; }

private:
	struct Node
	{
		T Data;
		Node* Next;

		Node(T Data) : Data(Data), Next(nullptr) {}
	};

	int Length;
	Node* Head;
	Node* Tail;
};

 

 

Doubly Linked List (DLL)

DLL의 노드는 데이터와 이전 노드와 다음 노드를 가리킬 포인터를 가지고 있다.

struct Node
{
	DataType Data;
	Node* Next;
	Node* Prev; //이전 노드를 가리키는 포인
}

 

DLL의 상태는 Node* Head 포인터가 NULL이라면 비어있는 리스트, NULL이 아니라면 비어있지 않은 리스트로 판단한다.

 

검색 (search)

SLL과 동일하다.

 

삽입 (insert)

삽입 알고리즘의 시간 복잡도는 O(1)로 SLL과 동일하지만 포인터를 바꾸는 작업이 조금 더 복잡하다.

 

i) 맨 앞에 삽입할 때 (현재 삽입할 노드는 P)

1. P->Next = Head
2. if(Head != NULL) Head->Prev = P
3. Head = P
4. P->Prev = NULL

 

ii) 중간 / 끝에 삽입할 때 (Q 노드 다음에 삽입할 때)

1. P->Next = Q->Next;
2. P->Prev = Q
3. if(Q->Next != NULL) Q->Next->Prev = P
4. Q->Next = P

 

삭제 (delete)

삭제 알고리즘 또한 시간 복잡도는 O(1) 이지만 포인터를 바꾸는 작업이 조금 더 복잡하다.

1. if(P->Next != NULL) P->Next->Prev = P->Prev //P가 첫번째 원소가 아니라면
2. if(P->Prev != NULL) P->Prev->Next = P->Next //1번과 똑같은 논리
3. else Head = P->Next //P가 첫번째 원소라면 Head 변경

 

 

실제 C++ 코드로 구현해보면 다음과 같다.

template<typename T>
class DoubleLinkedList
{
public:
	DoubleLinkedList() : Head(nullptr), Tail(nullptr), Length(0) {}

	DoubleLinkedList& Append(T Data)
	{
		Node* NewNode = new Node(Data);
		
		if (!Head)
		{
			Head = Tail = NewNode;
		}
		else
		{
			Tail->Next = NewNode;
			NewNode->Prev = Tail;
			Tail = NewNode;
		}
		Length++;
		return *this;
	}

	DoubleLinkedList& Remove(T Data)
	{
		Node* Current = Head;
		if (Search(Data))
		{
			while (Current->Next->Data != Data)
			{
				Current = Current->Next;
			}

			Node* Temp = Current->Next;
			Current->Next->Next->Prev = Current;
			Current->Next = Current->Next->Next;

			delete Temp;
			Length--;
			return *this;
		}
		return *this;
	}

	bool Search(T Data) //검색
	{
		Node* Current = Head;
		if (Current->Data == Data) return true;

		while (Current->Next)
		{
			Current = Current->Next;
			if (Current->Data == Data) return true;
		}
		return false;
	}

	void Print()
	{
		Node* Current = Head;
		while (Current)
		{
			std::cout << Current->Data << " ";
			Current = Current->Next;
		}
	}

	int Size() { return Length; }

private:
	struct Node
	{
		T Data;
		Node* Next;
		Node* Prev;

		Node(T Data) : Data(Data), Next(nullptr), Prev(nullptr) {}
	};

	Node* Head;
	Node* Tail;
	int Length;
};

 

 

이 밖에도 Circular List (원형 리스트)와 널 포인터를 없애 삽입/삭제가 더 간단해지는 Circular DLL with Structural Head 가 있다.

 

 

링크드 리스트의 시간복잡도

• 검색 : O(n)
• 삽입 : O(1)
• 삭제 : O(1)