Linked List 是面試必考、實務少用、但觀念影響深遠的資料結構。
改指標很快，跳格子很慢
Linked List 的插入刪除只需要改指標，O(1) 搞定。代價是你沒辦法直接跳到第 i 個節點——得從頭走過去。跟 Array 比起來，它們的優缺點幾乎完全相反。
指標串起來的節點
每個節點存兩樣東西：資料本身，和指向下一個節點的指標。
head
↓
[10|→] → [20|→] → [30|→] → [40|→] → null記憶體不連續，散落各處，靠指標串起來。這和 Array 的「一排連續格子」完全不同。
節點本身其實就這麼點東西：
class Node {
int data; // 資料
Node next; // 指向下一個節點
}一個值加一根指標。整條串列就是一堆這種節點你牽我、我牽你串起來的——沒有起始位址、沒有 index 算式，想找第 i 個只能順著 next 一路走。這也解釋了為什麼下面這張操作表長那個樣子：
| 操作 | 時間 | 為什麼 |
|---|---|---|
get(i) | O(n) | 從 head 一格一格走到第 i 個 |
addFirst | O(1) | 改 head 指標就好 |
addLast | O(n) | 得先走到尾巴 |
removeFirst | O(1) | 改 head 指標 |
removeLast | O(n) | 單向串列走不回去，得走到倒數第二個 |
注意 addLast / removeLast 都是 O(n)——這正是下面雙向串列要解的痛點。
Array vs Linked List：一張表說完
| Array | Linked List | |
|---|---|---|
| 記憶體 | 連續 | 分散 |
| 隨機存取 | O(1) | O(n) 從頭走 |
| 頭部插入 | O(n) 搬移 | O(1) 改指標 |
| 中間插入 | O(n) 搬移 | O(1) 改指標（但走到那裡要 O(n)） |
| cache 友善度 | 極高 | 極低 |
最後一點很關鍵：現代 CPU 的 cache 機制偏愛連續記憶體。Linked List 的節點散落各處，每次走一步就可能 cache miss。這就是為什麼理論上 Linked List 在某些操作比較快，但實際跑起來 Array 常常贏——cache 效應太強了。
插入只改兩個指標
在 index 1 插入 15：
原本: [10] → [20] → [30]
Step 1: 新節點指向 [20]
[15] → [20]
Step 2: [10] 改指向 [15]
[10] → [15] → [20] → [30]不用搬任何資料，只改兩個指標。這是 Linked List 最大的賣點。
刪除同理——把前一個節點跳過被刪的，指向下一個就好。被跳過的節點沒人引用，GC 會處理。
🎬 互動視覺化：鏈結串列指標操作動畫 — 一步步看插入、刪除時指標怎麼重接，比看十張靜態圖更懂「為什麼只改兩個指標就好」。
雙向鏈結串列：多花一點記憶體，換回便利
單向鏈結串列有個痛點：你只能往前走，不能往回。想刪最後一個節點？你得從頭走到倒數第二個。
雙向鏈結串列每個節點多存一個 prev 指標：
null ← [10] ⇄ [20] ⇄ [30] → nullremoveLast 從 O(n) 變成 O(1)。Java 的 LinkedList 就是雙向實作。
環狀鏈結串列：尾巴接頭
[10] → [20] → [30] → [10] → ...（繞圈）經典應用是 Round-Robin 排程——任務一個接一個輪流執行，跑完最後一個回到第一個。
老實說，什麼時候真的會用？
在大多數業務場景，你不太會直接用 Linked List。Array（動態陣列）在實務上幾乎全面碾壓。
但 Linked List 的觀念無處不在：
- LRU Cache 用雙向鏈結串列維護使用順序
- 作業系統的 process scheduling
- React Fiber 的工作單元就是一種鏈表結構
- Git 的 commit history 本質上也是
所以與其說「學 Linked List 要拿來用」，不如說「理解指標操作」本身就是程式設計的基本功。面試官考你 reverse linked list 不是在刁難你，是在看你會不會操作指標。好吧，也有一點在刁難你。
Linked List 就像手動排檔——你不會每天開，但懂了它你才真的理解變速箱怎麼運作的。