鏈結串列 — Linked Lists Interactive（C++）

📌 本頁使用方式（cppds Ch.4｜講義 04）

① 照節次讀：每一節先讀說明、動手玩互動元件，預測結果再按按鈕驗證。 ② 對照講義：頁上 §徽章對應 cppds 章節；細節與完整程式請回講義 04 與 cppds 原文。 ③ 每節做 quiz：答錯就回到該節重讀，不要往下跳。 ④ 最後翻關鍵詞彙卡（11 張）自測術語（中文為主、術語附英文），並用 REF 總覽區當速查表。標「講義補充」的節是課堂沒細講的延伸，第一輪可略過。

📑 講義 04 PDF 🖥 講義 04 HTML 📖 cppds 原文（LinearLinked）📘 Hello 演算法（鏈結串列）🏠 章節總覽

CONTENTS · 內容目錄

P00為什麼要鏈結？ P01Node 與指標 P02未排序串列操作 P03排序串列 P04雙向與環狀 P05STL 對照 EX練習題 REF總覽比較 CARD關鍵詞彙卡（11 張）

PROLOGUE · 開場

擺脫連續記憶體：用指標串起集合 cppds §4.2

陣列／vector 要求元素緊挨著放在記憶體裡；鏈結結構（linked structure）改用 節點（node）＋指標（pointer）：每個節點自己記得「下一個在哪」。只要能從第一個節點（head）出發，相對順序就能靠指標一路走出來。

取捨一覽

隨機存取 a[i]陣列 O(1)｜串列 O(n)

頭端插入/刪除陣列 O(n)｜串列 O(1)

記憶體串列多存指標

作業系統的例子

分時系統把工作排成環狀串列輪流執行：鏈結結構天生適合「不斷插入、移除、輪轉」的場景。

PART 01 · 節點

Node 類別：資料 + 一根指向下一個的指標 cppds §4.4.1

節點是鏈結串列的積木：data 放資料、next 指向下一個節點。 next == NULL 表示「後面沒有了」：這就是串列的結尾記號（grounded）。

C++ 實作 CODE

template <typename T>   // pythonds3/cppds/linked_list.hpp
class Node {
  private:
    T data;
    Node<T> *next;
  public:
    Node(T initdata) { data = initdata; next = NULL; }
    T getData() { return data; }
    Node<T>* getNext() { return next; }
    void setData(T d) { data = d; }
    void setNext(Node<T> *n) { next = n; }
};

指標語法速記

Node *p = new Node(93);
p->getData() // 93
p->getNext() // NULL
delete p; // 記得釋放！

講義 04 · Node 的使用畫面

#include <iostream>
#include "pythonds3/cppds/linked_list.hpp"   // Node / UnorderedList / OrderedList
using namespace std;
 
int main() {
    Node<int> *temp = new Node<int>(93);
    cout << temp->getData() << endl;
    cout << temp->getNext() << endl;   // NULL 印出來是 0
    delete temp;
    return 0;
}
 

預期輸出

93
0

new 出來的節點住在 heap，用指標操作、用 -> 呼叫方法。getNext() 是 0（NULL）：新節點還沒接上任何人。用完 delete，這是 C++ 跟你的約定。

PART 02 · 未排序串列

UnorderedList：add、search、remove 的指標舞步 cppds §4.3–4.4

未排序串列把新元素加在 head（最省事的位置，O(1)）。重點戲是 remove：需要 prev / cur 雙指標同行，找到後讓 prev「跳過」cur。 順序錯了串列就斷：先接住後面，再改前面。

速度

三大操作（動畫對照）CODE

void add(int item) {        // 加在 head，O(1)
    Node *temp = new Node(item);
    temp->setNext(head);      // ① 先接住整條串列
    head = temp; }           // ② 再移動 head
 
bool search(int item) {
    Node *cur = head;
    while (cur != NULL) {
        if (cur->getData() == item) return true;
        cur = cur->getNext(); } // 走訪 traversal
    return false; }
 
void remove(int item) { // 找不到就不修改串列
    Node *cur = head, *prev = NULL;
    while (cur != NULL && cur->getData() != item)
        { prev = cur; cur = cur->getNext(); }
    if (cur == NULL) return;
    if (prev == NULL) head = cur->getNext(); else prev->setNext(cur->getNext()); delete cur; }

完整類別長什麼樣（pythonds3/cppds/linked_list.hpp）

動畫面板用的是簡化寫法；實際的類別把 head 藏在 private、透過 Node 的 getNext()／setNext() 操作。size()、search()、remove() 都建立在同一個技巧上：走訪（traversal），也就是從 head 出發、一個節點一個節點地拜訪到 NULL 為止。

所有權契約：誰配置節點、誰負責釋放與複製，規則見本節下方講義卡「所有權與 deep copy」。

isEmpty / size CODE

bool isEmpty() { return head == NULL; }  // O(1)：只看 head
 
int size() {
    Node<T> *current = head;
    int count = 0;
    while (current != NULL) {
        count++;
        current = current->getNext();
    }
    return count;   // O(n)：串列不會免費告訴你長度
}

remove：雙指標＋delete CODE

void remove(T item) {
    Node<T> *current = head, *previous = NULL;
    bool found = false;
    while (!found && current != NULL) {
        if (current->getData() == item) found = true;
        else { previous = current; current = current->getNext(); }
    }
    if (found) {
        if (previous == NULL) head = current->getNext();
        else previous->setNext(current->getNext());
        delete current;   // C++ 沒有垃圾回收！
    }
}

為什麼需要 previous？單向串列不能往回走。current 停在要刪的節點上時，需要改的其實是「前一個節點的 next」，但這時已經回不去了。解法是讓 previous 永遠跟在 current 後面一格。刪 head 是特殊情況：previous 還是 NULL，這時改的是 head 本身。講義留了一題思考：刪最後一個節點時，這兩個分支夠用嗎？（提示：夠。想想 current->getNext() 那時是什麼。）

QUIZ · add 的兩行順序

add 裡若把兩行寫反（先 head = temp、再 temp->setNext(head)），會發生什麼事？

(A) temp 的 next 指向自己，其餘節點全部漏接

(B) 沒差，結果一樣

講義完整範例：UnorderedList 全套操作

講義 04 · add / size / search / remove

#include <iostream>
#include "pythonds3/cppds/linked_list.hpp"
using namespace std;
 
int main() {
    UnorderedList<int> myList;
    myList.add(31); myList.add(77); myList.add(17);
    myList.add(93); myList.add(26); myList.add(54);
 
    cout << myList << endl;
    cout << myList.size() << endl;
    cout << boolalpha << myList.search(93) << endl;
 
    myList.remove(54);
    myList.remove(93);
    myList.remove(31);
    cout << myList << endl;
    return 0;
}
 

預期輸出

54 26 93 17 77 31 
6
true
26 17 77

第一行輸出印證了 add 是頭插：最後加入的 54 排最前面。三次 remove 分別打中「中間、中間、尾巴」三種位置，下一張卡把指標動作攤開看。

講義 04 · remove(26) 的指標舞步逐格看

步驟	prev	cur	動作
開始	NULL	head（54）	兩根指標起跑
比對 54	54	26	不是目標：prev 跟上、cur 前進
比對 26	54	26	找到了，停
摘除	prev->setNext(cur->getNext())		54 直接指向 93，26 被跳過
收尾	delete cur		歸還記憶體（若 cur == head，改成 head = head->getNext()）

要背的只有一件事：單向串列摘節點需要「前一個」的協助，所以永遠帶著 prev、cur 兩根指標同行；目標剛好是 head 時沒有 prev，單獨處理。

講義 04 · 所有權與 deep copy

UnorderedList<int> a;
a.add(1); a.add(2);
UnorderedList<int> b = a;  // 必須複製整條鏈
b.remove(2);               // 不可改到 a

教學類別擁有 new 出來的節點：destructor 要逐一 delete；copy constructor 與 copy assignment 要 deep copy。若只複製 head，兩個物件會共用節點，最後可能 double free。remove 採 erase-if-found，找不到時保持不變。

PART 03 · 排序串列

OrderedList：維持大小順序的插入 cppds §4.5–4.6

排序串列的 add 不能亂插：prev/cur 往前走，直到 cur->getData() ≥ item 就是插入點。 search 因此能提前失敗：一旦看到比目標大的值就確定不存在。

remove(item) 也利用排序提前停止；找到後 unlink 並 delete，找不到則保持不變。

速度

排序版操作 CODE

void add(int item) { // 排序版：先找位置
    Node *cur = head, *prev = NULL;
    while (cur != NULL && cur->getData() < item) {
        prev = cur; cur = cur->getNext(); }
    Node *temp = new Node(item);
    temp->setNext(cur);
    if (prev == NULL) head = temp;
    else prev->setNext(temp);
}
 
// search 以 getData() 比較、以 getNext() 前進，可提前停止

分析：哪些操作 O(1)、哪些逃不掉走訪（cppds §4.6.1）

判斷準則一句話：只碰 head 的操作是 O(1)，其他都要走訪。 search 平均找到目標時走了 n/2 步：聽起來省一半，但 Big-O 只看成長率，係數 1/2 會被丟掉，而且最壞情況（不在串列裡、或排在最後）還是得走完全程，所以仍是 O(n)。下表是講義列的完整 List ADT，一次看清楚每個方法的代價：

方法	做什麼	未排序	排序
isEmpty()	串列是空的嗎（看 head）	O(1)	O(1)
add(item)	加入元素	O(1)（插 head）	O(n)（找位置）
size()	邊走邊數	O(n)	O(n)
search(item)	找得到嗎	O(n)	O(n)，可提前停
remove(item)	prev/cur 找到後摘除	O(n)	O(n)
append(item)	接在尾端（補充練習）	O(n)；有 tail 指標可 O(1)	不適用（位置由大小決定）
index(item)	回報元素排第幾	O(n)	O(n)
insert(pos, item)	插到指定位置	O(n)（走到 pos）	不適用
pop() / pop(pos)	移除尾端／指定位置並回傳	O(n)	O(n)

QUIZ · 平均走一半，為什麼還是 O(n)？

search 平均只要走 n/2 個節點就找到目標。為什麼複雜度不寫成 O(n/2)？

(A) 係數在 Big-O 裡沒有意義，且最壞情況要走完全程

(B) 因為 n/2 四捨五入之後就是 n

講義 04 · OrderedList：一樣的介面、排好的內容

#include <iostream>
#include "pythonds3/cppds/linked_list.hpp"
using namespace std;
 
int main() {
    OrderedList<int> myList;
    myList.add(31);
    myList.add(77);
    myList.add(17);
    myList.add(93);
    myList.add(26);
    myList.add(54);
 
    cout << myList << endl;
    cout << myList.size() << endl;
    cout << boolalpha << myList.search(93) << endl;
    cout << myList.search(100) << endl;
    return 0;
}
 

預期輸出

17 26 31 54 77 93 
6
true
false

同樣六次 add、同樣的呼叫介面，印出來卻是由小到大：差別全在 add 內部「找到正確位置再插」。search(100) 也更聰明：一碰到比 100 大的節點就能放棄（這條串列裡沒有更大的希望了）。

PART 04 · 變化型

雙向與環狀：多一根指標，換一批超能力課程補充（cppds §4 延伸）

單向串列刪尾端很痛：要先走到倒數第二個節點。雙向串列（doubly linked）給每個節點多存一根 prev，兩個方向都能走；環狀串列（circular）讓 tail 的 next 指回 head，作業系統的分時排程（輪流給每個程式一點 CPU）就是這樣繞圈的。

雙向串列的插入要同時接好四根指標：新節點的 prev、next，加上左右鄰居各一根。順序亂了照樣斷鏈，所以實務上常加哨兵節點（sentinel）：在頭尾各放一個不存資料的假節點，讓「插在最前」「刪到只剩一個」這些邊界情況消失，每次操作都變成「在兩個真實存在的節點之間動手」。多花兩個節點的記憶體，換到少一半的 if，很划算。

QUIZ · 尾端刪除

要讓「刪除尾端節點」變成 O(1)，需要哪種配置？

(A) 雙向串列 + tail 指標

(B) 單向串列 + tail 指標

PART 05 · 工業級

STL 的現成品：std::forward_list 與 std::list cppds §4.7

理解原理之後，實戰請用 STL：std::forward_list 是單向串列、std::list 是雙向串列。它們保證任意位置插入/刪除 O(1)（拿到迭代器之後），但不支援 [i] 隨機存取。

	vector	forward_list（單向）	list（雙向）
隨機存取 [i]	O(1)	—（不提供）	—（不提供）
頭端插入	O(n)	O(1) push_front	O(1) push_front
尾端插入	O(1) 攤銷	O(n)（無 tail）	O(1) push_back
已知位置插刪	O(n)	O(1) insert_after	O(1) insert/erase
每節點額外空間	0	1 指標	2 指標
cache 友善度	高（連續）	低（節點分散）

forward_list 的操作長相（cppds §4.7）

單向串列的 STL 版本連命名都在提醒你它的限制：插入叫 insert_after、刪除叫 erase_after，因為單向串列只能「在某個節點後面」動手。常用操作：

操作	說明
push_front(x) / pop_front()	頭端加入、移除，O(1)
emplace_front(...)	就地建構元素後放到最前面
insert_after(it, x)	在迭代器 it 的後面插入，O(1)
erase_after(it)	刪掉 it 後面那個節點，O(1)
remove(x) / unique() / sort()	串列自家的成員函式版本（不能用 std::sort，沒隨機存取）

工程直覺現代 CPU 上 vector 常常「理論輸、實測贏」，因為連續記憶體對快取太友善。選 list 家族的時機是：頻繁在中間插刪，而且手上已經握有位置（迭代器）。沒有這兩個條件，先用 vector。

QUIZ · 為什麼叫 insert_after？

forward_list 只提供 insert_after，不提供 insert（插在某節點前面）。原因是？

(A) 單向串列拿不到「前一個節點」，只能在已知節點後面接

(B) 歷史包袱，沒有技術原因

EXERCISES · 練習

動手驗證 cppds §4 綜合

EXERCISE 1 · 走訪計數

一條長度 n 的單向串列，size()（用走訪實作）與「取第 k 個元素」的成本分別是？

(A) O(n) 與 O(k)

(B) O(1) 與 O(1)

EXERCISE 2 · remove 邊界

remove(item) 用 prev/cur 雙指標。刪除的是 head 節點時，正確動作是？

(A) head = cur->getNext()（prev 是 NULL）

(B) prev->setNext(cur->getNext())

EXERCISE 3 · 記憶體

C++ 手刻串列 remove 之後少做了什麼，會發生什麼事？

(A) 少 delete cur → 記憶體洩漏

(B) 少 cur = NULL → 編譯錯誤

補充練習：實作 append() 講義補充（課堂跳過）

講義留了一題課後練習：替 UnorderedList 加上 append(item)，把新元素接在尾端。走訪版的解答長這樣：

append：一路走到尾 CODE

void append(T item) {
    Node<T> *temp = new Node<T>(item);
    if (head == NULL) { head = temp; return; }  // 空串列：直接當 head
    Node<T> *current = head;
    while (current->getNext() != NULL)
        current = current->getNext();       // 一路走到最後一個節點
    current->setNext(temp);
}

補充練習 · append 的成本

上面這個 append() 是 O(n)。要讓它變成 O(1)，正確的做法是？

(A) 類別多存一根 tail 指標，append 直接接在 tail 後面

(B) 把串列改成從尾端往頭端指

cppds Ch.4 課後題精選（自我挑戰）

size 的 O(1) 版：現在的 size() 要走訪整條串列。把「節點數」存成成員變數，改寫 add / remove / size，讓 size() 變 O(1)。
驗證 remove 契約：目標不在串列裡時應保持不變。替空串列、缺少目標、刪 head、刪尾端各寫一個測試。
補完 ADT：實作 append、index、pop、insert 四個缺席的方法，並分析各自的 Big-O。
slice(start, stop)：回傳從 start 到 stop（不含）的新串列。
用繼承減少重複：OrderedList 與 UnorderedList 大量方法相同。設計繼承階層，讓共同的部分只寫一次。
串列版 Stack／Queue／Deque：用鏈結串列各實作一次，跟第 3 章的 vector 版比效能。哪些操作變快、哪些變慢？

完整題目在 cppds ProgrammingExercises；第 1、2 題是課本的自我檢測熱身，第 5 題會逼你把兩個類別的差異想透。

REFERENCE · 總覽

鏈結串列 vs 陣列：一張表決勝負 cppds §4 總覽

操作	vector／陣列	UnorderedList	OrderedList
存取第 k 個	O(1)	O(k)	O(k)
插入（頭）	O(n)	O(1)	O(n)（找位置）
search	O(n)／排序後 O(log n)	O(n)	O(n)，可提前停
remove（已找到）	O(n)（搬移）	O(1)（改指標）	O(1)（改指標）

關鍵概念複習 ① 鏈結 = 用指標買「頭端 O(1) 插刪」，代價是失去隨機存取。
② 指標操作口訣：先接住後面，再改前面。
③ prev/cur 雙指標是 remove／有序插入的標準步法；head 是唯一入口，弄丟就全丟。
④ 之後的遞迴章（cppds Ch.5）會看到：串列的遞迴定義「node + 剩下的串列」。

CARDS · 關鍵詞彙卡