[ Open Data Structures ] - DoublyLinkedList - 2

Summary

다음과 같은 Theorem이 Doubly Linked List의 성질 혹은 Perfomance를 정리한다.

Theorem. DLList는 List Interface를 구현할 수 있다. 이 Implementation에서 Add, Remove, Set, Get은 모두 O(1 + min{i, n - i})의 Running time을 갖는다.

DLList에서 GetNode의 시간복잡도를 무시한다면 모든 작업이 상수시간 내에 해결된다는 것을 주목할 필요가 있다. 즉, 오직 특정 Node를 찾는 작업만이 시간을 많이 잡아먹고 한 번 Node를 잡으면 어떤 작업도 상수시간 내에 해결할 수 있다. 이것이 Array-Based List와 가장 큰 차이를 나타내는 지점이다. Array-Based List는 특정 정보를 찾는데엔 상수시간이 필요했지만 Add나 Remove에서 Non-Constant했다. 

이러한 이유로 Linked list structures는 외부적인 방법으로 Node를 찾아낼 수 있는 Applications에 적합하다. 예를 들면, 각 node에 대한 pointer를 USet에 저장해 두는 방법이 있다. 그렇게 하면 정보 x를 삭제하는 경우 USet에서 정보 x를 갖고 있는 Node를 찾아 상수시간내에 작업을 완료할 수 있게 된다.