doubly linked list는 singly linked list와 어떻게 다른가요?

Question

Accepted Answer

**doubly linked list(이중 연결 리스트)**는 각 노드에 **두 개**의 포인터(`next` *와* `prev`)를 주어, **양방향**으로 순회할 수 있고, 이미 참조를 가지고 있는 노드를 O(1)에 삭제할 수 있게 합니다(선행자를 찾기 위해 head에서부터 걸어갈 필요가 없음). ## 구조 ```text null <- [10] <-> [20] <-> [30] -> null 양방향으로 prev/next 링크 ``` ## 알려진 노드의 O(1) 삭제 ```python class Node: def __init__(self, val): self.val, self.prev, self.next = val, None, None def remove(node): # O(1) — 순회 불필요 if node.prev: node.prev.next = node.next if node.next: node.next.prev = node.prev ``` *singly* linked list에서는 노드를 삭제하려면 먼저 그 선행자를 찾아야 하므로 → **O(n)**. ## 비교 | 측면 | Singly | Doubly | |---|---|---| | 노드당 포인터 | 1개 (next) | 2개 (next, prev) | | 역방향 순회 | 불가 | 가능 | | 알려진 노드 삭제 | O(n) | **O(1)** | | 메모리 오버헤드 | 낮음 | 높음 | ## 언제 사용할까 - **Doubly:** LRU cache, 브라우저 기록, undo/redo, 중간에서 O(1) 제거가 필요한 모든 구조. - **Singly:** 메모리가 빠듯하고 앞으로만 이동할 때. ## 왜 중요한가 알려진 노드를 O(1)에 splice 해내는 능력은 doubly linked list가 **LRU cache**에서 hash map의 파트너가 되는 핵심 속성입니다. 추가된 `prev` 포인터는 메모리를 양방향 이동과 상수 시간 삭제의 유연성과 맞바꿉니다.

측면	Singly	Doubly
노드당 포인터	1개 (next)	2개 (next, prev)
역방향 순회	불가	가능
알려진 노드 삭제	O(n)	O(1)
메모리 오버헤드	낮음	높음