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

가변형 배열에 대하여

연결 리스트는 자료구조를 공부할 때 가장 먼저 나오는 자료구조이다.

이 리스트라는 이름에서 유추 가능한 것처럼 목록 형태로 이루어진 데이터 형식을 의미한다.

 

왜 연결 리스트를 사용하는가?

데이터가 고정되어 있다면, 즉 수가 정해져 있다면  = 당연히 배열을 사용하면 된다.

예를 들어 이 맵에 라이트가 4개 정도 배치될 것이다 라고 한다면 Light light[4]; 처럼 사용하면 된다.

혹은 array<Light> light(4) 같은 식으로 말이다.

 

그러나 일반적인 배열로는 IEnumerator를 다룰 수 없다. 무슨 소리냐면, 배열이 늘었다, 줄었다 하는 상황을 컨트롤 할 수 없다는 것이다. 수가 한정된 상황이라면 제어가 가능할 수도 있지만, 대부분의 상황은 그런식으로 흘러가지 않는다.

 

따라서 가변형 배열을 사용하게 된다. Vector처럼 말이다.

이 벡터는 가변형 배열의 대표적인 예시이다.

#include <vector>

int clip;

cin >> clip;

vector<int> N(clip);

 

벡터는 다음처럼 선언하게 된다. int형 변수 N의 크기를 clip의 크기로 만들겠다는 의미이다. 중요한 것은 기존의 배열의 경우 크기가 정해져 있어야만 선언이 가능했었던 반면, 벡터를 사용하게 되면 런타임 도중 크기를 선언해도 만들 수 있다는 것이다.

 

벡터 함수는 어느 순간 크기가 가득차게 되면 용량을 늘리고 데이터를 이동시키게 된다. 그런데 이때 기존 공간은 그대로 남아있게 된다. 대충 채워넣고 늘리고를 반복하다보면 어느 순간 공간이 애매하게 살짝씩 남게 된다. 그 공간을 단편화라고 하는데, 바로 이 이유 때문에 벡터는 삽입과 삭제가 빈번한 상황에서는 별로 좋지 않다.

---

단순 연결 리스트

이제 한번 그 잘났다는 리스트에 대해서 알아보자. 우선 가장 간단한 단방향 연결 리스트, 일명 SLL(Single Linked List)에 대해서 한번 알아보자.

 

우선 리스트는 노드라고 불리는 구조체를 쭉 연결해서 만든 구조이다.

struct Node
{
	Datatype Data;
	Node* NextNode;
}

노드는 다음과 같이 생겼다. 데이터를 보관하는 필드와 다음 노드를 가리키는 포인터.

 

너무 지엽적인 내용을 제외하고 설명하자면, 새로운 노드를 선언하고 노드의 데이터는 입력이 들어온 데이터를 대입해주고, 포인터 부분이 Null을 가리키도록 설정해주는 Create()메서드, 선택한 노드를 삭제하고 노드가 가리키는 값을 Null처리해주는 Destroy() 메서드, 선택한 노드의 사이에 새로운 노드를 끼워넣는 Insert()등의 노드가 있다.

 

이런 식의 구조가 바로 단순 연결 리스트의 예시이다.

 

노드의 탐색은 맨 처음 헤드 노드부터 해당하는 값이 나올 때까지 그 다음 노드, 그 다음 노드... 같은 방식으로 작동하게 된다.

 

노드의 추가와 삭제는 과연 어떻게 이루어질까?

 

먼저 추가의 경우, 끼워넣을 노드(이전 노드, 다음 노드라고 지칭하겠음) 사이에 들어갈 노드를 연결해야 한다.

1. 들어갈 노드의 노드 연결 부분에 다음 노드의 주소를 대입한다.

2. 이전 노드와 다음 노드간의 연결을 끊어준다.

3. 이전 노드와 들어갈 노드를 연결해준다.

 

삭제는 그렇다면 어떻게..?

1. 다음 노드와 그 다음 노드사이의 연결을 끊기 전에 이전 노드와 다다음 노드를 연결해준다.

2. 다음 노드와 다다음 노드사이의 연결을 끊어준다.