Linked List

List ADT

List 를 구현하기 위한 자료구조는 Linked List 혹은 Array 로 구현된다. 이번 포스트에서는 Linked List 에 대해서 다룬다.

구조

LinkedList 는 메모리에 연속적이지 않은 데이터를 다루기 위한 자료구조이다.(기본 개념)

Linked List 의 Vertex 는 item(아이템) 과 next(Pointer, 주소) 로 구성된다. next는 다음 번째의 vertex 를 가리키는 값이다.

Linked List 의 변형(추가)

Linked List 를 구현하는 방법에 따라서 모습이 조금씩 달라진다.

• 가장 앞, 가장 뒤의 Vertex 를 가리키는 포인터를 갖는 Linked List
• circular(순환) 하는 Linked List
• 가장 앞에 dummy 값이 Linked List
• 데이터의 중복을 허용하지 않는 Linked List

연산

Get(i)

특정 index 번째에 위치한 값 혹은 Vertex를 반환하는 연산은 O(N) 의 시간 복잡도를 지닌다. Array 와 비교했을 때 느린 연산이다(Array은 O(1) 시간복잡도를 갖는다).

Vertex* Get(int i) { // returns the vertex
  Vertex* ptr = head; // we have to start from head
  for (int k = 0; k < i; ++k) // advance forward i time(s)
    ptr = ptr->next; // the pointers are pointing to the higher index
  return ptr;
}

Search(v)

특정 값을 찾아서 반환하는 연산은 최악의 경우 마지막 인덱스까지 순회하면서 찾아야 하므로 O(N)의 시간복잡도를 지닌다. Array도 이 연산에 대해서는 O(N) 시간복잡도를 갖는다.

Insertion

Linked List 에 값을 삽입하는 연산의 경우 4 가지 경우가 존재한다.

1. 헤드 앞에 삽입
이 경우는 새로 생성한 Vertex 의 next 포인터를 기존 hea를 참조하게 하고 head 값을 새로 생성한 Vertex로 바꿔야 한다. 

Vertex* vtx = new Vertex(); // create new vertex vtx from item v 
vtx->item = v; 
vtx->next = head; // link this new vertex to the (old) head vertex 
head = vtx; // the new vertex becomes the new head

 

2. 빈 리스트에 삽입
이 경우 LinkedList의 head와 tail 이 새로 생성된 Vertex 를 참조하게 한다.

 

3. Linked List 중간에 삽입
해당 (인덱스-1)에 위치한 Vertex 를 찾고 그 Vertex 의 next가 가리키는 Vertex를 새로 생성한 Vertex 의 next가 참조하게 하고 (인덱스-1)에 위치한 Vertex 의 vertex 는 새로 생성된 Vertex 를 참조하게 한다. 이 연산의 경우 시간 복잡도는 Get(i) 연산 영향을 받을므로 최악의 경우 시간복잡도는 O(N) 을 갖는다.

Vertex* pre = Get(i-1); // traverse to (i-1)-th vertex, O(N)
aft = pre->next; // aft cannot be null, think about it
Vertex* vtx = new Vertex(); // create new vertex
vtx->item = v;
vtx->next = aft; // link this
pre->next = vtx; // and this

 

4. Tail 뒤에 삽입
기존 Tail 이 가리키던 Vertex 의 next 값을 새로 생성한 Vertex 를 참조하게 한다.

Vertex* vtx = new Vertex(); // this is also a C++ code
vtx->item = v; // create new vertex vtx from item v
tail->next = vtx; // just link this, as tail is the i = (N-1)-th item
tail = vtx; // now update the tail pointer

Remove

Linked List 에서 Remove 하는 연산은 세 가지 경우를 갖는다.

1. 헤드에 있는 Vertex 제거
기존 head 가 가리키는 Vertex 의 next 가 참조하는 Vertex를 head 포인터가 참조하게 한다.

if (head == NULL) return; // avoid crashing when SLL is empty
Vertex* tmp = head; // so we can delete it later
head = head->next; // book keeping, update the head pointer
delete tmp; // which is the old head

 

2.Linked List 중간에 위치한 Vertex 제거
(인덱스-1) 위치한 Vertex 를 찾곡 해당 Vertex의 next 가 삭제하는 대상의 next 가 가리키는 Vertex 를 참조하게 바꾼다.

Vertex* pre = Get(i-1); // traverse to (i-1)-th vertex, O(N)
Vertex* del = pre->next, aft = del->next;
pre->next = aft; // bypass del
delete del;

 

3. 꼬리에 위치한 Vertex 제거
꼬리 전에 위치한 Vertex 를 찾고 해당 Vertex 의 next 를 null 한다.이 연산의 경우 꼬리가 가리키는 이전의 Vertex 를 찾아야 하므로 O(N)의 시간복잡도를 갖는다.

Vertex* pre = head;
tmp = head->next;
while (tmp->next != null) // while my neighbor is not the tail
  pre = pre->next, tmp = tmp->next;
pre->next = null;
delete tmp; // tmp = (old) tail
tail = pre; // update tail pointer

 

Linked List 사용하는 경우

Linked List 보다 resizable array(vector)을 사용하는 것이 이점이 많다. 하지만, Linked List을 이용해 구현한 Stack 혹은 Queue를 많이 사용하기 때문에 Linked List 의 특징과 연산을 알고 있어야 한다. 

 

 

Doubly Linked List(DLL)

이중 연결 리스트(Doubly Linked List, 일명 DLL) 은 기본 연결 리스트(Linked List)에 이전을 가리키는 포인터 하나가 추가된 자료구조이다. Vertex 의 포인터로 next 만 있는 것이 아니라 이전 Vertex 를 가리키는 prev 도 존재한다.

 

포인터 관련 메모리 사용 공간이 2배로 늘어난다는 단점이 있지만 끝 근처에 위치한 Vertex 접근 시 성능 상에 이점이 존재한다.

특히, tail 포인터를 이용하여 끝의 Vertex를 삭제하는 연산에서 기존 Linked List 는 이전 Vertex 를 참조하는 방법이 없어 전체를 탐색했어야 했는데 DLL 의 경우 마지막 Vertex 의 prev 포인터를 이용하여 이전 Vertex 에 바로 접근할 수 있어 전체를 탐색할 필요가 없어지게 된다.

Vertex* tmp = tail; // remember tail item
tail = tail->prev; // the key step to achieve O(1) performance :O
tail->next = null; // remove this dangling reference
delete tmp; // remove the old tail