視覺化概覽
graph LR HEAD["head"] --> N1 N1["data: 10 | next"] --> N2["data: 20 | next"] --> N3["data: 30 | next"] --> N4["data: 40 | next"] --> NULL["null"] style HEAD fill:#fff,stroke:#333,stroke-dasharray: 5 5 style NULL fill:#fff,stroke:#333,stroke-dasharray: 5 5
💡 白話版：Linked List 就像尋寶遊戲的線索條。每個線索告訴你下一個在哪裡，但你不能直接跳到第五個，必須從第一個開始走。
什麼是鏈結串列？
鏈結串列是一串用指標串起來的節點，每個節點包含資料和指向下一個節點的指標。
head
↓
[10] -> [20] -> [30] -> [40] -> null
Array vs Linked List
| 比較 | Array | Linked List |
|---|---|---|
| 記憶體 | 連續空間 | 分散各處 |
| 大小 | 固定（需擴容） | 動態增減 |
| 隨機存取 | O(1) 直接跳 | O(n) 要從頭走 |
| 頭部插入 | O(n) 要搬移 | O(1) 改指標 |
| 中間插入 | O(n) 要搬移 | O(n) 走到位置 + O(1) 改指標 |
節點結構
class Node {
int data; // 資料
Node next; // 指向下一個節點
}+------+------+
| data | next | --> 指向下一個節點
+------+------+
操作與時間複雜度
| 操作 | 時間 | 說明 |
|---|---|---|
| get(i) | O(n) | 從頭走到第 i 個 |
| addFirst | O(1) | 改 head 指標 |
| addLast | O(n) | 走到尾巴再加 |
| insert(i) | O(n) | 走到位置再插入 |
| removeFirst | O(1) | 改 head 指標 |
| removeLast | O(n) | 走到倒數第二個 |
| search | O(n) | 從頭找到尾 |
插入操作圖解
在 index 1 插入 15：
原本: [10] -> [20] -> [30]
↑
要插入這裡
Step 1: 建立新節點，指向原本的 [20]
[15] -> [20]
Step 2: 讓 [10] 指向新節點
[10] -> [15] -> [20] -> [30]
關鍵：只需要改兩個指標，不用搬移任何資料！
刪除操作圖解
刪除 index 1 的節點：
原本: [10] -> [15] -> [20] -> [30]
↑
要刪除
Step 1: 讓 [10] 跳過 [15]，直接指向 [20]
[10] -> [20] -> [30]
[15] 沒人指向它，會被垃圾回收
什麼時候用 Linked List？
適合用：
- 頻繁在頭部插入/刪除
- 不需要隨機存取
- 資料量變動大
不適合用：
- 需要頻繁用 index 存取
- 記憶體空間有限（每個節點多存一個指標）
變體
雙向鏈結串列 (Doubly Linked List)
每個節點多一個指向前一個節點的指標：
null <- [10] <-> [20] <-> [30] -> null
優點：可以往前走，removeLast 變 O(1)
環狀鏈結串列 (Circular Linked List)
尾巴指回頭：
[10] -> [20] -> [30] -> [10] -> ...
相關檔案
- Java 實作：LinkedList.java
- 視覺化：linked-list.html