LeetCode Cycle 05：Linked List 的面試重點與 DOM / LRU 連結
Linked List 在演算法面試永遠在問 dummy head、反轉、cycle 偵測這三件事，但前端面試的加分題是「DOM tree 的 sibling 串就是 doubly linked list」「LRU cache 為什麼一定要 doubly linked list + hash」這類連結。內部使用。
寫前端寫到第七年都還沒有真的「自己宣告一個 linked list」過——所有的列表結構不是 array 就是 Map。但 senior 面試一定會考 linked list，理由不是要你會手寫，是要你知道「指標操作」這條心智模型——因為 DOM 樹的 sibling navigation 就是 linked list[^1]、React Fiber 內部也是 linked list、瀏覽器 LRU cache 跟 React Query 的 query cache 都是 doubly linked list + hash map 的組合。Cycle 05 的題型本質是「在不能用 array index 的世界裡，你怎麼操作元素」。
Linked list 的底層心智模型
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
跟 array 的差別：
| 操作 | Array | Singly Linked List |
|---|---|---|
隨機存取 arr[k] | O(1) | O(k)，要從 head 走 |
| 開頭插入 / 刪除 | O(n) | O(1) |
| 中間插入 / 刪除（已有指標） | O(n) | O(1) |
| 中間插入 / 刪除（沒有指標） | O(n) | O(n) |
| 找特定 value | O(n) | O(n) |
同樣是「中間插入/刪除」，為什麼會分出 O(1) 跟 O(n) 兩種結果？把成本拆成「找到節點」跟「改指標」兩段就一目了然：
| 前提 | 找到節點 | 改指標 | 總成本 |
|---|---|---|---|
| 已有指標 | O(1)，reference 已經在手 | O(1) | O(1) |
| 沒有指標（只給第 k 個位置） | O(k)，最差 O(n)，要從 head 走 k 步 | O(1) | O(n) |
關鍵在「改指標」永遠是 O(1)——差別全出在「找到節點」那一欄。
表格裡的 「已有指標」 指你手上已經拿到「要操作位置的那個節點」的 reference——例如 callback 把節點傳給你、或剛 traverse 到那一格。在這個前提下，刪除/插入就只是改 node.next = X 一行，所以是 O(1)。
如果沒有指標——只給「第 k 個位置」這種抽象描述——必須先從 head 一步一步走 k 步找到節點，這段是 O(k)，最差 O(n)，整個中間操作就退化成 O(n)，跟 array 一樣。所以 linked list 的 O(1) 不是免費的，要先付出「能取得指標」的代價。
這個前提解釋了後面 §LRU Cache 為什麼一定要 doubly linked list + hash map 的組合：hash map 用 key 直接 O(1) 拿到節點 reference，doubly linked list 才有條件 O(1) 把節點移到 head、從 tail 移除。少了 hash map，光找節點就 O(n)，再快的 list 操作也救不回來。