🎯 什麼情境該想到我
當你「以為需要 插入刪除」的時候。
★ 這一頁最重要的結論是反直覺的：現代硬體上，鏈結串列幾乎總是錯的選擇。
教科書上 插入的優勢，在真實 CPU 上大多被快取失誤吃光。
⚙️ 怎麼用（機制與現代觀點）
結構
單向： [a|•]──▶[b|•]──▶[c|nil]
雙向： nil◀─[•|a|•]⇄[•|b|•]⇄[•|c|•]─▶nil
| 操作 | 陣列／slice | 鏈結串列 |
|---|---|---|
隨機存取 a[i] | ||
| 在「已知節點」處插入／刪除 | （要搬移） | |
| 找到那個節點 | — | ← ★ 常被忽略 |
| 記憶體配置 | 一整塊 | 每個節點一次 |
| 快取局部性 | 極好 | 極差 |
★ 為什麼「 插入」是個陷阱
「在中間插入是 」的前提是「你已經握有那個節點的指標」。
如果你只知道「第 個」或「值等於 的那個」，光是找到它就要 ——
而這 的走訪，每一步都是一次可能的 cache miss。
陣列的 搬移 vs 鏈結串列的 走訪，在真實硬體上差很多：
陣列搬移 ：memmove，連續記憶體，CPU 預取器完全命中
→ 實際上快到接近 O(1) 的常數
鏈結走訪 ：每個 next 指標都可能指向記憶體的任意位置
→ ★ 每一步都可能是一次 cache miss（~100 個 cycle）
結果：在幾千個元素以內，陣列的「 插入」實測常常比鏈結串列的「 查找 + 插入」更快。
★ 這是「漸進複雜度會騙人」的第二個經典案例（第一個見 插入排序）。
面試時能講出「快取局部性」這一層，比背出複雜度表有價值得多。
★ 那它什麼時候是對的
| 場景 | 為什麼鏈結串列勝出 |
|---|---|
| ★ LRU 快取 | 雜湊表 + 雙向鏈結串列：hash 給 定位，鏈結串列給 移到頭部。 ★ 關鍵是「已經握有節點指標」（從 hash 拿到），所以真的是 （見 雜湊表） |
| 侵入式鏈表（intrusive） | 節點指標內嵌在物件本身，不需要額外配置。Go runtime、Linux 核心大量使用 |
| 雜湊表的碰撞鏈 | 每條鏈通常只有幾個元素，走訪成本可忽略 |
| 無鎖資料結構 | CAS 改一個指標就完成插入，不需要搬移整塊記憶體 |
| 合併排序 | 鏈結串列上可做到 額外空間的 排序（只改指標） |
| 不能移動的元素 | 元素被外部持有指標時，陣列擴容會讓指標失效 |
LRU 的骨架（最值得記住的應用）
type entry struct {
key, val int
prev, next *entry // ★ 雙向：刪除時需要 prev
}
type LRU struct {
cap int
m map[int]*entry // key → 節點，給 O(1) 定位
head, tail *entry // 哨兵節點，省掉一堆 nil 判斷
}
func (c *LRU) Get(key int) (int, bool) {
e, ok := c.m[key]
if !ok { return 0, false }
c.moveToFront(e) // ★ O(1)：因為我們已經握有 e 的指標
return e.val, true
}★ 用哨兵（sentinel）頭尾節點可以消除幾乎所有的 nil 檢查——這是鏈結串列實作最實用的技巧。
常考的操作
| 題目 | 關鍵技巧 |
|---|---|
| 反轉 | 三個指標 prev, cur, next 逐步翻轉 |
| 找中點 | 快慢指標：快的走兩步、慢的走一步 |
| 偵測環 | Floyd 龜兔賽跑：快慢指標若相遇則有環；再從頭與相遇點同步走可找到環的入口 |
| 合併兩個有序串列 | 哨兵節點 + 雙指標（就是 合併排序 的 merge） |
| 刪除倒數第 k 個 | 雙指標間隔 |
🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
- ★ Go 裡不要用
container/list。每個節點獨立配置、快取不友善、沒有泛型（存any要型別斷言）、GC 壓力大。
要堆疊佇列用 slice 或 channel（見 堆疊與佇列）；真的需要鏈結語義就自己定義 struct（可以用泛型且能內嵌）。 - ★ 預設用 slice。除非你能明確指出「為什麼這裡陣列不行」，否則 slice 幾乎總是更好。
- 每個節點一次配置 → 大量小物件對 GC 是負擔。侵入式設計可以避免。
- 無法二分搜尋（需要隨機存取，見 二分搜尋）。
- 刪除單向串列的節點需要前驅，所以要嘛用雙向、要嘛走訪時記著 prev。
- 並行修改極難寫對。多執行緒的鏈結串列（尤其無鎖版本）是公認難寫的——優先用 channel 或有鎖的 slice。