GESP 五级 第 04 讲：单链表、双链表与循环链表

本讲定位：五级客观题的最大失分点，安排两周。2026 年 3 月五级真题的前三道单选全是链表（共 6 分），其中第 2 题直接考”双向循环链表在结点 p 之前插入 s”的四行指针赋值顺序。这类题光看不练必错——必须让每个学生亲手画指针图、亲手写一遍代码。

对应官方大纲：五级知识块 4「链表」——单链表、双链表、循环链表的创建、插入、删除、遍历、查找的基本操作。

前置知识：四级第 02 讲（指针）、四级第 03 讲（结构体，尤其是 -> 运算符）。指针不熟的学生必须先补四级第 02 讲。

代码说明：本讲所有链表操作均已用 g++ 11.5 编译运行验证，插入/删除后的链表内容逐个打印核对，并用 valgrind 思路检查了空指针访问。

1. 为什么需要链表

1.1 数组的痛点

int a[100] = {1, 2, 3, 4, 5};       // 想在 2 和 3 之间插入一个 99

要插入，必须把 3、4、5 整体后移一格——$O(n)$ 的搬运。删除同理。

1.2 链表的解法

链表不要求元素在内存中连续存放，每个结点额外存一个”下一个在哪”的指针。插入时只改指针，不搬数据。

数组：  [1][2][3][4][5]        连续，插入要搬家

链表：  [1|→][2|→][3|→][4|→][5|✗]     散落各处，靠指针串起来

1.3 数组 vs 链表（必考对比表）

操作 数组 链表
按下标随机访问 a[i] $O(1)$ ✅ $O(n)$ ❌（必须从头走）
已知位置插入/删除 $O(n)$（要搬移） $O(1)$ ✅（只改指针）
查找某个值 $O(n)$ $O(n)$
内存 连续，需预先分配 分散，动态申请
额外空间 无 每个结点多存指针（8 字节/个）

$$ \boxed{\text{数组强在“随机访问”，链表强在“插入删除”}} $$

⚠️ 高频判断题：“链表比数组快” —— ❌ 错，要看什么操作。随机访问数组完胜。

2. 单链表

2.1 结点定义

struct Node {
    int data;           // 数据域
    Node *next;         // 指针域：指向下一个结点
};

图示：

   head
    │
    ▼
 ┌────┬───┐   ┌────┬───┐   ┌────┬───┐
 │ 1  │ ●─┼──▶│ 2  │ ●─┼──▶│ 3  │ ✗ │   ← 最后一个 next = nullptr
 └────┴───┘   └────┴───┘   └────┴───┘