鏈結串列的定義#

鏈結串列不需要連續的記憶體空間，通過「指標」將一組零散的記憶體塊串聯起來使用。

基本結構：

• 結點（Node）：記憶體塊
• 後繼指標（next）：指向下一個結點的地址
• 頭節點（head）：第一個結點，記錄鏈結串列基地址
• 尾結點（tail）：最後一個結點，next 指向 NULL

常見鏈結串列結構#

flowchart TB
    subgraph 單鏈結串列["單鏈結串列"]
        direction LR
        H1[Head] --> A1[A] --> B1[B] --> C1[C] --> N1[NULL]
    end

    subgraph 雙向鏈結串列["雙向鏈結串列"]
        direction LR
        N2[NULL] <--> A2[A] <--> B2[B] <--> C2[C] <--> N3[NULL]
    end

    subgraph 迴圈鏈結串列["迴圈鏈結串列"]
        direction LR
        A3[A] --> B3[B] --> C3[C] --> A3
    end

單鏈結串列#

每個結點只有一個 next 指標，指向下一個結點。

迴圈鏈結串列#

尾結點的 next 指向頭節點，形成環狀結構。適合處理環型結構資料，如約瑟夫問題。

雙向鏈結串列#

每個結點有兩個指標：

• next：指向下一個結點
• prev：指向前一個結點

雖然佔用更多記憶體，但支援雙向走訪，在某些場景下更高效。

鏈結串列 vs 陣列#

*鏈結串列插入/刪除為 O(1) 的前提是：已經找到操作位置。如果需要先查找，則還要加上 O(n) 的查找時間。

雙向鏈結串列的優勢#

場景一：刪除給定指標指向的結點

• 單鏈結串列：需要從頭走訪找前驅結點 → O(n)
• 雙向鏈結串列：直接取 prev 指標 → O(1)

場景二：在指定結點前插入

• 單鏈結串列：O(n)
• 雙向鏈結串列：O(1)

場景三：有序鏈結串列的按值查詢

可以記錄上次查找位置 p，根據目標值與 p 的大小關係決定往前或往後查找，平均只需查找一半資料。

設計思想：空間換時間。雙向鏈結串列用額外的記憶體空間（prev 指標）換取操作效率的提升。這是一個重要的設計原則：

• 記憶體充足 → 空間換時間
• 記憶體緊缺 → 時間換空間

LRU 快取實現#

問題： 如何用鏈結串列實現 LRU（Least Recently Used）快取淘汰策略？

策略：

• FIFO：先進先出
• LFU：最少使用
• LRU：最近最少使用

實現思路：

維護一個有序單鏈結串列，越靠近尾部的結點是越早存取的。

當有新資料被存取時：

flowchart TD
    A[存取資料] --> B{資料在快取中?}
    B -->|是| C[移動到頭部]
    B -->|否| D{快取已滿?}
    D -->|否| E[插入頭部]
    D -->|是| F[刪除尾結點]
    F --> E

    style C fill:#e8f5e9
    style E fill:#e3f2fd
    style F fill:#ffebee

1. 資料已在鏈結串列中 → 移到頭部
2. 資料不在鏈結串列中：
   • 快取未滿 → 插入頭部
   • 快取已滿 → 刪除尾結點，插入頭部

時間複雜度： O(n)（需要走訪查找）

引入雜湊表記錄每個資料的位置，將存取時間複雜度降到 O(1)。這就是「雜湊表 + 雙向鏈結串列」的 LRU 實現方式。

鏈結串列程式碼技巧#

技巧一：理解指標的含義#

p->next = q;  // p 的 next 指標存儲 q 的記憶體地址
p->next = p->next->next;  // p 的 next 指向 p 的下下個結點

技巧二：警惕指標丟失和記憶體洩漏#

錯誤示範：

p->next = x;           // p 的 next 已經指向 x
x->next = p->next;     // 相當於 x->next = x，鏈結串列斷裂！

正確順序：

x->next = p->next;     // 先讓 x 指向下一個結點
p->next = x;           // 再讓 p 指向 x

刪除結點時，C 語言需要手動釋放記憶體，否則會記憶體洩漏。

技巧三：利用哨兵簡化邊界處理#

插入第一個結點和刪除最後一個結點需要特殊處理，很容易出錯。

解決方案： 使用帶頭鏈結串列（哨兵結點）。

哨兵結點不存儲資料，head 始終指向它，統一了所有操作的邏輯。

技巧四：邊界條件檢查#

寫完程式碼後，用以下邊界條件測試：

• 鏈結串列為空
• 鏈結串列只有一個結點
• 鏈結串列只有兩個結點
• 處理頭節點和尾結點

技巧五：畫圖輔助思考#

複雜的鏈結串列操作容易把自己繞暈。畫出操作前後的鏈結串列變化，對照著寫程式碼會清晰很多。

技巧六：多寫多練#

常見的鏈結串列操作必須能熟練手寫：

1. 單鏈結串列反轉
2. 鏈結串列中環的檢測
3. 兩個有序鏈結串列合併
4. 刪除鏈結串列倒數第 n 個結點
5. 求鏈結串列的中間結點

寫鏈結串列程式碼最考驗邏輯思維能力。指標操作、邊界處理稍有不慎就會出 Bug。這也是面試官喜歡考鏈結串列的原因。

小結#