[DS] Linked List

2021. 6. 21. 22:14

1. Linked List 정의

Linked List란, [그림1]과 같이 특정 데이터를 연속적으로 연결하여 저장하는 자료구조를 말한다. 데이터를 나열한다는 점에서 배열과 비슷하지만 연속된 주소공간에 데이터를 저장하여 인덱싱으로 한번에 데이터를 검색할 수 있는 배열과 달리, Linked List는 연속되지 않은 주소공간에 데어터를 그때그때 생성하고 또 여기에 접근할 수 있도록 이전 데이터 주소공간과 연결하는 특징을 가진다. 따라서 배열과 같이 인덱싱으로 데이터 공간에 바로 접근은 못하지만 메모리를 조금 더 효율적으로 사용할 수 있다는 장점이 있다.

Linked List와 Node

Linked List는 위와 같이 데이터 블럭들이 서로 연결된 형태의 자료구조인데, 이러한 데이터 블럭을 보통 Node라고 부르며 크게 저장하고자 하는 Data와 다음 Node와의 연결을 위한 주소공간으로 구성되어 있다.

2. Linked List 연산

Linked List 삽입

Linked List에 새로운 Node를 삽입할때는 물론 중간에도 삽입할 수 있지만 보통은 [그림3]과 같이 Linked List의 맨 앞 또는 맨 뒤에 삽입하게 된다. 이 경우 맨 앞쪽 Node나 맨 뒤쪽 Node의 주소값을 알고 있다면 바로 삽입이 가능하기에 시간복잡도는 O(1)이 된다.

Linked List 검색

Linked List는 인덱스 값을 가지지 않기에 특정 값을 가진 Node를 검색하기 위해서는 앞이나 뒤에서 순차적으로 검색해야 한다. 따라서 시간복잡도는 O(N)이 된다.

Linked List 삭제

Node의 주소값을 알고 있다면 바로 삭제가 가능하므로 시간복잡도는 O(1)이 된다. 하지만 삭제할 Node의 주소값을 모른다면 검색 후 삭제해야하기에 시간복잡도는 검색연산과 같이 O(N)이 된다.

또한 Single Linked List에서 [그림4]와 같이 Linked List의 중간 Node를 삭제해야한다면 이전 Node와 다음 Node를 잘 연결시켜주고 삭제되어야하기에 삭제시 삭제할 Node주소값 뿐만 아니라 이전 Node의 주소값도 알고 있어야 한다.

3. Linked List 추가 구현 사항

Head & Tail Node

Linked List의 첫번째 Node를 보통 Head Node라고 부르고 마지막 노드를 Tail Node라고 부른다. Linked List의 시작과 끝을 나타내기에 둘중 하나는 반드시 알고 있어야 전방삽입, 후방삽입, 순차탐색등이 가능하다. [그림5]에서 보이는 Head, Tail은 각각 첫번째 Node와 마지막 Node에 접근하기 위한 주소값을 가지는 Pointer를 의미한다.

Dummy Node

의미없는 Data값을 가지는 Node를 Dummy Node라고 부른다. 보통 Node삽입, 검색, 삭제 코드를 단순하고 일관적이게 작성하기 위해 Linked List의 맨 앞이나 맨 뒤에 넣는다.

① Dummy Node가 없을때,
Head가 NULL을 가리키냐 아니냐에 따라 Node의 삽입, 검색, 삭제 방법이 다르게 된다. 즉, 첫 노드가 추가 되기 전과 후의 분기문을 코드내에 작성해야하기에 일관적이지 않고 복잡해진다.

[그림6] Dummy Node가 없을때, 초기 리스트 상태와 첫노드 삽입후 리스트 상태

② Dummy Node가 있을때,
Head는 무조건 Dummy Node를 가리키며 첫 노드가 추가 되었든 안되었든 Node의 삽입, 검색, 삭제가 모두 Dummy Node 다음 Node부터 이뤄지면 되어 코드가 일관적이고 단순해진다.

[그림7] Dummy Node가 있을때, 초기 리스트 상태와 첫노드 삽입후 리스트 상태

4. Linked List 종류

Single Linked List

가장 기본이 되는 Linked List 형태이다.

※ 아래에 소개할 다른 Linked List의 장점과 단점은 Single Linked List와 비교했을때의 장단점을 설명한 것이다.

[그림8] Single Linked List, Dummy Node와 Tail Node Pointer가 구현되지 않은 경우

[그림9] Single Linked List, Dummy Node와 Tail Node Pointer가 구현된 경우

Double Linked List

한쪽방향으로만 연결이 되어 있는게 아니라 반대방향으로도 연결이 되어 있다.

▶ 장점 : 순차탐색시 반대방향으로도 탐색이 가능하다, 삭제시 *이전 노드의 주소를 알 필요가 없다.

▶ 단점 : 메모리공간을 추가된 주소값 저장공간 만큼 더 사용한다.

*단방향 Linked List라면 삭제할 노드가 Head나 Tail이 아닌이상 삭제할 Node의 이전 Node 주소값도 알고 있어야 이전 Node와 이후 Node를 연결시킨뒤 삭제할 수 있다. ([그림4]와 Linked List 삭제 참고)

Circular Linked List

[그림11]와 같이 Head와 Tail이 연결되어 있어 순환하는 링크드 리스트를 말한다.

▶ 장점 : Tail하나만으로 Head접근이 바로 가능하므로 Tail하나만 있어도 전방, 후방 삽입이 가능하다.

아래는 [그림11]의 Circular Linked List에 data4값을 가진 Node를 전방과 후방에 각각 삽입한 결과를 보여준다. 그림에서 알수 있듯 전방삽입과 후방삽입은 모두 *동일한 순서로 순환하지만 단지 Tail이 가리키는 Node가 다를 뿐이다.

*[그림12], [그림13] 모두 data1->data2->data3->data4->(다시)data1-> ... 순으로 순환한다.

Double Circular Linked List

위에서 설명한 Double Linked List와 Circular Linked List를 합친 Linked List로 두 Linked List의 장점과 단점을 합친 특징을 지닌다. 단점에비해 장점의 효율성이 좋아 내가 생각하기에 위에 설명한 모든 Linked List종류 중 가장 유용하게 사용할 수 있는 Linked List가 아닐까 생각한다.

▶ 장점 : 순차탐색시 반대방향으로도 탐색이 가능하다, 삭제시 이전 노드의 주소를 알 필요가 없다.

Head하나만으로 Tail접근이 바로 가능하므로 Head하나만 있어도 전방, 후방 삽입이 가능하다.