[ Open Data Structures ] - Singly Linked List - 1

  Array가 아닌 Pointer를 기반으로 list interface를 공부해 보도록 합시다. 여기서 구조는 List Item을 포함하는 노드[Node]로 이루어져 있습니다. 포인터를 이용한 이 노드들은 일련의 연속적인 연결체로서 존재하게 됩니다. 우리는 먼저 FILO Interface ( Stack )와 Queue Operation들을 상수 시간 내에 해결해주는  Singly Linked List ( 以下SLL )를 공부하고 Deque Operation들을 상수 시간 내에 해결해주는 Doubly Linked List에 대해서 공부하기로 합니다.

SLL은 Array-Based List Interface와 비교해서 확연한 장단점이 존재합니다. 가장 눈에 띄는 단점은 상수 시간 내에 임의의 자료에 접근하는 Set과 Get의 기능을 잃게 된다는 점입니다. 우리는 SLL에서 임의의 자료에 접근하기 위해서는 순차적으로 모든 노드들을 검토해야만 합니다. 장점이라고 하면 Array-Based에 비해서 Dynamic ( 動的 )하다는 점이 있습니다. 자료를 저장하고 있는 List 내의 임의의 노드 u가 주어졌을 때, 이 노드를 제거하거나 인접한 노드에 자료를 추가하는 작업을 상수 시간 내에 처리할 수 있게 됩니다. 이는 노드 u가 일련의 노드 연속 SLL 내의 어디에 위치하든 참입니다.

 

Singly Linked List ( SLL )

 

 Singly linked list는 node들의 연속이라고 할 수 있다. 각 노드 ( Node u )들은 어떤 정보 ( u.x ) 와 다음 node로 이어지는 Reference(혹은 Pointer, u->next )를 가지고 있다. List의 마지막에 위치한 node는 다음 node에 대한 Reference로 null값 ( u->next = nullptr )을 가지고 있다.

효율성을 위해서 SLL는 첫 번째와 마지막 노드를 추적하는 방법으로 Head와 Tail 노드를 사용하는 방법을 채택했다. 또한, 노드의 개수를 추적하는 정수 n을 사용하기로 한다. 

여기서 주의할 점이 있는데 Node Class의 Destructor를 만들 때, next를 깨버리는 구현 ( delete[] next라든가 )하게 되면 모든 SLL의 구조가 깨지게 된다는 점이다. 다음은 SLList의 Stack과 Queue의 add와 deletion을 간단히 설명한 그림이다.

기능이 많고 정신없어 보이기는 하지만 { Add(x), Remove() } 는 Queue(), { Push(y), Pop() }은 Stack의 작업에 해당한다. Add와 Push가 각각 tail, head에 추가된다는 점을 확인하면 Remove와 pop이 어째서 head를 잘라내는지 이해할 수 있다.

* Queue는 FIFO을 사용하는 자료구조.

** Stack은 FILO을 사용하는 자료구조.

*** Deque(Double Ended Queue)는 Head와 Tail에서 모두 Insertion이 가능하며 Random Access기능을 제공한다. 따라서 지금까지  Add라든가 Delete작업에서 Random Access기능을 제공한 이유는 List를 이용하여 Stack, Queue, Deque를 모두 구현하기 위함이다.

 

Stack : Push Operation

 

SLList는 Head부분에 자료의 추가와 삭제를 실현함으로써 Push()와 Pop()을 구현할 수 있다. Push는 간단하게 새롭게 추가할 Node u에 자료 x를 담고 u.next Pointer를 기존 Head에 이어주면 된다. node의 개수를 추적하는 n을 1추가해주는 것도 잊지 않는다.

 

Stack : Pop Operation

 

Sequence, 즉 Node를 이어붙인 어떤 구조의 크기가 0이 아니라는 것을 검증하고 나서 Head를 Head->next를 가리키게 만들고 n--을 수행한다. 주의해야할 점은 pop을 수행할 때 n이 1이면 tail을 nullptr로 이어주는 것이다.

Push와 Pop작업은 O(1) 이내에 해결된다.

 

Queue : Remove Operation

 

SLList가 위에서 본 것처럼 Stack을 위한 기능을 제공할 수 있었던 것처럼 Queue를 구현할 수 있으며 Add(x)와 Remove()도 상수 시간 내에서 해결이 가능하다.

Code Dupulication이라고 해도 무방할 정도로 같은 기능, 방법, 성능이다. Stack의 Add와 다르게 Add는 tail에서 작업한다는 점을 고려하며 Add를 구현한다.

 

Queue : Add Operation

 

대부분의 경우에 Add는 tail->next에 새로운 node u를 연결하는 것으로 수행된다. 하지만 n=0인 특수한 경우(즉, head=tail=nulltpr)를 고려해야 하는데 이 경우에 Add를 수행하면 tail=head=u다.

Theorem

Singly Linked List는 이렇게 Stack(FILO)과 Queue(FIFO)의 Interface를 구성할 수 있다. Add, Remove, Push, Pop은 모두 O(1)의 Running time을 가진다.

SLList는 Deque작업의 거의 모든 것을 구현할 수 있다. Tail에서 자료를 제거하는 작업만이 유일하게 누락된 기능이다. Tail에서부터 SLList의 Sequence를 제거해 나가는 것은 까다롭다. 왜냐하면 Tail이 삭제되면 Tail에 선행하는 Node w의 next의 정보를 갱신해야하는데 w에 접근할 수 있는 방법은 head부터 시작해서 n - 2번 순차적으로 접근하는 수밖에는 없기 때문이다.

HiddenWriter/LinkedList at SinglyLinkedList (github.com)