Doubly Linked List
每個節點同時記錄前一個（prev）與後一個（next）節點，可雙向走訪。
struct Node {
int val;
struct Node *prev;
struct Node *next;
};
特性
- 可從任一節點往前或往後走訪。
- 已知節點指標時，插入與刪除皆為 O(1)（不需從頭找前驅節點；single linked list 刪除需先找到 prev）。
- 每個節點多存一個指標，記憶體開銷較大。
- 常搭配 dummy head/tail（哨兵節點） 簡化邊界處理，避免 NULL 判斷。
與 array 比較
| Doubly linked list | Array | |
|---|---|---|
隨機存取 a[i] | O(n) | O(1) |
| 已知位置插入/刪除 | O(1) | O(n)（需搬移元素） |
| 記憶體 | 額外 prev/next 指標、不連續 | 連續、cache friendly |
| 大小 | 動態成長 | 固定或需 realloc |
- 適合頻繁在中間插入刪除、且不需隨機存取的場景（如 LRU cache、deque）。