10. Elementary Data Structures

10.1. Stacks and queues

스택과 큐는 미리 정해진 DELETE 연산에 의해 원소가 삭제될 수 있는 동적 집합이다. 스택에서는 가장 마지막으로 삽입된 원소가 삭제되는 후입선출(LIFO) 방식을 따르며 에서는 가장 최초에 삽입된 원소가 삭제되는 선입선출(FIFO) 방식을 따른다. 구현은 여러 방식으로 할 수 있다.

Stacks

종종 스택에서의 INSERT 연산은 PUSH, DELETE 연산은 POP으로 불린다. 최대 크기 n인 스택 S는 길이 n인 배열 S을 이용해 구현할 수 있는데, S.top은 가장 최근에 삽입된 원소의 인덱스이고 S[1, …, S.top]이 스택이 된다. S.top = 0이면 스택이 것이며 STACK-EMPTY로 이를 테스트한다. 빈 스택에서 POP을 하면 스택에서 언더플로우 에러가 난다. S.top이 n을 넘어가면 스택에서 오버플로우 에러가 난다. 이들은 다음과 같이 구현할 수 있다.

STACK-EMPTY(S)
return S.top == 0
PUSH(S, x)
S.top += 1
S[S.top] = x
POP(S)
if STACK-EMPTY(S)
    error "underflow"
else
    S.top -= 1
    return S[S.top + 1]

Queues

종종 큐에서의 INSERT 연산은 ENQUEUE, DELETE 연산은 DEQUEUE로 불린다. 큐에는 머리꼬리가 존재하며 원소가 삽입될 때에는 꼬리 뒤에 삽입되고 원소가 제거될 때에는 머리에 있는 원소가 제거된다. 최대 크기 n – 1인 큐 Q는 길이 n인 배열 Q를 통해 구현될 수 있다. Q.head는 머리의 인덱스이고 Q.tail은 새 원소가 삽입될 위치의 인덱스이다. 원소들은 Q.head부터 Q.tail – 1까지 순환하면서 배치된다. Q.head = Q.tail이면 큐는 빈 것이며 최초에는 Q.head = Q.tail = 1이다. 빈 큐에서 원소를 제거하려 하면 언더플로우가 일어난다. Q.head = Q.tail + 1 이거나 Q.head = 1 and Q.tail = Q.length이면 큐는 꽉 찬 것이며 꽉 찬 큐에 원소를 추가하려 하면 오버플로우가 일어난다. 이는 다음과 같이 구현할 수 있다.

ENQUEUE(Q, x)
Q[Q.tail] = x
if Q.tail == Q.length
    Q.tail = 1
else
    Q.tail += 1
DEQUEUE(Q)
x = Q[Q.head]
if Q.head == Q.length
    Q.head = 1
else
    Q.head += 1
return x

10.2. Linked lists

연결 리스트는 선형으로 오브젝트가 나열된 자료 구조이다. 인덱스로 원소의 선형 순서를 판정하는 배열과는 달리 연결 리스트의 순서는 각 오브젝트의 포인터에 의해 판정된다. 연결 리스트는 동적 집합에 대해 단순하고 유연한 구현을 제공한다.

양방향 연결 리스트의 원소는 key 오브젝트와, 다음 항목을 가리키는 next 포인터, 이전 항목을 가리키는 prev 포인터로 이루어져 있다. x.prev = NIL이면 앞 원소가 없는 머리이다. x.next = NIL이면 뒤 원소가 없는 꼬리이다. L.head = NIL이면 리스트 L은 빈 리스트이다.

단방향 연결 리스트의 경우 prev가 없다.

정렬된 리스트의 경우 원소의 순서가 키의 순서와 같다. 정렬되지 않은 리스트라면 그렇지 않다.

원형 리스트에서는 머리의 prev 포인터는 꼬리를 가리키고, 꼬리의 next 포인터는 머리를 가리킨다.

이 절에서의 리스트는 정렬되지 않은 이중 연결 리스트라고 가정한다.

Searching a linked list

LIST-SEARCH(L, k)는 리스트 L에서 키 k를 갖는 첫 번째 원소를 선형 탐색해 해당 원소로의 포인터를 반환한다. 그런 원소가 없다면 NIL을 반환한다.

LIST-SEARCH(L, k)
x = L.head
while x ≠ NIL and x.key ≠ k
    x = x.next
return x

n개 오브젝트의 리스트에서 LIST-SEARCH의 최악 시간 복잡도는 \Theta(n)이다.

Inserting into a linked list

key가 세팅된 원소 x를 LIST-INSERT로 머리에 삽입할 수 있다. 수행 시간은 O(1)이다.

LIST-INSERT(L, x)
x.next = L.head
if L.head ≠ NIL
    L.head.prev = x
L.head = x
x.prev = NIL

Deleting from a linked list

LIST-DELETE는 연결 리스트 L에서 원소 x를 삭제한다. 단, 특정 키를 갖는 원소를 삭제하려면 LIST-SEARCH로 먼저 해당 원소를 검색해야 한다. 수행 시간은 O(1)이지만, 특정 키를 갖는 원소를 삭제하려면 최악의 경우 \Theta(n)이 된다.

LIST-DELETE(L, x)
if x.prev ≠ NIL
    x.prev.next = x.next
else
    L.head = x.next
if x.next ≠ NIL
    x.next.prev = x.prev

Sentinels

리스트에서 삭제하는 함수는 경계 조건을 무시하면 다음과 같이 간단해진다.

LIST-DELETE'(L, x)
x.prev.next = x.next
x.next.prev = x.prev

감시자는 경계 조건을 단순화시키기 위한 더미 오브젝트로 일반 이중 연결 리스트에 감시자를 추가하면 감시자가 있는 원형 이중 연결 리스트가 되며 이 때 감시자는 머리와 꼬리 사이에 위치한다. L.nil로 나타내어지는 감시자는 L.nil.next는 머리가 되고 L.nil.prev는 꼬리가 된다. 그러므로 L.head와 L.tail도 따로 지정할 필요 없다. 이 때 검색 함수는 다음과 같아진다.

LIST-SEARCH'(L, k)
x = L.nil.next
while x ≠ L.nil and x.key ≠ k
    x = x.next
return x

삽입 함수는 다음과 같다.

LIST-INSERT'(L, x)
x.next = L.nil.next
L.nil.next.prev = x
L.nil.next = x
x.prev = L.nil

감시자가 자료 구조 연산의 점근적 시간 상한을 줄이는 일은 거의 없지만 연산을 상수배만큼 줄이는 것은 가능하다. 필요없는 체크들이 없어지기 때문인데, 사실 이것보다는 코드의 명료함을 통한 이득이 더 크다. 작은 리스트가 여럿 있으면 감시자가 각각 들어가므로 메모리 낭비가 커진다.

10.3. Implementing pointers and objects

포인터와 오브젝트를 따로 지원하지 않는 언어에서 그들을 어떻게 구현할까? 이 절에서는 연결 리스트를 포인터 없이 구현하는 법을 알아본다.

A multiple-array representation of objects

어떠한 특성들을 공유하는 오브젝트의 모임은 각각의 특성을 배열로 표현해 구현할 수 있다. 예를 들어 이중 연결 리스트는 배열 3개 key, prev, next로 구현할 수 있다. NIL은 배열의 인덱스가 될 수 없는 상수로 구현하고, 리스트를 나타내는 변수 L은 리스트의 머리의 인덱스를 저장한다.

A single-array representation of objects

컴퓨터 메모리에서의 단어는 적당한 정수 M에 대해 0부터 M – 1까지의 정수로 나타내어진다. 많은 프로그래밍 언어에서 오브젝트는 연속된 컴퓨터 메모리를 차지하며 포인터는 그 오브젝트가 차지하는 첫 번째 메모리 주소이다. 다른 오브젝트의 위치는 포인터에 오프셋을 더해 가져올 수 있다. 비슷한 방식으로 포인터 타입이 없는 언어에서도 단일 배열을 이용해 이를 구현할 수 있다. 이 구현 방식은 같은 배열 내에서 서로 다른 길이를 가진 오브젝트들을 같이 저장할 수 있다는 장점이 있다.

Allocating and freeing objects

양방향 연결 리스트에 키를 삽입하려면 사용되지 않은 오브젝트에 포인터를 할당해야 하므로, 할당되지 않은 오브젝트들의 저장소를 관리하는 쓰레기 수집기는 때때로 유용하다.

다배열 표현에서의 배열들이 각각 길이 m이고 동적 집합이 n \leq m개의 원소를 갖고 있다고 하자. 그러면 m – n개의 오브젝트는 가용 상태가 되어 할당 가능해진다. 이 가용 오브젝트들 가용 리스트라 불리는 단방향 연결 리스트 내에서 관리하자. 가용 리스트는 next 배열만 사용하고, 이는 리스트 내 next 포인터를 저장한다. 이 리스트의 머리는 전역 변수 free에 저장된다. 연결 리스트 L로 표현되는 동적 집합이 비어 있지 않으면 이 가용 리스트는 원본 리스트 L과 쌍둥이 관계를 이룰 수 있다. 이 때 각 오브젝트는 L 안에 있거나 가용 리스트 안에 있지만 두 리스트 내에 동시에 존재할 수는 없다.

가용 리스트는 스택처럼 동작한다: 할당되는 다음 오브젝트는 마지막으로 해제된 오브젝트이다. 이는 스택과 비슷하게 구현할 수 있다.

ALLOCATE-OBJECT()
if free == NIL
    error "out of space"
else
    x = free
    free = x.next
    return x
FREE-OBJECT(x)
x.next = free
free = x

가용 리스트는 최초에는 비할당된 오브젝트 n개 전부를 들고 있다. 가용 리스트가 전부 소모되면 ALLOCATE-OBJECT 호출은 에러가 난다. 이 때 하나의 가용 리스트를 여러 개의 연결 리스트에 대한 가용 리스트로 사용하는 것도 가능하다. 이 할당, 해제 작업은 O(1)의 수행 시간을 가진다. 오브젝트의 특성 중 next처럼 동작하는 것만 있다면 임의의 동일한 구조의 오브젝트 집합에 대해 확장 가능하다.

10.4. Representing rooted trees

앞 절에서 리스트의 표현법은 동일한 구조의 오브젝트들에 대한 자료 구조로 확장 가능하다. 이 절에서는 루트가 있는 트리들 연결 리스트로 표현하는 법을 알아보도록 한다.

Binary trees

이진 트리의 각 노드 내 오브젝트의 특성 p, left, right는 부모, 왼쪽 자식, 오른쪽 자식을 나타내게 할 수 있다. x.p = NIL이면 x는 루트이다. x에 왼쪽 자식이 없으면 x.left = NIL이 된다. x에 오른쪽 자식이 없으면 x.right = NIL이 된다. 트리의 루트는 T.root로 나타낼 수 있다. T.root = NIL이면 그것은 빈 트리이다.

Rooted trees with unbounded branching

위 방법은 left와 right를 child_1, …, child_k로 대체해 k-진 트리로 확장할 수 있다. 노드의 자식 수에 상한이 없다면 이 방법은 불가능하다. 또한, 상한은 크지만 대부분의 노드의 자식 수는 적다면 많은 메모리를 낭비하게 될 것이다.

더 나은 방법은 왼쪽-자식, 오른쪽-형제 표현으로서 임의의 노드가 n개인 루트가 있는 트리에 대해서 O(n)의 공간만을 사용한다. 모든 노드는 부모 포인터 p를 갖고 트리 T는 루트 T.root를 갖지만, 자식 노드에 대한 포인터를 가지는 대신에 가장 왼쪽 자식에 대한 포인터 x.left-child와 오른쪽 형제에 대한 포인터 x.right-sibling만을 갖는다. 자식이 없으면 x.left-child = NIL이다. 해당 노드가 부모 노드의 가장 오른쪽 자식이면 x.right-sibling = NIL이다.

Other tree representations

루트 있는 트리는 다른 방식으로 표현할 수도 있다. 완전 이진 트리인 힙은 단일 배열과 힙의 마지막 노드의 인덱스로 표현할 수 있다. 자식 노드 없이 부모 노드만 가지고도 표현할 수 있다. 최적의 표현은 구현에 달려 있다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중