Lecture 17: 链表 (Linked Lists)

目录 · ← l16 · l18 →

Lecture 17: 链表 (Linked Lists)

概述

本讲解决的核心问题是：当元素个数在编译期未知、且需要在中间频繁插入与删除时，数组不再是合适的容器。 我们引入自引用结构 (self-referential structure)、头指针 (head pointer) 与指针链，把散布在堆 (heap) 上的结点串成单链表 (singly-linked list)，并给出建表、遍历、查找、有序插入、删除、销毁的标准惯用法。 链表是内核就绪队列、编译器符号表与抽象语法树 (AST) 子结点链的共同基础，也是下一讲树结构（每个结点带两个链接指针）的直接前驱。

核心概念与底层机制图解

• 数组作为容器的三个结构性限制 (limits of arrays)：数组只能表达”定长、连续、按位序访问”的数据，像一排焊死的储物柜：数量固定，想在中间塞进一个，得把后面所有柜子整体搬开。
  • 底层机制图解：int32_t a[1000] 在编译期决定 4000 字节连续空间；中间插入/删除都要整体搬移元素（O(n) 次内存写）；动态数组扩容 (dynamic resizing) 用 realloc 申请更大块并整体拷贝，按 2 倍增长时累计拷贝 ≤ 2N，平均浪费约 38% 空间。
  • 作用域与存储期：int32_t a[1000]; 是 automatic storage duration，随栈帧销毁；malloc 出来的动态数组是 allocated storage duration，必须显式 free。
• 自引用结构 (self-referential structure)：结构体内含一个指向同类型的指针成员，从而表达”任意多个自己”。
  • 直观解释：每个结点像一张卡片，卡片上写着”下一张卡片放在哪个房间”——房间不挨着也没关系，顺着地址能走完全部卡片。
  • 底层机制图解：struct node_t { int32_t value; struct node_t* next; }; 中 value 占 4 字节，next 是指针（64 位平台上 8 字节），含填充共 16 字节。必须用指针而不是内嵌 struct node_t next;：内嵌会让类型大小无限递归，编译器直接报 field 'next' has incomplete type。
  • 作用域与存储期：类型名 struct node_t 在文件作用域可见；每个 malloc 出来的结点是 allocated storage duration，生命周期从 malloc 到 free，与任何栈帧无关——这正是链表能跨函数存活的原因。
• 头指针与 NULL 终止符 (head pointer and NULL terminator)：整个链表由一个指针变量代表。
  • 直观解释：头指针是”第一张卡片所在房间的号码”；最后一个结点的 next 写 NULL，等于卡片上写”到此为止”。
  • 底层机制图解：LC-3 中 NULL 就是 x0000，而代码从 x3000 装载、全局数据区在 x4000 以上，0 永远不是合法结点地址——这就是 NULL 能当哨兵的原因。
  • 作用域与存储期：node_t* head; 定义在函数内时头指针本身是 automatic（栈上 8 字节），但它指向的结点在堆上；函数返回后头指针消失、结点仍在堆上，这就是内存泄漏 (memory leak) 的物理来源。

链表的内存布局图解（结点在堆上散布、由指针串联）：

 栈 (automatic)                堆 (allocated)
+--------------+          +----------------+     +----------------+     +----------------+
| head = 0x9A40|--------->| value = 30     |     | value = 20     |     | value = 10     |
+--------------+          | next  = 0x9B18 |     | next  = 0x9C70 |     | next  = 0x0000 |
                          +----------------+     +----------------+     +----------------+
                            @0x9A40              @0x9B18              @0x9C70
                              ^ 地址由 malloc 决定，与元素的逻辑次序无关

• 头插法与尾插法 (head insertion / tail insertion)：决定新结点接到链表的哪一端。
  • 直观解释：头插像”往牌堆顶放牌”，永远 O(1)；尾插像”把牌放到牌堆底”，没有尾指针就得从顶翻到底。
  • 底层机制图解：头插两步且顺序不可颠倒：n->next = head; head = n;。若颠倒则旧链表地址永久丢失（见本讲最后的演示）。尾插的 O(n) 版本用指向指针的指针 (pointer to pointer) 一次遍历定位到那个值为 NULL 的链接字段：

    node_t** find;
    for (find = &head; NULL != *find; find = &(*find)->next) { }
    *find = make_node(value);   /* 直接改写"最后一个 next 字段" */
    

    若维护 node_t* tail，尾插降为 O(1)：tail->next = n; tail = n;。

  • 作用域与存储期：find 是 automatic 变量（栈上 8 字节），保存的是堆中某个 next 字段的地址，解引用它就是对堆中链接字段的读或写。
• 遍历惯用法 (traversal idiom)：for (p = head; NULL != p; p = p->next)。
  • 直观解释：像一只手沿铁链逐节往前摸，摸到”没有下一节”就停。
  • 底层机制图解：每次迭代两次内存访问——读 p->value（偏移 0）与读 p->next（偏移 1），对应 LC-3 的 LDR R2,R0,#0 与 LDR R0,R0,#1。绝不能写 p++：结点地址不连续，p++ 只会走到相邻的无意义内存。
  • 作用域与存储期：迭代变量 p 是 automatic；循环体若 free(p)，p->next 立刻失效（见”删除”与”销毁”）。
• 有序插入、查找与删除 (sorted insertion, search and deletion)：三者共用”维护待改写的那个链接字段”这一手法。
  • 直观解释：有序插入像排队时走到第一个比自己高的人前面站定；删除像从链条上摘下一节，必须同时捏住它前面那一节。
  • 底层机制图解：用 find = &head 起步、find = &(*find)->next 前进，find 始终指向”待改写的链接字段”。于是有序插入是 n->next = *find; *find = n;，删除是 *find = dead->next; free(dead);，删头、删中间、删尾三种情况合并为同一句。这正是课程 player_delete 中 player_t** find 的写法（for (find = &player_list; p != *find; find = &(*find)->next)）。查找则是 O(n) 的线性扫描，命中即返回结点地址。
  • 作用域与存储期：free(dead) 后该结点进入”已释放”状态，内容随时可能被下一次 malloc 覆盖；任何仍指向它的指针都是悬垂指针 (dangling pointer)。
• 销毁整个链表 (destroying a list)：必须先保存 p->next，再 free(p)。
  • 直观解释：拆链条时先把”下一节在哪”记在手心，再把当前节扔掉。
  • 底层机制图解：free 会把内存交还分配器，分配器可能立刻写入自己的元数据，因此 free(p) 之后读 p->next 是未定义行为 (undefined behaviour, UB)。正确写法是 next = p->next; free(p);，循环结束后务必 *head = NULL。
  • 作用域与存储期：销毁后头指针归零是接口契约的一部分——调用者不能再使用旧头指针。
• 双向链表与哨兵 (doubly-linked list and sentinel)：每个结点多一个 prev 指针，换取 O(1) 删除与双向遍历。
  • 直观解释：每张卡片同时写”上一张”和”下一张”的房间号，于是从任意一张都能前后走；代价是每结点多 8 字节（开销增加 50%），且插入/删除要改写 4 个或 2 个指针。
  • 底层机制图解：课程推荐的简化写法是带哨兵的循环双向链表 (cyclic doubly-linked list with a sentinel)：

    static double_list_t my_list = {&my_list, &my_list};   /* 空表：指向自己 */
    void dl_insert (double_list_t* head, double_list_t* elt) {
        elt->next = head->next;       /* 1 */
        elt->prev = head;             /* 2 */
        head->next->prev = elt;       /* 3 */
        head->next = elt;             /* 4 */
    }
    void dl_remove (double_list_t* elt) {   /* 已知结点，O(1)，无需前驱 */
        elt->prev->next = elt->next;
        elt->next->prev = elt->prev;
    }
    

    没有 NULL 检查、没有头/尾特例：空表时哨兵的前后指针都指向自己。

  • 作用域与存储期：哨兵可以是 static（静态存储期，程序全程存在），也可以是 malloc 出来的；把 double_list_t 放在 “thing” 结构的首字段，就能在同一地址上自由转换”结点”与”数据”两种身份（&my_thing.dl == &my_thing）。
• 链式栈与链式队列 (stack and queue on a list)：同一个结点结构，改变增删端就得到两种容器。
  • 直观解释：栈像弹夹（后进先出，只在顶端操作）；队列像排队买饭（队首出、队尾进）。
  • 底层机制图解：栈只需一个 top 指针，push 是头插、pop 是删头，均 O(1)；队列需要 head 与 tail，enqueue 改 tail->next 与 tail，dequeue 改 head，均 O(1)。删掉最后一个元素时必须把 tail 也置 NULL，否则它成为悬垂指针。
  • 作用域与存储期：stack/q_head/q_tail 定义为 static 时具有 static storage duration，生命周期等于整个程序，但只在定义它的文件内可见。
• 链表与动态数组的权衡 (linked list vs dynamic array)：

代码示例与底层机制分析

示例 1：单链表的全套基本操作

代码 (C) — /tmp/ece220_l17/ll_core.c（完整文件已编译运行）：

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node_t node_t;

struct node_t {
    int32_t value;
    node_t* next;
};

static node_t* make_node(int32_t value)
{
    node_t* n = malloc(sizeof(*n));

    if (NULL == n) {
        fprintf(stderr, "out of memory\n");
        exit(2);
    }
    n->value = value;
    n->next = NULL;
    return n;
}

static node_t* push_front(node_t* head, int32_t value)      /* O(1) 头插 */
{
    node_t* n = make_node(value);

    n->next = head;         /* 先接旧链表 */
    return n;               /* 再成为新头 */
}

static node_t* append_slow(node_t* head, int32_t value)     /* O(n) 尾插 */
{
    node_t** find;

    for (find = &head; NULL != *find; find = &(*find)->next) {
    }
    *find = make_node(value);
    return head;
}

static node_t* find_value(node_t* head, int32_t value)      /* 查找：O(n) */
{
    node_t* p;

    for (p = head; NULL != p; p = p->next) {
        if (value == p->value) {
            return p;
        }
    }
    return NULL;
}

static node_t* insert_sorted(node_t* head, int32_t value)   /* 有序插入 */
{
    node_t** find = &head;
    node_t* n;

    while (NULL != *find && value > (*find)->value) {
        find = &(*find)->next;
    }
    n = make_node(value);
    n->next = *find;
    *find = n;
    return head;
}

static node_t* delete_classic(node_t* head, int32_t value)  /* prev 指针：三种情况 */
{
    node_t* p = head;
    node_t* prev = NULL;

    while (NULL != p && value != p->value) {
        prev = p;
        p = p->next;
    }
    if (NULL == p) {
        return head;                    /* 没找到 */
    }
    if (NULL == prev) {
        head = p->next;                 /* 情况 1：删头结点 */
    } else {
        prev->next = p->next;           /* 情况 2/3：删中间或尾结点 */
    }
    free(p);
    return head;
}

static node_t* delete_pp(node_t* head, int32_t value)       /* 指针的指针 */
{
    node_t** find = &head;
    node_t* dead;

    while (NULL != *find && value != (*find)->value) {
        find = &(*find)->next;
    }
    if (NULL == *find) {
        return head;
    }
    dead = *find;
    *find = dead->next;                 /* 三种情况合并为一句 */
    free(dead);
    return head;
}

static void destroy(node_t** head)
{
    node_t* p;
    node_t* next;

    for (p = *head; NULL != p; p = next) {
        next = p->next;                 /* 必须在 free 之前保存 */
        free(p);
    }
    *head = NULL;
}

验证到的真实输出（gcc -g -std=c99 -Wall -Werror ll_core.c -o ll_core && ./ll_core）：

push_front 10..50 head -> 50 -> 40 -> 30 -> 20 -> 10 -> NULL
append_slow      head -> 10 -> 20 -> 30 -> 40 -> 50 -> NULL
append_fast      head -> 10 -> 20 -> 30 -> 40 -> 50 -> NULL
find 30         -> found
find 35         -> not found
insert_sorted    head -> 10 -> 20 -> 30 -> 40 -> 50 -> NULL
delete 30 (mid)  head -> 10 -> 20 -> 40 -> 50 -> NULL
delete 10 (head) head -> 20 -> 40 -> 50 -> NULL
delete 50 (tail) head -> 20 -> 40 -> NULL
delete 99 (none) head -> 20 -> 40 -> NULL
rebuilt          head -> 15 -> 20 -> 25 -> 35 -> 40 -> NULL
pp delete 15     head -> 20 -> 25 -> 35 -> 40 -> NULL
pp delete 35     head -> 20 -> 25 -> 40 -> NULL
pp delete 25     head -> 20 -> 40 -> NULL
pp delete 25 x2  head -> 20 -> 40 -> NULL
after destroy    head -> NULL
allocated = 23, freed = 23

【代码做什么？】

1. push_front 依次插入 10、20、30、40、50，每次都放到最前面，因此打印为 50→10，即逆序。
2. append_slow 用 find 走到末尾的 NULL 链接后挂上新结点，得到正序 10→50；带尾指针的 append_fast（写法与示例 2 的 enqueue 相同）借助 tail 得到同样结果，但不再每次遍历。
3. find_value(head, 30) 命中后返回结点地址，打印 found；find_value(head, 35) 走完全表返回 NULL。
4. insert_sorted 以 50、30、20、40、10 的顺序插入，最终仍为升序，说明有序不变量被维持。
5. delete_classic 依次删除 30（中间）、10（头）、50（尾），各走一个分支；删除不存在的 99 时链表不变；delete_pp 用同一段代码完成同样的三种情况。
6. destroy 逐结点释放并把 head 置 NULL；计数器 23 = 23，说明无泄漏。

【底层机制透视】 malloc(sizeof(*n)) 在堆上分配 16 字节（int32_t 4 字节 + 4 字节填充 + 指针 8 字节），返回地址与上次分配无任何可预测关系——这正是必须显式保存 next 的物理原因。用 sizeof(*n) 而非 sizeof(node_t) 是 ECE 220 约定：它随指针类型自动变化。 (*find)->next 是一个 node_t* 左值，取地址得到”链接字段本身的地址”（类型 node_t**）；下一次 *find 读取该字段。把链接字段当变量来改写，正是删除三种情况能坍缩成一句的原因。 计数器 n_alloc/n_free 是 static int32_t，位于数据段而非栈上，因此跨调用保留数值。

【内存布局图解】 以 insert_sorted 建好的 10→20→30→40→50 为例（地址为示意）：

 栈（automatic）                        堆（allocated）
+-----------------+       +----------------+     +----------------+     +----------------+
| head = 0x9A40   |-----> | value=10       |     | value=20       |     | value=30       |
| tail = 0x9C70   |--+    | next  = 0x9B18 |---> | next  = 0x9C70 |---> | next  = 0x9D88 |--> ...
+-----------------+  |    +----------------+     +----------------+     +----------------+
                     +--------> tail 指向尾结点，尾插 O(1)
 find = &head -> 不匹配;  find = &head->next -> 命中 20;
 dead = *find;  *find = dead->next;  free(dead)      /* head/中间/尾部同一套代码 */

【与汇编的对应】 设 head 是文件作用域变量（符号表：from = R4, offset = 0），value 在偏移 0、next 在偏移 1（LC-3 按 16 位字编址）：

; ---- 遍历：for (p = head; p != NULL; p = p->next) ----
        LDR   R0,R4,#0        ; R0 = head
LOOP    BRz   DONE            ; p == NULL ? 退出
        LDR   R2,R0,#0        ; R2 = p->value   （偏移 0）
        ; ... 使用 R2 ...
        LDR   R0,R0,#1        ; p = p->next     （偏移 1）
        BRnzp LOOP
DONE

; ---- 头插：n->next = head; head = n;（顺序不可颠倒）----
        LDR   R0,R4,#0        ; R0 = head（旧链表）
        ADD   R6,R6,#-1
        STR   R0,R6,#0        ; 把 head 作为参数传给 MAKE_NODE
        JSR   MAKE_NODE       ; 返回新结点地址在栈顶
        LDR   R1,R6,#0        ; R1 = n
        ADD   R6,R6,#2        ; 弹出返回值与参数
        LDR   R0,R4,#0        ; R0 = head（旧链表地址）
        STR   R0,R1,#1        ; n->next = head   <- 先接旧链表
        STR   R1,R4,#0        ; head = n         <- 再改头指针

示例 2：用链表实现栈与队列

代码 (C) — /tmp/ece220_l17/ll_stack_queue.c：

static node_t* stack = NULL;

static void push(int32_t value)          /* LIFO：头插 */
{
    node_t* n = malloc(sizeof(*n));
    n->value = value;
    n->next = stack;
    stack = n;
}

static int32_t pop(int32_t* value)       /* LIFO：删头 */
{
    node_t* old = stack;
    if (NULL == stack) {
        return 0;
    }
    *value = stack->value;
    stack = stack->next;
    free(old);
    return 1;
}

static node_t* q_head = NULL;
static node_t* q_tail = NULL;

static void enqueue(int32_t value)       /* FIFO：尾插，O(1) */
{
    node_t* n = malloc(sizeof(*n));
    n->value = value;
    n->next = NULL;
    if (NULL == q_head) {
        q_head = n;
    } else {
        q_tail->next = n;
    }
    q_tail = n;
}

static int32_t dequeue(int32_t* value)   /* FIFO：删头，O(1) */
{
    node_t* old = q_head;
    if (NULL == q_head) {
        return 0;
    }
    *value = q_head->value;
    q_head = q_head->next;
    if (NULL == q_head) {
        q_tail = NULL;                   /* 队列变空，tail 必须同步归零 */
    }
    free(old);
    return 1;
}

验证到的真实输出：

stack pops : 4 3 2 1
pop empty  : empty
queue pops : 100 200 300 400
deq empty  : empty

【代码做什么？】

1. push(1..4) 把 1、2、3、4 压栈，栈顶为 4。
2. while (pop(&v)) 连续弹出得到 4、3、2、1（后进先出）；栈空时 pop 返回 0，循环结束。
3. 再次 pop 打印 empty，验证空栈判断；enqueue/dequeue 对 100..400 得到先进先出的 100、200、300、400。

【底层机制透视】 栈与队列共用同一结点结构，区别只在在哪一端增删：栈只改一个指针；队列必须同时维护 q_head 与 q_tail。 dequeue 里 if (NULL == q_head) { q_tail = NULL; } 是关键：若只把 q_head 置空而不管 q_tail，q_tail 就指向已释放结点，下一次 enqueue 会写 q_tail->next，即写已释放内存（堆破坏）。 pop/dequeue 用 int32_t* 输出参数返回数据、用返回值表达成败，这与 mem220_reallocate 的 -1/0 约定一致：调用者必须先检查返回值再使用 *value。

【内存布局图解】

 栈（stack 容器，只动 stack 指针）        队列（queue 容器，两端各一个指针）
 stack -> 4 -> 3 -> 2 -> NULL            q_head -> 100 -> 200 -> 300 -> NULL
                                         q_tail -------------------^
          push/pop 只动 stack；enqueue 动 q_tail，dequeue 动 q_head

【与汇编的对应】（value 在偏移 0、next 在偏移 1）

; ---- push(value)：value 已在 R0 ----
        ADD   R6,R6,#-1
        STR   R0,R6,#0        ; 参数入栈
        JSR   MALLOC_NODE     ; 返回新结点地址在栈顶
        LDR   R1,R6,#0        ; R1 = n
        ADD   R6,R6,#2        ; 弹出返回值与参数
        LDR   R2,R4,#0        ; R2 = stack
        STR   R2,R1,#1        ; n->next = stack
        STR   R1,R4,#0        ; stack = n

; ---- pop：删头 ----
        LDR   R0,R4,#0        ; R0 = stack
        BRz   POP_EMPTY       ; 空栈
        LDR   R1,R0,#0        ; R1 = stack->value
        LDR   R2,R0,#1        ; R2 = stack->next
        STR   R2,R4,#0        ; stack = stack->next
        ; ... 调用 FREE(R0) ...

示例 3：带哨兵的循环双向链表

代码 (C) — /tmp/ece220_l17/dll.c（核心部分）：

typedef struct dnode_t dnode_t;

struct dnode_t {
    int32_t value;
    dnode_t* prev;
    dnode_t* next;
};
static dnode_t sentinel;            /* static：静态存储期，程序全程存在 */

static void dl_init(void)
{
    sentinel.prev = &sentinel;      /* 空表：哨兵指向自己 */
    sentinel.next = &sentinel;
}

static void dl_insert_after(dnode_t* head, dnode_t* elt)   /* 4 次指针改写，无循环 */
{
    elt->next = head->next;
    elt->prev = head;
    head->next->prev = elt;
    head->next = elt;
}

static void dl_remove(dnode_t* elt)                        /* 2 次指针改写，无搜索 */
{
    elt->prev->next = elt->next;
    elt->next->prev = elt->prev;
    elt->prev = NULL;
    elt->next = NULL;
}

验证到的真实输出：

forward    head <-> 10 <-> 20 <-> 30 <-> head (cyclic)
backward   head <-> 30 <-> 20 <-> 10 <-> head (cyclic)
after removing 30:
forward    head <-> 10 <-> 20 <-> head (cyclic)

【代码做什么？】

1. dl_init 让哨兵的前后指针都指向自己，表示空表。
2. 依次 dl_insert_after(&sentinel, a=20)、dl_insert_after(a, b=30)、dl_insert_after(&sentinel, c=10)，每次都插在头部之后，最终顺序为 10、20、30。
3. print_forward 从 sentinel.next 出发、以 &sentinel != p 为终止条件，绕回哨兵即停；print_backward 把 next 换成 prev 得到逆序。
4. dl_remove(b) 摘除 30，只需两次指针改写，不需要从头搜索前驱。

【底层机制透视】 单链表删除要”找前驱”（O(n)），因为只有 next 一条线索；双向链表结点自带 prev，已知结点指针即可 O(1) 删除。 哨兵把”表头”从可为 NULL 的指针变成永远存在的结点，于是插入/删除代码不再需要任何边界判断——这是系统编程用哨兵消除特例的经典手法（Linux 内核的 list_head 即此结构）。 代价是每结点多 8 字节，且指针改写必须成对：dl_insert_after 四步少做一步，前驱的 prev 就永久失去同步。

【内存布局图解】

 数据段 (static sentinel)              堆
+---------------------+          +----------------+     +----------------+
| sentinel.prev = ----|--+       | value = 10     |     | value = 20     |
|   &sentinel (0x4100)|  |       | prev = --------|--+  | prev = --------|--+
| sentinel.next = ----|--+       | next = --------|--+->| next = --------|--+-> 回哨兵
|   &sentinel (0x4100)|  |       +----------------+  |  +----------------+  |
+---------------------+  |         @0x9A40           |    @0x9B18           |
      @0x4100            |                            |                      |
                         +----------------------------+----------------------+
   两个方向都能回到哨兵，所以循环终止条件是 &sentinel != p，而不是 p != NULL

【与汇编的对应】（prev 在偏移 1、next 在偏移 2）

; ---- dl_insert_after(head, elt)：head 在 R5+4，elt 在 R5+5 ----
        LDR   R0,R5,#4        ; R0 = head
        LDR   R1,R5,#5        ; R1 = elt
        LDR   R2,R0,#2        ; R2 = head->next
        STR   R2,R1,#2        ; elt->next = head->next
        STR   R0,R1,#1        ; elt->prev = head
        LDR   R2,R1,#2        ; R2 = elt->next
        STR   R1,R2,#1        ; head->next->prev = elt
        STR   R1,R0,#2        ; head->next = elt
        RET

演示（仅供演示，请勿模仿）：丢失整条链表

演示 A：头插顺序颠倒（/tmp/ece220_l17/ll_bug_lost.c）

/* DEMONSTRATION ONLY -- DO NOT IMITATE */
static node_t* broken_push_front(node_t* head, int32_t value)
{
    node_t* n = make_node(value);

    head = n;          /* BUG：n->next 仍是 NULL，旧链表被彻底孤立 */
    return head;
}

真实输出（程序本身是良定义的，但泄漏了 3 个结点）：

before broken insert   head -> 10 -> 20 -> 30 -> NULL
after broken insert    head -> 40 -> NULL

【为什么丢失】 head = n 只把栈上的头指针改指 40；10、20、30 仍在堆上，但再没有任何指针指向它们，程序既无法访问也无法释放。

 错误写法（head = n）：head -> 40 -> NULL，而 10 -> 20 -> 30 成为孤立结点（不可达 = 泄漏）
 正确写法（先 n->next = head 再 head = n）：head -> 40 -> 10 -> 20 -> 30 -> NULL

演示 B：释放后继续使用（悬垂指针）（/tmp/ece220_l17/ll_bug_uaf2.c）

/* DEMONSTRATION ONLY -- DO NOT IMITATE.  UB. */
static int32_t peek(node_t* p) { return p->value; }
static void release(node_t* p) { free(p); }

int main(void)
{
    node_t* head = malloc(sizeof(*head));

    head->value = 7;
    head->next = NULL;
    release(head);
    printf("value after free = %d\n", peek(head));  /* UB：读已释放内存 */
    return 0;
}

若把 head->value 直接写在 free 之后，-Werror 会在编译期拦下：error: pointer 'head' used after 'free' [-Werror=use-after-free]（GCC 12+ 的静态分析）。把读写拆进两个函数后编译器无法静态证明，程序得以编译，此时输出完全不确定（一次运行得到 value after free = 3491，另一次得到 7）。Valgrind 能稳定抓住它：

$ valgrind --error-exitcode=9 -q ./ll_bug_uaf2
==1212390== Invalid read of size 4
==1212390==    at 0x401152: peek (ll_bug_uaf2.c:19)
==1212390==  Address 0x4a6f040 is 0 bytes inside a block of size 16 free'd
==1212390==    by 0x40116D: release (ll_bug_uaf2.c:24)

UB：此处的输出完全依赖分配器实现与运行环境，绝不可依赖。

常见错误与调试技巧

• 头插顺序颠倒：head = n; n->next = head; 会让 n->next 指向自己（遍历死循环），或让旧链表丢失。 调试：valgrind --leak-check=full --show-leak-kinds=all ./prog 报告 “definitely lost” 块及其分配栈；在 GDB 中 print head、print n->next 逐步核对。
• free 后访问 p->next：销毁链表时写 free(p); p = p->next; 是 UB，可能读到分配器元数据而崩溃。 调试：valgrind -q ./prog 报 “Invalid read of size 8”；或 gcc -fsanitize=address -g（该选项需要足够虚拟地址空间，受限环境下改用 Valgrind）。
• 销毁后忘记置 head = NULL：调用者继续使用旧头指针即悬垂访问。 调试：销毁接口用 node_t** head，从类型上强制”我能改写你的头指针”；销毁后用 print head 确认其为 0x0。
• 在遍历中删除当前结点：for (p = head; p; p = p->next) { if (...) free(p); } 会在 free 后读 p->next。 调试：改用 node_t** find 循环（先取 next 再改链接）；gdb 中 watch -l p->next 观察字段何时被改写。
• 结构体自引用写成内嵌：struct node_t { int32_t value; struct node_t next; }; 报 field 'next' has incomplete type。调试：gcc -std=c99 -Wall -Werror -c file.c 直接定位错误行；规则是”自引用必须是指针”。
• 删空队列后忘记 q_tail = NULL：q_tail 成为悬垂指针，下一次 enqueue 写坏堆。调试：valgrind -q ./prog 报 “Invalid write of size 8”；每次 enqueue 前用 p q_head / p q_tail 确认二者同为 0x0 或都非空。
• sizeof 用错：malloc(sizeof(node_t*)) 只分配指针大小的 8 字节，写 n->next 就越界。 调试：valgrind -q ./prog 报 “Invalid write of size 8”；养成 malloc(sizeof(*n)) 的习惯。

关键要点

• 数组与链表的差别源于内存布局：连续布局换来 O(1) 随机访问，链式布局换来 O(1) 插入删除；选择容器本质是在”访问模式”与”修改模式”之间取舍。
• 自引用结构的成员必须是指针；NULL 是链表唯一的终止符，一切循环都写成 NULL != p。
• 指针的指针 T** 是消除链表边界情况的统一工具：find = &head 起步、find = &(*find)->next 前进，最后 *find = ... 一句话完成头/中/尾的插入与删除。
• 多指针改写顺序即正确性：头插先接后换、销毁先存 next 再 free、双向链表四个指针成对更新。
• 越”强大”的结构越要维护不变量：带哨兵的循环双向链表用”空表时哨兵指向自己”换掉了所有 NULL 判断，代价是每结点 8 字节与更严格的改写顺序。

思考题（带答案）

问题 1：下面这个 append 为什么在第二次调用时破坏链表？

static node_t* append(node_t* head, node_t* tail, int32_t value)
{
    node_t* n = make_node(value);

    if (NULL == head) { head = n; } else { tail->next = n; }
    tail = n;
    return head;
}

答案：tail 是按值传递的指针，函数内 tail = n 只改到副本，调用者的尾指针永远停在第一个结点。第二次调用时 tail 仍指向旧结点，tail->next = n 把新结点插在旧结点之后而不是队尾，链表结构被破坏；若调用者传入的 tail 已是已释放结点则直接 UB。修正是传 node_t** tail（*tail = n;）或让函数返回新的尾指针。

问题 2：给定长度 n = 100000 的链表，需要”按值查找”与”在第 50000 个元素前插入”各 1000 次。你会坚持用链表吗？

答案：不会无条件坚持。单链表按值查找是 O(n)，1000 次即 10^8 次结点访问；”已知位置的插入”虽只需 O(1) 次指针改写，但定位该位置同样要 O(n)。若改用动态数组：先排序后二分查找为 O(log n)，中间插入虽要 O(n) 次搬移，但搬移的是连续内存（memcpy、缓存友好、常数极小）。因此对”查找/插入混合”的场景动态数组通常更快；链表只在元素本身巨大（搬移代价高）或需要结点地址长期稳定（外部已握有结点指针）时才占优。