Learning Objectives
- 說明鏈結串列的節點由「值」和「指向下一個節點的 next」組成，並用 Python、C++、Java 寫出節點
- 從 head 出發沿著 next 走訪整個串列，知道走到 null（None、nullptr）就是結尾
- 在開頭或某個節點後面插入新節點，說明兩個指標要依什麼順序修改
- 刪除一個節點：找到它的前一個節點並跳過它；C++ 要用 delete 歸還記憶體
- 用 prev、cur、nxt 三個指標反轉串列，用快慢指標找中間的節點
- 比較陣列與鏈結串列各種操作的成本，依需求選擇資料結構
不用搬動元素的串列
第 03 課看過：陣列的元素在記憶體裡一個緊接著一個，所以用索引讀取很快，但要在最前面插入一個元素時，後面每個元素都得往後挪一格，n 個元素就要搬 n 次。
排隊時如果每個人只記得「我後面是誰」，有人要插隊到第一個，只要他記住原本排第一的人，其他人完全不用動。鏈結串列（linked list）就是這樣組成的：
- 每個元素放在一個節點（node）裡，節點有兩個欄位：值
val，以及指向下一個節點的next - 第一個節點叫 head，只要記住 head，就能沿著
next找到所有節點 - 最後一個節點的
next是空的：Python 寫None，C++ 寫nullptr，Java 寫null
節點不必在記憶體裡相鄰，散在各處都可以，靠 next 連成一條鏈。這一課的「串列」都是指這種單向鏈結串列（singly linked list），每個節點只知道下一個是誰。
三種語言的節點
三種語言都用一個小類別（或結構）表示節點，欄位名稱一律是 val 和 next：
class Node:
def __init__(self, val):
self.val = val
self.next = None # 還沒接上任何節點
struct Node {
int val;
Node* next; // 指向下一個節點的指標
Node(int v) : val(v), next(nullptr) {}
};
Node* head = new Node(12); // new 配置一個節點，得到它的位址
static class Node {
int val;
Node next; // 物件欄位預設是 null
Node(int val) { this.val = val; }
}
C++ 的 next 是指標（存另一個節點的位址），用 -> 取欄位；Python 和 Java 的變數本來就是指向物件的參考，用 . 取欄位。三者的意思相同：next 告訴你下一個節點在哪裡。
C++ 用 new 建立的節點不會自動回收，用完要 delete，否則會記憶體洩漏（memory leak）。所以本課的 C++ 範例最後都有一段釋放節點的程式；Python 和 Java 由垃圾回收自動處理，不需要這一段。
建立三個節點並走訪
先看前半段：三個節點一開始各自獨立（每一列都只有一個節點），head.next = second 之後，從 head 出發就能走到 7。後半段的 cur 從 head 出發，每一輪往後走一個節點，走到 null 就停。注意 second 那一列：它和 head 那一列的後半段是同一批節點，不是複製出來的。
插入節點：兩個指標的修改順序
在開頭插入（push front）：新節點的 next 指向原本的 head，再讓 head 改成新節點。不管串列多長都只改兩個指標，是 O(1)。
在某個節點 prev 後面插入：
node.next = prev.next：新節點先接上 prev 原本的下一個prev.next = node：prev 再改成指向新節點
順序不能顛倒。如果先寫 prev.next = node，prev 原本的下一個就沒有任何變數記得了，第 2 步的 node.next = prev.next 會讓新節點指向自己，後半段串列整段遺失。
插入本身是 O(1)，但前提是已經拿到 prev；要在第 k 個位置插入，得先從 head 走 k 步找到 prev，這一段是 O(k)。
在開頭與中間插入
一開始串列是 20 → 40。push_front 把 10 接在最前面；insert_after 把 30 插在 20 後面。看 node 那一列：新節點先接上後面的節點，然後才被前面的節點指到，那一刻它才出現在 head 那一列。（C++、Java 的函式名稱是 pushFront、insertAfter。）
刪除節點：找到前一個，跳過它
單向串列的節點只知道下一個是誰，不知道上一個是誰。要刪除值為 target 的節點，得找到它的前一個節點 prev，再讓 prev 跳過它：
victim = prev.next
prev.next = victim.next # prev 直接連到 victim 的下一個
被跳過的節點已經不在串列裡了。Python、Java 沒有任何變數再指向它，垃圾回收會自動收走；C++ 要自己寫 delete victim 歸還記憶體，而且要在改好指標之後才 delete，delete 之後就不能再讀 victim->next。
刪除開頭的節點是特例：它沒有前一個節點，直接讓 head 往後移一個就好。所以 remove_value 會回傳新的 head，呼叫的地方要寫 head = remove_value(head, x)。
刪除中間的節點與開頭的節點
先用「一直插在開頭」的方式建出 10 → 20 → 30 → 40（依序插入 40、30、20、10）。刪 30：prev 走到 20 停下，20 改成直接指向 40。刪 10：它是開頭，head 直接往後移。C++ 版本最後用同一個函式把剩下的節點全部刪掉。（C++、Java 的函式名稱是 removeValue。）
想一想：插入與刪除
在 prev 後面插入新節點 node 時，如果寫成這個順序：
prev.next = node
node.next = prev.next
會發生什麼事？
下面的程式會印出什麼？
class Node:
def __init__(self, val):
self.val = val
self.next = None
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next = head.next.next
cur = head
while cur is not None:
print(cur.val, end=" ")
cur = cur.next
單向鏈結串列有 n 個節點，要刪除「值等於 x 的節點」（不知道它在哪裡）。最壞情況要多少時間？
反轉串列：三個指標
把 1 → 2 → 3 → 4 變成 4 → 3 → 2 → 1，不建立新節點，只把每個箭頭轉向。需要三個指標：
| 指標 | 意思 |
|---|---|
prev |
已經反轉好的部分的開頭（一開始是 null） |
cur |
正在處理的節點（一開始是 head） |
nxt |
cur 原本的下一個，先存起來 |
每一輪做四件事：
nxt = cur.next：先記住下一個，因為第 2 步會把這個箭頭改掉cur.next = prev：把 cur 的箭頭轉向，指回已經反轉好的部分prev = cur：cur 加入「已反轉」的部分cur = nxt：處理下一個
cur 變成 null 時，所有節點都處理完了，prev 指向原本的最後一個節點，也就是新的 head。每個節點只處理一次，時間 O(n)，額外空間只有三個指標，O(1)。
一步一步把箭頭轉向
進入 reverse 之後看 prev 和 cur 兩列：prev 那一列是已經反轉好的部分，每一輪變長一個；cur 那一列是還沒處理的部分，每一輪變短一個。head 那一列是函式的參數，第一輪之後它指向的節點 1 已經變成結尾，所以只剩 1 → null。
快慢指標：走一次就找到中點
鏈結串列不能用索引跳到中間。最直接的做法是走兩次：第一次數出有 n 個節點，第二次再走 n / 2 步。
快慢指標只要走一次：slow 一次走一步，fast 一次走兩步。fast 走到結尾時，slow 剛好走了一半的路，就停在中間。
- 節點數是奇數（例如 5 個）：slow 停在正中間（第 3 個）
- 節點數是偶數（例如 6 個）：slow 停在中間兩個的後面那一個（第 4 個）
迴圈條件 fast is not None and fast.next is not None 要兩個都檢查：fast 一次走兩步，必須確定 fast.next 存在，才能讀 fast.next.next。
同樣的技巧也能判斷串列裡有沒有環：如果有環，fast 會在環裡繞圈追上 slow；沒有環，fast 會走到 null。
快慢指標找中間的節點
先建 10 → 20 → 30 → 40 → 50，fast 走到最後一個節點時，slow 停在 30。再建 6 個節點的串列，fast 走到 null 時，slow 停在 40。
陣列和鏈結串列怎麼選
| 操作 | 陣列（動態陣列） | 單向鏈結串列 |
|---|---|---|
| 讀第 k 個元素 | O(1)，用索引直接算出位置 | O(k)，要從 head 走 k 步 |
| 在開頭插入或刪除 | O(n)，後面全部要搬 | O(1)，改 head 就好 |
| 在已知節點的後面插入或刪除 | O(n)，後面全部要搬 | O(1)，改一兩個指標 |
| 在結尾加入 | 攤銷 O(1) | O(n)；另外記住尾巴的指標就是 O(1) |
| 搜尋某個值 | O(n)；排序過可以二分搜尋，O(log n) | O(n)，不能二分搜尋 |
| 額外的記憶體 | 少（可能預留一些空位） | 每個節點多一個指標 |
陣列的元素在記憶體裡相鄰，CPU 讀取很有效率，所以大多數情況下動態陣列（Python 的 list、C++ 的 vector、Java 的 ArrayList）就是最好的選擇。
鏈結串列適合「常常在開頭或已知位置插入、刪除」的情況，也是很多資料結構的零件：第 10 課的佇列、下一課雜湊表的鏈結法，都可以用它實作。
各語言也有內建的鏈結串列：C++ 的 std::list、Java 的 LinkedList，兩者都是雙向的；Python 沒有，需要兩端快速進出時通常用 collections.deque。
雙向鏈結串列（doubly linked list）的節點多一個 prev 欄位指向前一個節點，刪除時不必另外找前一個，代價是每個節點多一個指標、插入刪除要多改一組指標。
想一想：反轉、快慢指標與成本
反轉 1 → 2 → 3 → 4 時，迴圈第一輪結束後，prev 和 cur 分別指向哪個節點？
用快慢指標（範例的寫法）找 7 個節點 1 → 2 → … → 7 的中間，會印出什麼？
下列哪一個操作，鏈結串列明顯比陣列慢？
實作：刪除已排序串列裡重複的值
串列已經由小到大排好：1 → 3 → 3 → 3 → 5 → 7 → 7 → 9。請完成 remove_duplicates（C++／Java 是 removeDuplicates），讓每個值只留一個。已排序代表相同的值會排在一起，所以只要比較「cur 和它的下一個」。C++ 版本記得 delete 被跳過的節點。
重點整理
- 鏈結串列由節點組成，每個節點有
val和指向下一個節點的next；記住 head 就能走到全部節點，next是 null 表示結尾 - 走訪：
cur從 head 出發，cur = cur.next一路走到 null，O(n) - 插入：先
node.next = prev.next，再prev.next = node；在開頭插入是 O(1) - 刪除：找到前一個節點，
prev.next = victim.next跳過它；C++ 要delete，而且要在改好指標之後 - 反轉：
prev、cur、nxt三個指標，每一輪「記住下一個、轉向、兩個指標往前」，O(n) 時間、O(1) 額外空間 - 快慢指標：slow 一次一步、fast 一次兩步，fast 到底時 slow 在中間
- 常常要讀第 k 個元素就用陣列；常在開頭或已知位置插入、刪除才考慮鏈結串列
下一課：雜湊表。它能在平均 O(1) 的時間裡查到一個鍵；兩個鍵擠在同一格時，處理方法之一就是在每一格掛一條串列。