链表（Linked List）
1. 链表的结构
1.1 数组的局限性
在探讨链表之前，我们首先需要理解其“对手”——数组（Array）的特性及其固有的局限性。
数组在内存中是一段物理上连续的存储空间，这为它带来了极高的随机访问效率。给定一个索引 $i$，我们可以在 $O(1)$ 时间内通过地址偏移公式直接访问元素 a[i]。
然而，正是由于“物理连续存储”这一特性，给数组带来了两个主要的性能瓶颈： * 大小固定：数组在创建时必须指定一个固定的大小。如果初始分配过小，当数据量超出预期时，就需要重新开辟一个更大的内存空间，并将所有旧数据复制过去，这个过程的开销极为昂贵；如果分配过大，则会造成严重的内存闲置浪费。 * 插入与删除低效：要在数组的第 $k$ 个位置插入一个新元素，为了保持数组的连续性，必须将从第 $k$ 个位置开始的所有后继元素都向后移动一位，时间复杂度为 $O(N)$。删除元素也面临同样的批量移动问题。
为了在频繁插入、删除的场景下取得高效率，链表应运而生。
1.2 链表的“指针”思想
链表的核心思想是放弃对物理连续内存的苛求。它的元素（我们称之为“节点”）可以零散地散布在内存的任何位置。 为了将这些零散的节点组织成一个逻辑上连续的线性序列，我们引入了“指针”或“引用”。
我们可以把链表想象成一个寻宝游戏： 你手上有第一张藏宝图（第一个节点），它告诉你宝藏（数据）的内容，并且在图的背面写着下一张藏宝图的隐藏地点（指向下一个节点的指针）。你根据指引找到第二张藏宝图，它同样包含着宝藏和指向下一张图的线索。如此往复，直到你找到一张背面写着“游戏结束”（空指针）的图，整个寻宝过程宣告结束。
- 每一张藏宝图 $\to$ 节点（Node）
- 藏宝图上的宝藏 $\to$ 数据域（Data）
- 下一张图的线索 $\to$ 指针域（Next 指针）
1.3 节点：链表的基本单位
一个最简单的单向链表节点（Singly Linked List Node）由两部分构成：
1. 数据域（Data Field）：用于存储元素的值。
2. 指针域（Pointer Field）：用于存储下一个节点的内存地址（通常命名为 next）。
整个链表由一个指向第一个节点的“头指针”（head）来标识。链表末尾节点的 next 指针通常指向一个特殊的值（如 nullptr 或 -1），用来表示链表的终结。
head
│
▼
+--------+--------+ +--------+--------+ +--------+--------+
| val | next | ───> | val | next | ───> | val | NULL |
+--------+--------+ +--------+--------+ +--------+--------+
1.4 静态链表 vs. 动态链表
实现链表主要有两种方式：
- 动态链表（Dynamic Linked List）：
教科书中最标准的实现方式。在程序运行时，使用
new(C++) 或malloc(C) 动态申请内存来创建每一个节点。 - 优点：灵活，能根据运行时的实时需要动态增删节点，直到物理内存耗尽。
-
缺点：频繁地申请和释放堆内存会带来一定的系统开销；且涉及底层的指针指针操作，若管理不当极易造成内存泄漏（Memory Leak）。
-
静态链表（Static Linked List）： 在算法竞赛中，为了追求极致的执行效率和编码的简洁性，选手们常常使用数组来模拟链表。 我们预先开辟一个足够大的数组空间（例如大小为 $10^5 + 10$）。指针域不再存储真实的物理内存地址，而是存储下一个节点在数组中的下标（index）。
- 优点：规避了频繁申请动态内存的额外时间开销，运行速度极快，且易于调试，代码非常简短。
- 缺点：链表的总容量上限在编译期就已经由数组大小固定。
对于算法竞赛而言，熟练掌握静态链表的实现至关重要。
2. 静态链表的实现
我们使用两个平行的数组 val[] 和 nxt[] 来模拟单链表：
* val[i]：存储索引为 $i$ 的节点的数据值。
* nxt[i]：存储索引为 $i$ 的节点的下一个节点在数组中的下标。
* head：整型变量，存储头节点的索引。
* idx：整型变量，指向当前数组中下一个可分配（未使用）的空闲位置。
2.1 核心操作
1. 初始化
空链表状态下，头指针 head 指向特殊的标记 -1，可分配指针 idx 归零。
const int N = 100005;
int head, val[N], nxt[N], idx;
void init() {
head = -1; // -1 表示空指针
idx = 0; // 从数组 0 号位置开始分配
}
2. 在表头插入元素（头插法）
要在链表头部插入一个值为 $x$ 的新节点，时间复杂度为 $O(1)$：
void add_to_head(int x) {
val[idx] = x; // 存储数值
nxt[idx] = head; // 新节点的 next 指向原 head
head = idx; // head 更新为新分配的节点
idx++; // idx 指向下一个空闲位置
}
3. 在任意已知位置后插入元素
要在索引为 $k$ 的节点后面插入一个值为 $x$ 的新节点，时间复杂度为 $O(1)$：
void add(int k, int x) {
val[idx] = x; // 存储数值
nxt[idx] = nxt[k]; // 新节点的 next 指向原 k 节点的后继
nxt[k] = idx; // k 节点的 next 指向新节点
idx++;
}
4. 删除任意已知位置后的节点
要删除索引为 $k$ 的节点后面的那个节点（绕过该节点），时间复杂度为 $O(1)$：
void del(int k) {
nxt[k] = nxt[nxt[k]]; // k 节点的 next 指向其下下个节点
}
注：被断开的节点在数组中并未被物理抹除，它只是失去了引用，在静态链表中我们通常不回收“孤儿节点”以保持代码的极简性。
5. 遍历链表
void traverse() {
for (int i = head; i != -1; i = nxt[i]) {
cout << val[i] << " ";
}
cout << endl;
}
2.2 静态链表完整代码示例
问题描述： 实现一个单链表，支持以下三类操作： 1.
H x：在表头插入一个数 $x$。 2.D k：删除第 $k$ 个插入的数后面的数（当 $k=0$ 时，代表删除头节点）。 3.I k x：在第 $k$ 个插入的数后面插入一个数 $x$。 共执行 $M$ 次操作，最后输出链表。
#include <iostream>
using namespace std;
const int N = 100010;
int head, val[N], nxt[N], idx;
void init() {
head = -1;
idx = 0;
}
void add_to_head(int v) {
val[idx] = v;
nxt[idx] = head;
head = idx++;
}
void add_after_k(int k, int v) {
val[idx] = v;
nxt[idx] = nxt[k];
nxt[k] = idx++;
}
void del_after_k(int k) {
nxt[k] = nxt[nxt[k]];
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
init();
int m;
if (!(cin >> m)) return 0;
while (m--) {
char op;
cin >> op;
if (op == 'H') {
int x; cin >> x;
add_to_head(x);
} else if (op == 'D') {
int k; cin >> k;
if (k == 0) head = nxt[head]; // 删除头节点
else del_after_k(k - 1); // 第 k 个插入的数物理下标为 k-1
} else { // op == 'I'
int k, x; cin >> k >> x;
add_after_k(k - 1, x);
}
}
for (int i = head; i != -1; i = nxt[i]) {
cout << val[i] << " ";
}
cout << "\n";
return 0;
}
3. 动态链表的实现
动态链表是利用 C++ 的结构体 struct 与指针 * 构建的，是软件开发和标准库（STL）中链表的正统形态。
3.1 结构体定义
struct Node {
int val; // 数据域
Node* nxt; // 指针域，指向下一个 Node 实例
// 构造函数，便于快速初始化节点
Node(int v) : val(v), nxt(nullptr) {}
};
Node*表示“指向 Node 类型对象的指针”。nullptr是 C++11 引入的空指针字面量，相比传统的NULL更安全，能避免隐式转换为整型的歧义。
3.2 内存动态开辟
我们使用关键字 new 在程序的堆（Heap）内存中申请空间，并用 delete 进行物理释放：
Node* p = new Node(10); // 在堆上创建一个值为 10 的节点，并用指针 p 指向它
// 使用完毕后需物理释放，防止内存泄漏
delete p;
3.3 动态链表核心操作代码示例
#include <iostream>
#include <map>
using namespace std;
struct Node {
int val;
Node* nxt;
Node(int v) : val(v), nxt(nullptr) {}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
Node* head = nullptr;
map<int, Node*> mp; // 建立第 k 个插入的数与物理节点指针的映射
int cnt = 0;
int m;
if (!(cin >> m)) return 0;
while (m--) {
char op;
cin >> op;
if (op == 'H') {
int x; cin >> x;
Node* cur = new Node(x);
cur->nxt = head;
head = cur;
cnt++;
mp[cnt] = cur;
} else if (op == 'D') {
int k; cin >> k;
if (k == 0) {
if (head) {
Node* tmp = head;
head = head->nxt;
delete tmp; // 物理释放
}
} else {
Node* p = mp[k];
if (p && p->nxt) {
Node* tmp = p->nxt;
p->nxt = tmp->nxt;
delete tmp;
}
}
} else { // op == 'I'
int k, x; cin >> k >> x;
Node* p = mp[k];
if (p) {
Node* cur = new Node(x);
cur->nxt = p->nxt;
p->nxt = cur;
cnt++;
mp[cnt] = cur;
}
}
}
// 遍历输出
Node* cur = head;
while (cur) {
cout << cur->val << " ";
cur = cur->nxt;
}
cout << "\n";
// 统一垃圾回收释放内存
while (head) {
Node* tmp = head;
head = head->nxt;
delete tmp;
}
return 0;
}
- 时间复杂度：因为引入了
std::map进行位置检索，单次操作包含 $O(\log N)$ 复杂度。若要追求极限 $O(1)$，可用静态分配指针数组替代map建立映射。
4. 常见链表变体
4.1 双向链表 (Doubly Linked List)
单向链表无法反向移动，若已知节点指针 p 欲删除该节点，单向链表必须从头遍历以寻找其前驱。双向链表通过增加一个指向前驱的指针 prev（或 prv）完美解决了这一痛点。
4.1.1 静态双向链表实现
需要额外维护一个前驱指针数组 prv[]：
// 增加 prv[] 维护前驱
// 在已知索引 p 节点后插入值为 v 的新节点
void add(int p, int v) {
val[idx] = v;
// 1. 新节点指向后继，后继指向新节点
nxt[idx] = nxt[p];
prv[nxt[p]] = idx;
// 2. 前驱指向新节点，新节点指向前驱
nxt[p] = idx;
prv[idx] = p;
idx++;
}
// 删除索引为 p 的节点（无需知道其前驱）
void del(int p) {
nxt[prv[p]] = nxt[p];
prv[nxt[p]] = prv[p];
}
4.1.2 动态双向链表实现
struct Node {
int val;
Node *nxt, *prv;
Node(int v) : val(v), nxt(nullptr), prv(nullptr) {}
};
// 删除指针 p 所指的节点
void del_node(Node* p) {
if (p->prv) p->prv->nxt = p->nxt;
if (p->nxt) p->nxt->prv = p->prv;
delete p;
}
4.2 循环链表 (Circular Linked List)
循环链表的尾节点的 next 不再指向空，而是指向头节点 head，从而在逻辑和结构上闭合成环。
* 特点：从任意节点出发都可以遍历整个环形链表。
* 注意点：遍历结束判定条件不再是 p == nullptr，而是当前节点重新回到起点 p->next == head。
4.3 经典例题选讲
例题 1：约瑟夫问题 (Josephus Problem)
-
问题描述： $N$ 个人围成一圈，从 1 号开始报数，报到 $M$ 的人出局，其下一个人重新从 1 开始报数，直到所有人出局。求出局序列。
-
题解思路： 此题是循环链表的绝对经典应用，使用环形结构进行模拟非常直观。
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m;
if (!(cin >> n >> m)) return 0;
// 静态数组模拟循环链表
vector<int> nxt(n + 1);
for (int i = 1; i <= n; ++i) {
nxt[i] = (i % n) + 1; // 形成闭环：1->2->3...->n->1
}
int cur = n; // cur 指向当前报数人前驱，开始时 1 号报数，故前驱设为 n
for (int i = 0; i < n; ++i) {
// 走 m-1 步找到要出局的人的前一个节点
for (int j = 0; j < m - 1; ++j) {
cur = nxt[cur];
}
int p = nxt[cur]; // p 为当前需要出局的人
cout << p << " ";
// 从环中切断、移除 p 节点
nxt[cur] = nxt[p];
}
cout << "\n";
return 0;
}
- 时间复杂度：共出局 $N$ 个节点，每次移动 $M-1$ 步，总复杂度为 $O(N \times M)$。
例题 2：序列维护问题（双向动态链表完整实现）
- 问题描述： 给定长度为 $n$（$n \le 1000$）的初始整数序列，支持 $m$（$m \le 1000$）个在线操作：
1 i：询问序列中第 $i$ 个元素的值。2 i v：在序列中第 $i$ 个元素的前面加入新元素 $v$。3 i：删除序列中的第 $i$ 个元素。
#include <iostream>
#include <cstdio>
using namespace std;
struct node {
int val;
node *prev, *next;
node(int v) : val(v), prev(nullptr), next(nullptr) {}
} *head = nullptr;
int n, m;
// 查找并返回第 i 个（从 0 开始计）节点的值
int find_node(node *head, int i) {
node *cur = head;
while (i-- > 0 && cur) {
cur = cur->next;
}
return cur ? cur->val : -1;
}
// 在第 i 个节点前面插入值为 v 的新节点
void insert_node(node* &head, int i, int v) {
node *t = new node(v);
if (i == 0) { // 在表头插入
if (head == nullptr) {
head = t;
} else {
t->next = head;
head->prev = t;
head = t;
}
return;
}
node *cur = head;
// 遍历到对应位置前驱
while (--i > 0 && cur->next) {
cur = cur->next;
}
t->prev = cur;
t->next = cur->next;
if (cur->next) cur->next->prev = t;
cur->next = t;
}
// 删除第 i 个节点
void del_node(node* &head, int i) {
if (i == 0) { // 删除头节点
node *t = head;
head = head->next;
if (head) head->prev = nullptr;
delete t;
return;
}
node *cur = head;
while (i-- > 0 && cur) {
cur = cur->next;
}
if (!cur) return;
if (cur->next) cur->next->prev = cur->prev;
if (cur->prev) cur->prev->next = cur->next;
delete cur;
}
int main() {
if (scanf("%d", &n) != 1) return 0;
for (int i = 0; i < n; i++) {
int v; scanf("%d", &v);
if (head == nullptr) head = new node(v);
else insert_node(head, i, v); // 依次在尾部追加建立链表
}
if (scanf("%d", &m) != 1) return 0;
for (int i = 0; i < m; i++) {
int opt, x, v;
scanf("%d %d", &opt, &x);
if (opt == 1) {
printf("%d\n", find_node(head, x - 1));
} else if (opt == 2) {
scanf("%d", &v);
insert_node(head, x - 1, v);
} else if (opt == 3) {
del_node(head, x - 1);
}
}
return 0;
}
5. 小结
5.1 链表与数组的性能全方位对比
| 特性 | 数组 (Array) | 链表 (Linked List) |
|---|---|---|
| 内存布局 | 物理上连续，紧凑存储 | 离散存储在堆或数组空闲处 |
| 空间分配 | 编译期或初始化时固定大小 | 运行时根据需要动态扩展 |
| 随机访问效率 | 极高：$O(1)$ | 较低：$O(N)$（需从头遍历） |
| 头部插入与删除 | 较低：$O(N)$（需整体搬移） | 极高：$O(1)$（只需改动头指针） |
| 尾部插入与删除 | 极高：$O(1)$ | 单向链表 $O(N)$，双向或带尾指针 $O(1)$ |
| 中间已知位置插入删除 | 较低：$O(N)$ | 极高：$O(1)$ |
5.2 链表学习与避坑建议
- 画图辅助：由于链表逻辑性极强，纸笔是攻克链表最好的工具。编写涉及指针修改的代码时，先在草稿纸上画出节点图，用箭头标识指针修改前后的指向变化。
- 警惕指针越界与野指针：在进行
cur->next->prev这种长距离引用的修改时，必须先保证cur与cur->next本身不为空，否则程序会引发段错误（Segmentation Fault）崩溃。 - 重视边界条件特判：
- 链表当前为空链表
- 链表仅含有单一节点
- 操作位置在头节点处
- 操作位置在尾节点处
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
