本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-08 20:37:47
链表
一、链表基础知识
1. 链表特性
- 动态数据结构，节点通过指针连接
- 支持O(1)时间的插入/删除操作
- 不支持随机访问（访问效率O(n)）
- 两种常见实现方式：数组模拟（静态链表）、STL list（双向链表）
2. 链表类型对比
| 实现方式 | 内存管理 | 访问效率 | 插入效率 | 竞赛适用性 |
|---|---|---|---|---|
| 数组模拟链表 | 预分配 | O(1) | O(1) | 推荐 |
| STL list | 动态分配 | O(n) | O(1) | 特殊场景 |
二、数组模拟链表
1. 单向链表模板
const int MAXN = 1e6+5;
struct Node {
int val;
int next;
} node[MAXN];
int idx; \/\/ 当前可用节点索引
\/\/ 初始化
void init() {
node[0].next = -1; \/\/ 头节点
idx = 1;
}
\/\/ 在pos节点后插入新节点
void insert(int pos, int x) {
node[idx].val = x;
node[idx].next = node[pos].next;
node[pos].next = idx++;
}
\/\/ 删除pos节点的后继节点
void remove(int pos) {
node[pos].next = node[node[pos].next].next;
}
2. 双向链表模板
const int MAXN = 1e6+5;
struct Node {
int val;
int prev, next;
} node[MAXN];
int idx;
void init() {
node[0].next = 1; \/\/ 头节点
node[1].prev = 0; \/\/ 尾节点
idx = 2;
}
\/\/ 在pos节点右侧插入
void insert(int pos, int x) {
node[idx] = {x, pos, node[pos].next};
node[node[pos].next].prev = idx;
node[pos].next = idx++;
}
\/\/ 删除pos节点
void remove(int pos) {
node[node[pos].prev].next = node[pos].next;
node[node[pos].next].prev = node[pos].prev;
}
三、STL list应用
1. 基本操作
#include <list>
using namespace std;
list<int> lst;
list<int>::iterator it;
lst.push_back(x); \/\/ 尾部插入
lst.push_front(x); \/\/ 头部插入
lst.pop_back(); \/\/ 删除尾部
lst.pop_front(); \/\/ 删除头部
it = lst.begin(); \/\/ 获取起始迭代器
advance(it, k); \/\/ 迭代器移动k步
lst.insert(it, x); \/\/ 在迭代器位置插入
lst.erase(it); \/\/ 删除迭代器指向元素
四、基础例题实现
例题1：洛谷P1160 队列安排
题目描述：实现双向链表操作，支持：
- 将i号同学插入到k号同学左边/右边
- 删除指定同学
数组模拟实现
#include <iostream>
using namespace std;
const int MAXN = 1e5+5;
struct Node { int prev, next; } node[MAXN];
bool exist[MAXN];
void init() {
node[0].next = 1;
node[1].prev = 0;
}
void insert(int k, int x, int pos) { \/\/ pos:0左 1右
if(pos == 0) {
node[x].prev = node[k].prev;
node[x].next = k;
node[node[k].prev].next = x;
node[k].prev = x;
} else {
node[x].prev = k;
node[x].next = node[k].next;
node[node[k].next].prev = x;
node[k].next = x;
}
exist[x] = true;
}
void remove(int x) {
if(!exist[x]) return;
node[node[x].prev].next = node[x].next;
node[node[x].next].prev = node[x].prev;
exist[x] = false;
}
STL list实现
#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;
unordered_map<int, list<int>::iterator> mp;
list<int> lst;
int main() {
lst.push_back(1);
mp[1] = lst.begin();
int n, k, p, m, x;
cin >> n;
for(int i=2; i<=n; ++i) {
cin >> k >> p;
auto it = mp[k];
if(p == 1) ++it;
mp[i] = lst.insert(it, i);
}
\/\/ ...后续删除操作类似...
return 0;
}
例题2：洛谷P1996 约瑟夫问题
题目描述：n个人围成环，从第1个开始报数，数到m的人出列
数组模拟实现
int cur = 0;
for(int i=0; i<n; ++i){
for(int j=1; j<m; ++j)
cur = node[cur].next;
cout << node[cur].next << " ";
remove(cur);
cur = node[cur].next;
}
STL list实现
list<int> lst;
for(int i=1; i<=n; ++i) lst.push_back(i);
auto it = lst.begin();
while(!lst.empty()){
for(int i=1; i<m; ++i){
++it;
if(it == lst.end()) it = lst.begin();
}
cout << *it << " ";
it = lst.erase(it);
if(it == lst.end() && !lst.empty())
it = lst.begin();
}
五、进阶练习题
- 洛谷P2058 海港（STL list维护时间窗口）
- Codeforces 706D - Vasiliy's Multiset（双向链表维护有序集合）
- AtCoder ABC237E - Skiing（链表优化BFS）
- 洛谷P4001 [ICPC-Beijing 2006]狼抓兔子（双向链表维护平面图）
- Codeforces 1154E - Two Teams（双向链表快速删除）
六、使用技巧
数组模拟常用优化：
- 使用「索引0」作为头节点
- 预先分配足够空间（1e6级别）
- 用exist数组标记有效节点
STL list注意事项：
- 迭代器失效问题
- 结合unordered_map实现快速查找
- 谨慎处理空链表和边界情况
性能对比：
- 数组模拟：访问O(1)，适合频繁修改
- STL list：代码简洁，适合简单操作
七、常见错误
- 数组模拟时忘记更新相邻节点的指针
- STL list在循环中错误处理迭代器
- 没有正确处理空链表的情况
- 数组模拟时未初始化头尾节点
- 时间复杂度误判（多次遍历链表）
鲁ICP备2025150228号