Learning Objectives
- 說明節點由值與指標組成，指標存的是另一個節點的位置，節點在記憶體裡不必相鄰
- 同時記住 head 與 tail，讓尾端插入變成 O(1)，並處理串列變空時 tail 的更新
- 列出插入、刪除時要改哪幾個指標，說明為什麼順序不能任意調換；C++ 刪除節點後要 delete
- 用哨兵（dummy）節點讓「刪除開頭」「空串列」等邊界情況不必特別處理
- 寫出雙向串列與環狀串列的插入、刪除，並比較各種串列的操作成本
散在記憶體各處、靠指標串起來的節點
第 02 課看過，陣列的元素在記憶體裡一個接一個排好，所以「第 i 個在哪裡」可以直接算出來；代價是在中間插入或刪除時，後面的元素都要搬。
鏈結串列（linked list）走另一條路：每個元素放在獨立配置的節點（node）裡，節點散在記憶體的任何位置，每個節點用指標（pointer）記住下一個節點的位置：
位址 0x2040 位址 0x1A08 位址 0x3310
┌────┬────────┐ ┌────┬────────┐ ┌────┬──────┐
│ 10 │ 0x1A08 │──→│ 20 │ 0x3310 │──→│ 30 │ null │
└────┴────────┘ └────┴────────┘ └────┴──────┘
val next val next val next
（位址是示意。）只要記住第一個節點（head），就能沿著 next 一路走到最後；最後一個節點的 next 是空的（Python None、C++ nullptr、Java null）。
| 語言 | 節點的寫法 | 取欄位 | 建立 | 歸還記憶體 |
|---|---|---|---|---|
| Python | class Node |
node.next |
Node(10) |
自動（沒有變數指著就會回收） |
| C++ | struct Node，next 是 Node* |
node->next |
new Node(10) |
要自己 delete |
| Java | static class Node |
node.next |
new Node(10) |
自動（垃圾回收） |
演算法軌第 11 課介紹過單向串列的走訪、在開頭插入、反轉與快慢指標。這一課專注在結構本身：每個操作要改哪幾個指標、改的順序、邊界情況怎麼處理，以及雙向、環狀這兩種變形。
三種語言的節點欄位都叫 val、next（雙向串列再加 prev）。
同時記住頭和尾
只記 head 的話，要接在尾端得先從頭走到最後一個節點，是 O(n)。多記一個 tail 指向最後一個節點，尾端插入就變成 O(1)：
self.tail.next = node # 接在目前的尾端後面
self.tail = node # 新節點變成尾端
多記一個指標，就多一份要維持正確的責任。最容易漏掉的兩個邊界情況：
- 空串列插入第一個節點：沒有 tail 可以接，新節點同時是 head 和 tail
- 取出最後一個節點，串列變空：head 變成 null，tail 也要跟著清成 null。忘了清的話，tail 還指著已經被取走的節點，下次接在尾端時會接到那個舊節點後面，新節點從 head 永遠走不到
head＋tail 的單向串列，從前面取出、從後面放入都是 O(1)，正好可以當佇列用（和第 04 課的環狀佇列比，它不會滿，但每個元素多一個指標的空間）。
head 與 tail：尾端插入與取出到變空
依序接上 10、20、30，再全部取出。第三次取出時 head 變成 null，tail 也要清掉；之後再放入 40，它又同時是 head 和 tail。C++ 版本每次取出都 delete 那個節點。（C++ 的方法名稱也是 push_back、pop_front；Java 是 pushBack、popFront。）
改指標的順序：先接新的，再斷舊的
在節點 prev 後面插入新節點 node，要改兩個指標：
node.next = prev.next # 1. 新節點先接上 prev 原本的下一個
prev.next = node # 2. prev 再改成指向新節點
順序不能反過來。先執行第 2 行的話，prev 原本的下一個節點就沒有任何變數或指標記得了，第 1 行再讀 prev.next 只會讀到新節點自己，後半段串列整段遺失（C++ 還會變成記憶體洩漏）。
規則可以記成：一個節點只要還要用到，在改掉最後一個指向它的指標之前，要先讓別的指標記住它。
刪除 prev 後面的節點也一樣：
Node* victim = prev->next; // 先用變數記住要刪的節點
prev->next = victim->next; // 跳過它
delete victim; // 最後才 delete：delete 之後就不能再讀 victim->next
先 delete 再讀 victim->next 是使用已釋放的記憶體（use after free），屬於未定義行為：有時看起來正常，有時讀到垃圾值，有時程式直接當掉，是 C++ 最難找的錯誤之一。
下面的小工具讓你自己選改指標的順序，選錯會看到節點怎麼遺失。
哨兵節點：讓「開頭」不再特別
單向串列刪除節點時，要找到它的前一個節點來改 next。可是開頭的節點沒有前一個，只好另外寫一段「如果要刪的是 head……」，刪除所有符合條件的節點時更麻煩，因為新的開頭也可能要刪。
哨兵節點（sentinel，也叫 dummy node）的作法是：在真正的第一個節點前面，先放一個不存資料的假節點。
- 每個真正的節點（包括第一個）都有前一個節點，刪除只剩一種寫法：
prev.next = prev.next.next - 處理完之後，
dummy.next就是新的 head
哨兵用一個節點的空間，換來程式少了一整個分支。分支越少，忘記處理邊界情況的機會也越少。
用哨兵節點刪除所有 7
串列是 7 → 7 → 3 → 7 → 5，開頭連續兩個都要刪。有了哨兵，刪開頭的 7 和刪中間的 7 是同一行程式。注意 prev 只在「下一個不用刪」時才往前走；刪掉一個之後要留在原地，再檢查新的下一個。（C++、Java 的函式名稱是 removeAll。）
想一想：指標的順序與邊界
單向串列要在 prev 後面插入 node。下面哪一種寫法是對的？
下面的程式會印出什麼？
同時記 head 和 tail 的單向串列，取出最後一個節點之後忘了把 tail 清成 null。接著再 push_back 一個新節點，會發生什麼事？
雙向串列：每個節點也記住前一個
單向串列只能往後走：要刪除某個節點，得從頭找它的前一個，是 O(n)。雙向串列（doubly linked list）的每個節點多一個 prev 指標：
null ← [prev|10|next] ⇄ [prev|20|next] ⇄ [prev|30|next] → null
好處：
- 拿到一個節點就能 O(1) 刪除它，
p.prev就是前一個 - 可以從 tail 往回走
代價是每個節點多一個指標的空間，而且每次插入、刪除要改的指標加倍：
| 操作 | 單向串列要改 | 雙向串列要改 |
|---|---|---|
| 在 p 後面插入 | 2 個（node.next、p.next） | 4 個（node.prev、node.next、後一個的 prev、p.next） |
| 刪除 p | 1 個（前一個的 next） | 2 個（前一個的 next、後一個的 prev） |
插入的四個指標要注意順序：p.next.prev = node 要在 p.next = node 之前做，因為它要透過 p.next 找到原本的下一個節點。
另外，p 在尾端時沒有「後一個節點」，p 在開頭時沒有「前一個節點」，這時要改的是 tail 或 head。下面的範例把這些 if 都寫出來，下一節再用哨兵把它們消掉。
雙向串列：插入與刪除（含頭尾的特殊情況）
先插入 30（p 是尾端，要改 tail），再插入 20（插在中間，四個指標都要改）。然後從 tail 沿著 prev 往回走一遍。最後刪除開頭與尾端，兩次都走到改 head 或 tail 的分支。（Java 的方法名稱是 insertAfter；C++ 版本在 remove 裡 delete 節點。）
環狀雙向串列加哨兵：所有 if 都不見了
上一個範例的 insert_after 和 remove 一共有三個 if，都是為了「前面或後面沒有節點」。把兩個技巧合起來，就能讓這些情況消失：
- 放一個哨兵節點
s，它不存資料，永遠在串列裡 - 把串列頭尾相接：最後一個節點的 next 指向哨兵，哨兵的 prev 指向最後一個節點；第一個節點的 prev 指向哨兵，哨兵的 next 指向第一個節點
空串列就是哨兵自己接自己：s.next = s、s.prev = s。
| 想做的事 | 寫法 |
|---|---|
| 插在最前面 | insert_after(s, x) |
| 插在最後面 | insert_after(s.prev, x) |
| 第一個節點 | s.next |
| 最後一個節點 | s.prev |
| 走訪 | 從 s.next 開始，回到 s 就停 |
現在任何真正的節點，前後一定都有節點（最差是哨兵），所以 insert_after、remove 都不需要 if。
Linux 核心的 list_head 就是這種結構：頭尾相接的雙向串列，用串列頭當哨兵，list_empty 檢查的正是「串列頭的 next 是否指回自己」。第 18 課的 LRU 快取也會用到它。
環狀雙向串列＋哨兵
一開始只有哨兵自己，畫面顯示「↺ 回到 0」。插入 20、30、10 時，不論插在最前面還是最後面，都是同一個 insert_after，四行指標一行 if 都沒有。刪除第一個和最後一個也是同一個 remove。
環狀單向串列：只記 tail
單向串列也可以頭尾相接：最後一個節點的 next 指回第一個。這時只要記 tail 一個指標就夠了，因為 tail.next 就是開頭：
- 插在開頭：新節點接上
tail.next，再讓tail.next指向新節點，O(1) - 插在尾端：先插在開頭，再把 tail 往前移一格（新節點就變成尾端），O(1)
- 輪流處理：
tail = tail.next一行就把開頭的節點轉到尾端
最後一點很適合「輪流」的情境，例如作業系統讓好幾個程式輪流使用 CPU（round-robin）、多人遊戲輪流出牌。
走訪環狀串列時沒有 null 可以當終點，要改成「回到起點就停」。因為一開始就站在起點上，條件要在走了一步之後才檢查，C++、Java 用 do … while，Python 用 while True 加 break。
環狀單向串列：插入與輪流
第一個節點自己接自己。之後的 push_back 都是「先插在開頭，tail 再往前一格」。印出內容後呼叫 rotate，tail 往前一格，開頭就換成下一個：10 20 30 → 20 30 10 → 30 10 20。（Java 的方法名稱是 pushFront、pushBack。）
各種串列的操作成本
n 是元素個數。「已知節點 p」表示手上已經有指向那個節點的指標，不必先找：
| 操作 | 陣列 | 單向（只記 head） | 單向（head＋tail） | 雙向＋哨兵 |
|---|---|---|---|---|
| 讀第 i 個 | O(1) | O(i) | O(i) | O(i) |
| 插在開頭 | O(n) | O(1) | O(1) | O(1) |
| 插在尾端 | 攤銷 O(1) | O(n) | O(1) | O(1) |
| 刪除開頭 | O(n) | O(1) | O(1) | O(1) |
| 刪除尾端 | O(1) | O(n) | O(n) | O(1) |
| 刪除已知節點 p | O(n) | O(n)（要找前一個） | O(n) | O(1) |
| 每個元素額外的空間 | 0 | 1 個指標 | 1 個指標 | 2 個指標 |
注意「head＋tail 的單向串列刪除尾端」仍然是 O(n)：刪掉最後一個之後，要把 tail 移到倒數第二個，可是單向串列沒辦法往回走。
表格上鏈結串列有很多 O(1)，但實務上陣列常常更快：陣列的元素相鄰，CPU 一次載入一整段記憶體（快取），走訪時幾乎都命中；鏈結串列的節點散在各處，每走一步都可能要到記憶體重新讀取。 所以選擇的依據通常是「需不需要在已知位置 O(1) 插入、刪除」，而不是只看表格。
想一想：雙向與環狀串列
雙向串列在 p 後面插入 node，四行程式的哪一種順序是錯的？
環狀雙向串列加哨兵 s，串列是空的時候，下面哪一個條件成立？
只記 tail 的環狀單向串列，下面哪一個操作不是 O(1)？
實作：把節點移到最前面
「最近使用的放最前面」是很常見的需求，第 18 課的 LRU 快取就是這樣做的。請在環狀雙向串列（有哨兵）完成 move_to_front(p)（C++、Java 是 moveToFront）：把節點 p 從原本的位置拆下來，接到哨兵後面。不要建立新節點，要搬的是同一個節點。預期輸出在右邊。
重點整理
- 節點由值與指標組成，散在記憶體各處；C++ 用
new建立的節點要自己delete - 同時記 head 與 tail，尾端插入變成 O(1)；串列變空時 tail 也要清成 null
- 改指標的順序：先讓別的指標記住還要用的節點，再改掉原本指向它的指標；C++ 先跳過節點，最後才 delete
- 哨兵節點讓每個真正的節點都有前一個，刪除開頭不再是特例
- 雙向串列多一個 prev，拿到節點就能 O(1) 刪除；插入要改 4 個指標，
p.next.prev = node要在p.next = node之前 - 環狀雙向串列＋哨兵：空串列是哨兵自己接自己，insert_after、remove 都不需要 if
- 環狀單向串列只記 tail，
tail.next是開頭；走訪用「回到起點就停」，tail = tail.next就能輪流
下一課：串列的應用。用鏈結串列表示多項式、只存非零元素的稀疏矩陣，看「只存需要的資料」能省下多少空間。