世界的尽头

双链表

双链表中的每个节点除了保存数据，还会同时保存前驱节点和后继节点的位置。因此，与单链表相比，双链表可以在 $O(1)$ 时间内完成以下操作：

在已知节点的左侧或右侧插入新节点；
删除一个已知节点；
从任意节点向左或向右移动。

在 ACM 模式中，如果操作次数已经确定，常用三个数组模拟双链表：

int e[N];  // e[i]：编号为 i 的节点保存的值
int l[N];  // l[i]：编号为 i 的节点的左邻节点
int r[N];  // r[i]：编号为 i 的节点的右邻节点
int idx;   // 下一个可以使用的节点编号

数组模拟不需要频繁申请和释放内存，节点编号也不会因为删除操作而改变，适合处理按照“第几个插入的节点”进行操作的题目。

使用两个哨兵节点

为了统一链表首尾的插入和删除操作，可以设置两个不保存有效数据的哨兵节点：

0 表示左端点；
1 表示右端点；
真正的数据节点从 2 开始编号。

初始化时让两个哨兵互相连接：

void init() {
  r[0] = 1;
  l[1] = 0;
  idx = 2;
}

空链表可以表示为：

0（左哨兵） <-> 1（右哨兵）

这样一来，在链表最左侧插入就是在节点 0 的右侧插入，在最右侧插入就是在节点 1 的左邻节点右侧插入，不需要额外判断链表是否为空。

核心操作

在节点 `k` 的右侧插入

假设节点 k 原来的右邻节点是 r[k]，插入新节点 idx 后，需要建立四条连接：

k <-> idx <-> r[k]

代码如下：

void add(int k, int x) {
  e[idx] = x;
  l[idx] = k;
  r[idx] = r[k];
  l[r[k]] = idx;
  r[k] = idx;
  idx++;
}

如果要在节点 k 的左侧插入，只需要在它原来的左邻节点 l[k] 右侧插入：

add(l[k], x);

删除节点 `k`

删除节点时，不需要移动数组中的元素，只要让它的左右邻居直接连接：

l[k] <-> k <-> r[k]
 
变为
 
l[k] <------> r[k]

void remove_node(int k) {
  r[l[k]] = r[k];
  l[r[k]] = l[k];
}

被删除节点原来的数据仍然留在数组中，但它已经不在从左哨兵到右哨兵的有效链上，因此不会影响后续操作。

下标映射

如果题目中的 k 表示“第 k 个插入的节点”，需要将它转换成数组中的真实编号。

由于 0 和 1 已经被哨兵占用，第一个插入的节点编号为 2，所以：

\text{第 } k \text{ 个插入的节点编号} = k + 1

需要特别注意：这里的 k 是插入顺序，不是节点在当前链表中的位置。即使某个节点被删除，后续节点的编号也不会改变。

五类操作可以统一转换为：

操作	含义	实现
`L x`	在最左侧插入 `x`	`add(0, x)`
`R x`	在最右侧插入 `x`	`add(l[1], x)`
`D k`	删除第 `k` 个插入的节点	`remove_node(k + 1)`
`IL k x`	在第 `k` 个插入的节点左侧插入 `x`	`add(l[k + 1], x)`
`IR k x`	在第 `k` 个插入的节点右侧插入 `x`	`add(k + 1, x)`

正确性说明

初始化后，r[0] = 1 且 l[1] = 0，空链表的左右连接一致。

插入节点时，新节点的左指针指向 k，右指针指向 k 原来的右邻节点；随后再把这两个相邻节点指回新节点。因此插入后，对链上的每一对相邻节点 a 和 b，仍然有 r[a] = b 且 l[b] = a。

删除节点时，节点 k 的左邻节点直接指向它的右邻节点，右邻节点也直接指向它的左邻节点。除这两个连接外，链表的其他连接都没有改变。因此删除后，剩余节点的先后顺序保持不变，双向连接仍然一致。

由此可知，只要每次操作的目标节点有效，所有插入和删除操作都会维护一个正确的双链表。

AcWing 827：双链表

题意

维护一个初始为空的双链表，依次执行以下操作：

L x：在链表最左侧插入 x；
R x：在链表最右侧插入 x；
D k：删除第 k 个插入的节点；
IL k x：在第 k 个插入的节点左侧插入 x；
IR k x：在第 k 个插入的节点右侧插入 x。

完成所有操作后，从左到右输出链表中的元素。

完整代码

#include <iostream>
 
using namespace std;
 
const int N = 100010;
 
int e[N], l[N], r[N];
int idx;
 
void init() {
  r[0] = 1;
  l[1] = 0;
  idx = 2;
}
 
// 在节点 k 的右侧插入值为 x 的新节点
void add(int k, int x) {
  e[idx] = x;
  l[idx] = k;
  r[idx] = r[k];
  l[r[k]] = idx;
  r[k] = idx;
  idx++;
}
 
// 删除节点 k
void remove_node(int k) {
  r[l[k]] = r[k];
  l[r[k]] = l[k];
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  init();
 
  int m;
  cin >> m;
 
  while (m--) {
    string op;
    int k, x;
    cin >> op;
 
    if (op == "L") {
      cin >> x;
      add(0, x);
    } else if (op == "R") {
      cin >> x;
      add(l[1], x);
    } else if (op == "D") {
      cin >> k;
      remove_node(k + 1);
    } else if (op == "IL") {
      cin >> k >> x;
      add(l[k + 1], x);
    } else {
      cin >> k >> x;
      add(k + 1, x);
    }
  }
 
  for (int i = r[0]; i != 1; i = r[i]) {
    cout << e[i] << ' ';
  }
  cout << '\n';
 
  return 0;
}

复杂度分析

初始化的时间复杂度为 $O(1)$ ；
每次插入或删除只修改常数个指针，时间复杂度为 $O(1)$ ；
执行 $m$ 次操作的总时间复杂度为 $O(m)$ ；
最后遍历链表的时间复杂度为 $O(n)$ ，其中 $n$ 是链表中剩余节点数；
三个数组最多保存 $m$ 个数据节点，空间复杂度为 $O(m)$ 。

常见错误

没有预留两个哨兵节点：真实节点必须从 idx = 2 开始编号。
混淆题目编号和数组编号：第 k 个插入的节点对应 k + 1，不是 k。
把 k 当成当前第 k 个节点：删除不会使后续节点重新编号，题目中的 k 始终对应插入顺序。
更新顺序错误：执行 r[k] = idx 后，r[k] 已经不再是原来的右邻节点，因此要先保存新节点的左右关系并更新 l[r[k]]。
最右侧插入位置错误：右哨兵是 1，最右侧数据节点是 l[1]，所以应调用 add(l[1], x)。
遍历时输出哨兵：应从 r[0] 开始，在到达节点 1 时停止。
删除后复用编号：数组模拟通常只递增 idx，不要因为删除节点而回退或复用编号。

2-双链表

双链表