陣列的大小固定、中間插入要整批搬移；鏈結串列用「節點 + 指標」換來動態成長與 O(1) 插入。
它是第一個要你同時駕馭 struct、malloc/free 與指標的指標的資料結構，
也是作業系統核心（行程佇列、檔案系統快取）與各種函式庫的基本零件。
本單元對應 K&R §6.5 的自我參考結構概念，完整實作單向與雙向鏈結串列。
學習目標
- 理解自我參考結構（self-referential structure）的定義方式
- 完整實作單向鏈結串列：建立、頭插、尾插、搜尋、刪除、反轉、釋放
- 理解並實作雙向鏈結串列，體會 prev 指標的代價與好處
- 會用「指標的指標」寫出無特例的刪除／插入
- 能比較串列與陣列的複雜度並依場景選型
對照章節 / 參考來源
- K&R §6.5 Self-referential Structures（二元樹範例中的節點概念）
- K&R §6.7 Typedef、§5.4（指標與位址運算）
- CLRS《Introduction to Algorithms》第 10.2 節 Linked lists
- Linux 核心
include/linux/list.h（侵入式雙向串列的工業級範例）
觀念講解
1. 自我參考結構
結構不能包含「自己」（大小會無限大），但可以包含「指向自己型別的指標」 （指標大小固定，編譯器只需要知道型別名稱存在即可）：
struct node {
int value;
struct node *next; /* 合法：指標，不是完整的 struct node */
};ASCII 圖——三個節點的單向串列：
head
│
v
┌───────┬──────┐ ┌───────┬──────┐ ┌───────┬──────┐
│ 10 │ next─┼──>│ 20 │ next─┼──>│ 30 │ NULL │
└───────┴──────┘ └───────┴──────┘ └───────┴──────┘慣例：head == NULL 表示空串列；最後一個節點的 next 是 NULL。
2. 頭插與尾插
頭插 O(1)，最簡單也最常用（順序會反過來）：
struct node *push_front(struct node *head, int v)
{
struct node *n = malloc(sizeof *n); /* sizeof *n：改型別不用改這行 */
if (n == NULL) return head; /* 教學簡化；實務要回報錯誤 */
n->value = v;
n->next = head; /* 新節點指向舊頭 */
return n; /* 新節點成為新頭 */
}尾插要先走到最後一個節點，O(n)；若維護一個 tail 指標可降為 O(1)。
3. 刪除：指標的指標消除特例
初學者版的刪除要分「刪頭」與「刪中間」兩種情況。用 struct node **
追蹤「指向目前節點的那個指標」（可能是 head 本身，也可能是前一個節點的 next），
兩種情況合而為一：
void delete_value(struct node **pp, int v)
{
while (*pp != NULL && (*pp)->value != v)
pp = &(*pp)->next; /* 前進：改追蹤下一個 next 欄位 */
if (*pp != NULL) {
struct node *victim = *pp;
*pp = victim->next; /* 繞過被刪節點（不管它是不是頭） */
free(victim);
}
}pp ──> [head] ──> (10) ──> (20) ──> (30)
刪 20 時 pp 指向「節點10 的 next 欄位」
*pp = victim->next 直接把 10 的 next 接到 30這是 Linus Torvalds 稱為 "good taste" 的經典範例，務必親手畫圖理解。
4. 反轉（iterative）
三指標法，邊走邊把箭頭掉頭：
struct node *reverse(struct node *head)
{
struct node *prev = NULL;
while (head != NULL) {
struct node *next = head->next; /* 先存好下一站 */
head->next = prev; /* 箭頭掉頭 */
prev = head; /* 兩個游標前進 */
head = next;
}
return prev; /* prev 是新頭 */
}5. 雙向鏈結串列
每個節點多存一個 prev，可雙向走訪、O(1) 刪除「已知節點」（不用找前驅）：
┌────────────┐ ┌────────────┐ ┌────────────┐
NULL <──┼─prev next─┼──> │ │──> │ NULL │
│ 10 │ <──┼─prev 20 │ <──┼─prev 30 │
└────────────┘ └────────────┘ └────────────┘代價：每個節點多 8 位元組、每次插入刪除要維護兩倍的指標，寫錯機率也加倍。 守則：先接好新節點的兩條線，再改動鄰居的線，順序錯了串列就斷。
6. 複雜度比較
| 操作 | 陣列 | 單向串列 | 雙向串列 |
|---|---|---|---|
| 隨機存取第 i 個 | O(1) | O(n) | O(n) |
| 頭部插入/刪除 | O(n)（搬移） | O(1) | O(1) |
| 尾部插入 | O(1)（攤銷，動態陣列） | O(n)，有 tail 則 O(1) | O(1)（有 tail） |
| 已知節點刪除 | O(n) | O(n)（要找前驅） | O(1) |
| 搜尋值 | O(n)；已排序 O(log n) | O(n) | O(n) |
| 快取友善度 | 極佳（連續記憶體） | 差（節點四散） | 差 |
實務提醒：現代 CPU 快取效應巨大，資料量不大時「陣列 + memmove」常常實測比串列快。 串列的甜蜜點：頻繁的中間插刪、節點被外部長期引用、或大小完全不可預測。
範例程式
| 檔案 | 內容 | 編譯 / 執行 |
|---|---|---|
01_singly_list.c |
單向串列全套：頭插/尾插/搜尋/刪除（指標的指標版）/反轉/長度/釋放 | cc -std=c11 -Wall -Wextra -o out 01_singly_list.c && ./out |
02_doubly_list.c |
雙向串列：頭尾插入、雙向走訪、O(1) 節點刪除、整串釋放 | cc -std=c11 -Wall -Wextra -o out 02_doubly_list.c && ./out |
兩個程式的 main 都以寫死的示範資料展示每個操作，並在每步後印出串列狀態，
最後把所有記憶體釋放乾淨（可用 -fsanitize=address 驗證無洩漏）。
常見錯誤與陷阱
- 遺失串列頭：
head = head->next前沒有保存原頭就 free，整條串列漏光。 走訪用另一個游標變數，別直接動 head。 - use-after-free 的走訪：
for (p = head; p; p = p->next) free(p);——free 之後又讀p->next。正確寫法要先存next再 free。 - 忘記維護尾巴/邊界：插入空串列、刪除唯一節點、刪頭刪尾都是特例高發區； 用指標的指標或啞節點（dummy head）消除特例。
- 雙向串列指標順序錯：先斷開舊連結再接新連結，中途另一半就找不到了； 永遠先把新節點自己的 prev/next 設好。
sizeof(struct node *)誤用：malloc(sizeof(struct node *))只配了 8 位元組， 寫入成員直接踩記憶體。慣用寫法malloc(sizeof *n)可根絕此類錯誤。
練習題
- 【易】為單向串列加上
list_min/list_max/list_sum三個查詢函式。 - 【易】實作
push_back的 O(1) 版本：維護一個含head與tail的struct list包裝結構。 - 【中】實作「有序插入」
insert_sorted，維持串列遞增；用它寫插入排序。 - 【中】實作
list_merge：合併兩條已排序串列成一條（不配置新節點，只改指標）。 - 【中】偵測環：實作 Floyd 龜兔賽跑演算法
has_cycle，自建一個帶環串列測試 （測完記得把環拆掉再釋放）。 - 【難】實作 LRU 快取骨架：雙向串列 + 「最近使用移到頭部」+「淘汰尾部」， 容量固定為 N，展示存取序列造成的淘汰過程。
延伸閱讀
- K&R §6.5–6.7
- CLRS 第 10 章 Elementary Data Structures
- Linus Torvalds 談 "good taste" 刪除節點（TED 訪談，2016）
- Linux 核心的侵入式串列
list_head設計（container_of巨集） - 《Algorithms in C》(Sedgewick) 第 3 章