[CLSR] 10.2 Linked lists (Ch.10 Elementary Data Structures)

x = L.head
while x ≠ NIL and x.key ≠ ㅏ
	x = x.next
return x

연결 리스트는 객체를 선형 순서로 배열한 자료 구조이다.

배열과 달리 연결 리스트는 각 객체의 포인터를 통해 결정된다.

 

'doubly linked list' $L$은 'key'와 포인터 변수인 'next'와 'prev'를 특성(attribute)으로 갖는 객체들을 원소로 갖는다.

'singly linked list'인 경우 'prev'포인터가 존재하지 않는다.

리스트의 요소 $x$에 대해 $x.prev$는 $x$ 직전 원소를 가리키고 $x.next$는 $x$ 다음 요소를 가리킨다.

$x.prev = NIL$인 경우 $x$는 직후의 요소가 없으므로 마지막 요소이다. 이를 'tail'로 부른다.

$L.head$는 리스트의 첫번째 요소를 가리키며 $L.head = NIL$인 경우 배열이 비었다고 한다.

doubly linked list의 예시 (CLRS p.237)

---

Searching a linked list

'$List-Search(L, K)$'는 리스트 $L$에서 $k$값의 key를 갖는 첫번째 원소를 찾아서 해당 요소의 포인터를 반환한다. 만약 탐색에 실패하면 NIL을 반환한다. 수도코드는 다음과 같다.

x = L.head
while x ≠ NIL and x.key ≠ k
	x = x.next
return x

n개의 오브젝트가 있는 리스트를 탐색할 때 최악의 경우 $\Theta(n)$이 소요된다.

---

Inserting into a linked list

key가 이미 정해진 요소 $x$를 리스트의 맨 앞에 넣는 것은 $List-Insert$를 통해 할 수 있다. 수도코드는 다음과 같다.

x.next = L.head
if L.head ≠ NIL
	L.head.prev = x
L.head = x
x.prev = NIL

$n$개 요소의 리스트에서 $List-Insert$의 실행시간은 $O(1)$이다.

---

Deleting from a linked list

$List-Delete$는 리스트 $L$의 요소 $x$를 가리키는 포인터를 받으면 $x$를 리스트에서 분리시킨다. 만약 특정 key의 원소를 찾고 싶은 것이라면 먼저 $List-Search$를 통해 요소의 포인터를 찾아야 한다.

$List-Delete$의 수도코드는 다음과 같다.

if x.prev ≠ NIL
	x.prev.next = x.next
else L.head = x.next
if x.next ≠ NIL
	x.next.prev = x.prev

$List-Delete$자체로는 $O(1)$이 소요되지만 특정 key의 요소를 제거하기 위해서 $List-Search$를 호출하면 최악의 경우에 $\Theta(n)$이 소요된다.

---

Sentinels(보초법)

$List-Delete$에서 경계 조건을 없애면 코드가 다음과 같이 더 간단해질 수 있다.

x.prev.next = x.next
x.next.prev = x.prev

sentinel은 이를 실현시키기 위한 더미 오브젝트이다.

$L.nil$이라는 더미를 만들고 $L.nil.next$는 리스트의 head를 가리키도록, $L.nil.prev$는 tail을 가리키도록 하고, head의 prev는 $L.nil$을, tail의 next는 $L.nil$을 가리키도록 하면 된다.

$L.nil$자체가 head를 가리키고 있으므로 $L.head$라는 attribute를 없애고 $L.nil.next$를 찾으면 된다.

 

$List-Search$에 대한 코드는 이전과 비슷하지만 $NIL$과 $L.head$에 대한 부분만 조금 바꾸면 된다.

x = L.nil.next
while x ≠ L.nil and x.key ≠ k
	x = x.next
return x

 

$List-Insert$는 다음과 같다.

x.next = L.nil.nxet
L.nil.next.prev = x
L.nil.next = x
x.prev = L.nil

점근적으로 보초법이 줄여주는 time bounds는 거의 없다. 하지만 상수항의 요소는 줄여줄 수 있다. 반복문에서 보초법을 사용하는 것은 보통 속도보다는 코드의 명확성 때문이다. 연결 리스트 코드에서 코드는 더 단순해지지만 $List-Insert$와 $List-Delete$에서 줄어드는 시간은 $O(1)$뿐이다. 그래도 다른 상황에서는 반복문의 코드를 더 단순하게 만들어서 $n$ 또는 $n^2$만큼의 실행 시간을 줄여준다.

따라서 보초법은 잘 생각해서 써야 된다. 작은 리스트가 많이 있는 경우 보초법을 사용해서 추가적으로 사용하게 되는 메모리가 클 수 있다.