LinkedList
-
[ Open Data Structures ] - DoublyLinkedList - 2DataStructure 2021. 4. 14. 22:31
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는 ..