数组的优点是访问快,随便给个下标就能 O(1) 拿到元素。它的缺点是插入和删除麻烦:往中间插一个元素,后面的都得往后挪。
链表换了个思路。它不要求元素连续存放,每个元素记住下一个元素在哪。这样插入和删除只需改几个「指针」,缺点是访问第 k 个元素得从头一个个走过去。
本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。
| 考试 | 大纲要求 | 本章位置 |
|---|---|---|
| GESP C++ 五级 | 考点 3:链表的创建、插入、删除、遍历和反转,单链表、双链表、循环链表的区别 | 全章 |
| CSP-J/S 入门级 | 3.1 线性结构:单链表、双向链表、循环链表 | 全章 |
数组与链表的对比
| 对比项 | 数组 | 链表 |
|---|---|---|
| 存储方式 | 连续内存 | 分散,靠指针连接 |
| 随机访问第 k 个 | O(1) |
O(n) |
| 已知位置后插入或删除 | O(n),要移动元素 |
O(1),只改指针 |
| 查找某个值 | O(n) |
O(n) |
| 额外空间 | 无 | 每个节点多存一个指针 |
结论很简单:经常随机访问就用数组,经常在中间插入删除就用链表。竞赛里绝大多数情况数组更划算,链表更多出现在需要频繁增删的场景,以及初赛的阅读程序题里。
单链表
单链表的每个节点存两部分:数据,以及指向下一个节点的指针。
struct Node {
int data; // 数据域
Node *next; // 指针域,指向下一个节点
};一个链表用一个头指针标记起点。如果头指针是 NULL(或 nullptr),说明链表为空。
建立链表(头插法)
头插法每次把新节点放到最前面。读入 1 2 3,建出来的链表是 3 → 2 → 1。
Node *head = NULL;
for (int i = 1; i <= n; i++) {
Node *p = new Node; // 申请一个新节点
p->data = a[i];
p->next = head; // 新节点指向原来的头
head = p; // 头指针移到新节点
}建立链表(尾插法)
尾插法保持读入顺序。读入 1 2 3,链表就是 1 → 2 → 3。
Node *head = NULL, *tail = NULL;
for (int i = 1; i <= n; i++) {
Node *p = new Node;
p->data = a[i];
p->next = NULL;
if (head == NULL) {
head = tail = p; // 第一个节点
} else {
tail->next = p; // 接到尾巴后面
tail = p; // 尾巴后移
}
}遍历
for (Node *p = head; p != NULL; p = p->next) {
cout << p->data << " ";
}查找
Node *find(Node *head, int x) {
for (Node *p = head; p != NULL; p = p->next) {
if (p->data == x) return p; // 找到就返回节点地址
}
return NULL; // 没找到
}在节点 p 之后插入
Node *q = new Node;
q->data = x;
q->next = p->next; // 先让新节点接上后面
p->next = q; // 再让 p 指向新节点这两行的顺序不能反。如果先写 p->next = q,原来 p 后面的那串节点就丢了。
删除节点 p 之后的节点
Node *q = p->next;
p->next = q->next; // 跳过 q
delete q; // 释放内存删除头节点
头节点没有前驱,要单独处理。
if (head != NULL) {
Node *q = head;
head = head->next;
delete q;
}这个「头节点要特殊处理」的麻烦,可以用一个不存数据的虚拟头节点(也叫哨兵)绕开,让所有节点的删除逻辑统一。
双向链表
双向链表的节点多存一个指向前驱的指针,可以往前也能往后走。
struct DNode {
int data;
DNode *prev; // 指向前一个
DNode *next; // 指向后一个
};在节点 p 之后插入 q:
q->next = p->next;
q->prev = p;
if (p->next != NULL) p->next->prev = q; // 后面还有节点才需要
p->next = q;代价是每个节点多一个指针,插入删除要改更多地方,写错一处整条链就断了。
循环链表
循环链表把尾节点的 next 指回头节点,形成一个环。从任意一个节点出发,一直走都能回到自己。
循环链表没有天然的「末尾」,遍历时要记住起点,走到回到起点为止:
Node *p = head;
do {
cout << p->data << " ";
p = p->next;
} while (p != head);约瑟夫环问题用循环链表描述最自然。
反转单链表
经典题,也是初赛阅读程序的高频素材。
Node *reverse(Node *head) {
Node *prev = NULL, *cur = head;
while (cur != NULL) {
Node *nxt = cur->next; // 先记住下一个
cur->next = prev; // 当前节点指向前一个
prev = cur; // prev 前进
cur = nxt; // cur 前进
}
return prev; // 新头指针
}三根指针依次挪动,走完一遍就反转了,时间 O(n),额外空间 O(1)。
用数组模拟链表
竞赛里 new 和 delete 很慢,而且容易忘记释放。常见做法是用两个数组模拟:一个存数据,一个存「下一个节点的下标」。
const int N = 100005;
int val[N], nxt[N];
int head = -1, cnt = 0; // head = -1 表示空链表
void insert_head(int x) { // 头插
val[cnt] = x;
nxt[cnt] = head;
head = cnt++;
}
void insert_after(int p, int x) { // 在 p 之后插入
val[cnt] = x;
nxt[cnt] = nxt[p];
nxt[p] = cnt++;
}
void erase_after(int p) { // 删除 p 之后的节点
nxt[p] = nxt[nxt[p]];
}用 -1 表示「没有下一个」,遍历时判断 p != -1 即可。这种写法在初赛阅读程序里很常见,看到两个数组加一个 nxt,基本就是链表。
复杂度
| 操作 | 单链表 | 双向链表 |
|---|---|---|
| 访问第 k 个 | O(n) |
O(n) |
| 已知位置插入/删除 | O(1) |
O(1) |
| 在头部插入/删除 | O(1) |
O(1) |
| 遍历整个链表 | O(n) |
O(n) |
常见易错点
- 插入时先接后面再接前面,顺序反了会丢链。
- 删除后要
delete,或者改用数组模拟。 - 头节点、尾节点要单独处理,忘了就崩。
- 遍历循环链表不能用
p != NULL,永远为真,要用起点判断。 ->和.别混:指针访问成员用->,对象访问成员用.。- 链表不支持下标访问,
l[i]这种写法只属于数组和vector。 - 反转链表时先改指针、后存后继。顺序反了就直接丢链,后面的节点全找不回来。
- 数组模拟链表用
0表示空。0是合法下标,必须用-1表示「没有下一个」。 - 约瑟夫环走了
m步而不是m-1步。当前节点自己已经报了 1。 - 循环链表删除后忘记维护前驱。单向链表没法回头,
prev要在移动时顺手记下来。
练习
练习 1:反转单链表
题目描述
给定 n 个整数,用链表存储,把它们反转后输出。
输入格式
第一行一个整数 n;第二行 n 个整数。
输出格式
输出一行 n 个整数,为反转后的序列。
输入输出样例
输入
5
1 2 3 4 5输出
5 4 3 2 1数据范围
1 \le n \le 10^5,元素在int范围内。
题目分析
反转链表是链表操作里最经典、也最能考出「你有没有真的理解指针」 的一道题。核心是三指针法:
prev:已经反转好的部分的头(初始为「空」);cur:当前要处理的节点;nxt:暂存cur的下一个节点(必须先存下来,因为cur->next马上就要被改掉)。
每一步做三件事:
- 先把
cur的下一个节点存进nxt(不然改完就找不到了); - 把
cur的next指向prev(完成这一步的反转); prev和cur各往前走一格。
走完一遍,prev 就是新链表的头。
为什么第 1 步不能省? 这是链表题最典型的坑:一旦写下 cur->next = prev,原来的后继就永久丢失了,后面的节点全部「断链」找不回来。
用数组模拟的写法(竞赛里更常用,避免 new 的开销)只需要把「指针」换成「下标」:
int prev = -1, cur = head;
while (cur != -1) {
int nx = nxt[cur]; // 1. 存后继
nxt[cur] = prev; // 2. 反转指向
prev = cur; // 3. 前进
cur = nx;
}
head = prev; // 新的头注意用 -1 表示空(而不是 0),因为 0 是合法的数组下标。这个约定和正文一致。
参考代码
练习 2:约瑟夫环(循环链表)
在线评测练习:P1423 报数出圈
题目描述
n 个小朋友围成一圈,编号从 1 到 n。从 1 号开始顺时针报数,报到 m 的人出圈,他旁边的人从 1 重新开始报数。按顺序输出所有出圈的小朋友的编号。
输入格式
输入一行,包含两个正整数 n 和 m,中间用一个空格隔开。
输出格式
输出一行,包含 n 个整数,依次为出圈的小朋友的编号,相邻两个整数之间用一个空格隔开。
输入输出样例
输入
5 3输出
3 1 5 2 4输入
1 1输出
1数据范围
1 \le n \le 1000,1 \le m \le 1000。
题目分析
这是「循环链表」最标准的应用场景:一圈人天然对应一个首尾相连的链表,出圈就是「删除一个节点」,然后从下一个节点接着数。
用数组模拟循环链表,写法比真指针干净得多:
- 建表:
nxt[i] = i + 1,最后nxt[n] = 1(首尾相连); - 循环
n次,每次:- 走
m - 1步(因为当前这个人自己就报了 1,所以只需再走m-1步); - 输出当前节点,然后把它从链表里删掉:
nxt[prev] = nxt[cur]; cur移到下一个节点,继续。
- 走
- 因为只有一个人时
nxt[cur] = cur(自己指向自己),删除后仍然指向自己,所以循环能自然终止。
最容易错的两个地方:
- 走
m-1步而不是m步。想一想:cur指向的人现在报的是 1,报 2 要走到下一个,……,报到m一共走了m-1步。 - 删除时要维护
prev。数组模拟的单向循环链表没法回头,所以循环里要始终记住「当前节点的前一个」:
for (int step = 1; step < m; step++) {
prev = cur; // 记住前驱
cur = nxt[cur]; // 前进
}
nxt[prev] = nxt[cur]; // 删除 cur
cur = nxt[cur]; // 从下一个继续为什么不用双向链表或直接 vector 删除? vector 删除中间元素是 O(n),总复杂度 O(n^2) 到 O(n^3);链表删除是 O(1)。本题 n \le 1000 用 vector 也能过,但链表才是这个问题的「正确」数据结构——这也是本章为什么把约瑟夫环放在链表这一节。
想进一步优化到
O(n),需要用「递推公式」f(n) = (f(n-1) + m) \bmod n(只能求最后剩下的那个人,不能输出全部出圈顺序)。见《找规律与打表》那一章的示例。
参考代码
小结
- 链表用指针把分散的节点串起来,插入删除
O(1),但随机访问要O(n)。 - 单链表只能往后走,双向链表能双向走,循环链表首尾相连。
- 头插法会反转顺序,尾插法保持顺序。
- 竞赛里常用两个数组模拟链表,避免
new/delete的开销。 - 反转链表用三指针法,必须先把后继存下来再改指针,否则会断链。
- 约瑟夫环用循环链表:
nxt[n] = 1首尾相连,出圈就是删除节点,注意「走m-1步」和维护前驱。 - 用数组模拟时用
-1表示「空」,不要用0(0是合法下标)。