链表
链表和数组相似，都是存储一系列元素，但是相比于数组的一次性申请所有空间不同，链表是生成一个结点，申请一块空间，即用时申请。链表和数组的另一个不同点是链表不支持随机访问，链表的每次访问都是从表头开始的。
链表的一个优势是它支持在任意位置插入和删除！
根据指针方向的不同，链表可以分为：
- 单链表：每个结点只保存指向下一个结点的指针，只能从头向后遍历；
- 双链表：每个结点同时保存前驱与后继，可以双向遍历，代价是多一个指针域；
- 循环链表：尾结点的指针指向头结点，首尾相连成环（分为单循环链表、双循环链表）；
- 静态链表：用数组下标模拟指针（如
存值、 存下一个结点的下标），竞赛中常用，避免动态内存分配的开销。
链表与数组的对比：
| 操作 | 数组 | 链表 |
|---|---|---|
| 随机访问 | ||
| 头部插入/删除 | ||
| 任意位置插入/删除 | ||
| 空间申请 | 一次性申请连续空间 | 用时申请（静态链表为预分配） |
因此链表适合"频繁插入删除、很少随机访问"的场景，例如实现栈与队列、图的邻接表、哈希表的拉链法等；数组则适合随机访问频繁的场景。
单链表
cpp
// 结构体模拟
struct Node {
int value, next;
} node[N];
int head, idx;
// 数组模拟
// head 表示头结点的下标
// e[i] 表示结点i的值
// ne[i] 表示结点i的下一个结点的下标
// idx 表示当前可用的空间
int head, e[N], ne[N], idx;
// 初始化
void init() {
head = -1;
idx = 0;
}
// 头插法
void insert_head(int x) {
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
// 在下标为k的结点后插入
void insert_k(int k, int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
// 删除下标为k的结点的后一个结点
void remove_k(int k) {
ne[k] = ne[ne[k]];
}AcWing 826. 单链表
题目描述
实现一个单链表，链表初始为空，支持三种操作：
- 向链表头插入一个数；
- 删除第
个插入的数后面的数； - 在第
个插入的数后插入一个数。
现在要对该链表进行
注意：题目中第
输入格式
第一行包含整数
接下来
H x，表示向链表头插入一个数。 D k，表示删除第个插入的数后面的数（当 为 时，表示删除头结点）。 I k x，表示在第个插入的数后面插入一个数 （此操作中 均大于 ）。
输出格式
共一行，将整个链表从头到尾输出。
数据范围
输入样例
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6输出样例
6 4 6 5示例代码
cpp
int main() {
int m;
cin >> m;
init();
while(m --) {
char op[2];
int k, x;
scanf("%s", op);
if(op[0] == 'H'){
cin >> x;
insert_head(x);
}
if(op[0] == 'D'){
cin >> k;
if(!k) head = ne[head];
else remove_k(k - 1);
}
if(op[0] == 'I') {
cin >> k >> x;
insert_k(k - 1, x);
}
}
for(int i = head; i != -1; i = ne[i]) {
cout << e[i] << " ";
}
return 0;
}双链表
- 思考：如何快速访问当前结点的前一个结点？
cpp
// 结构体模拟
struct Node {
int value, prev, next;
} node[N];
int head, tail, idx;
void init() {
idx = 2;
head = 1, tail = 2;
node[head].next = tail;
node[tail].prev = head;
}
// 数组模拟
int e[N], l[N], r[N], idx;
void init() {
r[0] = 1;
l[1] = 0;
idx = 2;
}
// 在k结点的右边插入
void insert_k_right(int k, int x) {
e[idx] = x;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx;
idx++;
}
// 在k结点的左边插入
void insert_k_left(int k, int x) {
insert_k_right(l[k], x);
}
// 删除k结点
void remove_k(int k) {
l[r[k]] = l[k];
r[l[k]] = r[k];
}AcWing 827. 双链表
题目描述
实现一个双链表，双链表初始为空，支持
- 在最左侧插入一个数；
- 在最右侧插入一个数；
- 将第
个插入的数删除； - 在第
个插入的数左侧插入一个数； - 在第
个插入的数右侧插入一个数
现在要对该链表进行
注意：题目中第
输入格式
第一行包含整数
接下来
L x，表示在链表的最左端插入数。 R x，表示在链表的最右端插入数。 D k，表示将第个插入的数删除。 IL k x，表示在第个插入的数左侧插入一个数。 IR k x，表示在第个插入的数右侧插入一个数。
输出格式
共一行，将整个链表从左到右输出。
数据范围
输入样例
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2输出样例
8 7 7 3 2 9示例代码
cpp
int main() {
int m;
cin >> m;
init();
while(m --) {
string op;
int k, x;
cin >> op;
if(op == "L") {
cin >> x;
insert_k_right(0, x);
} else if(op == "R") {
cin >> x;
insert_k_right(l[1], x);
} else if(op == "D") {
cin >> k;
// 为什么是k + 1呢？因为第k个插入的节点的下标是k + 1，idx 从 2 开始
remove_k(k + 1);
} else if(op == "IL") {
cin >> k >> x;
insert_k_right(l[k + 1], x);
} else if(op == "IR") {
cin >> k >> x;
insert_k_right(k + 1, x);
} else {}
}
for(int i = r[0]; i != 1; i = r[i]) {
cout << e[i] << " ";
}
cout << endl;
return 0;
}