[ Open DataStructures ] - Doubly Linked List - 1

Doubly Linked List(以下DLList)는 Singly Linked List와 유사한 형태이다. 차이점이라고 하면 SLList는 Node u가 존재할 때, u->next에 해당하는 정보만을 가지고 있으나 DLList는 Node u에 선행하는 Node w를 가리키는 Pointer혹은 Refernce (u->prev)를 가지고 있다는 점이다.

 

Doubly Linked List

 

SLList를 구현함에 있어서 특별히 주의를 기울여야만 했던 요소들이 있었다. 가령 List끝(tail)의 정보를 제거하는 경우나 크기가 0인(n=0)경우에 Add 작업을 수행하는 경우가 있다. DLList는 이렇게 주의를 기울여야 하는 요소가 더욱 늘어난다. 다양한 상황에 적합하게 대응할 수 있는 방법 중 하나가 Dummy Node를 도입하는 방법이다. 이 Node는 의미있는 정보를 가진 Node가 아니고 Place Holder( 대충 자리만 차지한다는 뜻 )의 역할을 한다. Head( 가장 선행하는 Node )보다 선행하며 dummy->next 호출 시 Head가 반환된다. 같은 맥락으로 Tail에 따라붙으며 tail->next호출 시 dummy가 반환된다.

이 방법으로 DLList를 하나의 원형 형태로 이해할 수 있다.

 

Finding node

 

DLList에서 특정한 index의 Node에 접근하는 것은 어렵지 않다. Head에서 시작해서 정방향으로 탐색하거나(dummy->next) Tail에서 시작할 수 있다(dummy->prev). 이러한 방법은 i번째 node에 이르기까지 O(1 + min{i, n - i})의 Running time을 보장해준다.

Get(index), Set(index, data)

 

Node가 가진 정보에 접근하는 Get이나 index에 위치한 정보를 변경하기 위한 함수도 어렵지 않게 작성할 수 있다. 단순히 GetNode를 호출한 뒤, 원하는 작업을 해주면 된다.

이전 Interface에 대해 정리했던 것처럼 Set은 변경 전 정보를 반환하도록 했다.

 

Adding and Removing

 

만약 DLList 상의 어떤 Node w에 대한 Reference를 가지고 있고 w의 Prev에 node u를 추가하고 싶다면 단순히 u->next = w / u->prev = w->prev 그리고 u->prev->next와 u->next->prev를 손봐주면 된다. Dummy Node 덕분에 prev와 next가 없는 경우는 고려하지 않아도 된다.

가장 먼저 삽입되는 Node의 정보를 정리하고 w ( 직관적으로 우측 Node )를 정리한 후에 마지막으로 가장 좌측의 Node의 연결을 정리한다.

이제, List Operation인 Add(_i, _x)가 자명해진다. DLList 내부에서 i번째 Node를 찾고 정보x를 갖는 새로운 Node u를 그 앞에 삽입한다.

Add 작업에서는 오직 GetNode를 사용해서 i번째 Node를 찾는 과정만이 Non-constant한 부분이다. 따라서 Add는 O(1 + min{i, n - i})의 Running time을 가진다.

어떤 Node w를 제거하는 작업은 Dummy Node의 존재로 훨씬 간결하게 해결을 할 수 있다. w의 next와 prev의 pointer만 조정해서 w를 넘기도록 만들면 된다.

이렇게 되면 어떤 index i를 가진 node를 제거하는 일도 어렵지 않다. i번째 node를 찾고 Remove(node)를 호출하면 된다.

Add와 똑같이 오직 i번째 node를 찾는 과정만이 Non-constant이기 때문에 Remove 역시 O(1 + min{i, n-i})의 Running time을 요구한다.

 

HiddenWriter/LinkedList at DoublyLinkedList (github.com)