数组模拟双向链表：洛谷 P1160 队列安排 O(1) 插入删除详解

第一次在洛谷上看到 P1160 这道“队列安排”，很多人第一反应都是：“这不就是数组插插删删，最后输出一下吗？”然后高高兴兴用 vector 写完，一提交，超时。再回头看一眼数据范围，n 和 m 都是十万级别，vector 的 insert 和 erase 在中间操作是 O(n) 的，最坏情况下每次插入都要挪动上万个元素，总复杂度直接爆炸到 10^10 级别，TLE 一点都不冤。

这题真正考的其实不是“队列”，而是“链表”——准确点说，是用数组模拟双向链表，把每次插入和删除都压到 O(1)。今天我就把这个思路从头到尾拆一遍，把完整 AC 代码、指针修改顺序、还有几个我当年踩过的坑都拿出来说说。不管你是刚开始刷洛谷的新手，还是已经会链表但老在细节上 WA 的同学，这篇应该都能帮到你。

1. 题目到底在干什么：先把“队列安排”啃透

1.1 输入格式与操作拆解

题目流程是这样的：一开始队列里只有 1 号同学。接下来 2 号到 n 号同学依次入队，每次输入两个整数 k 和 p，意思是把当前编号为 i 的同学插到编号为 k 的同学左边（p=0）或者右边（p=1）。注意输入的第 i 行对应的是 i 号同学，这行里的 k 一定小于 i，也就是说参照对象一定是已经入队的同学。

插入全部完成后，再输入一个整数 m，接下来有 m 行，每行一个整数 x，表示把 x 号同学从队列中移走。如果 x 已经不在队列里，就忽略这次操作。最后要求按从左到右的顺序输出还在队列里的同学编号。

这就是一个典型的“中间插入 + 任意删除 + 顺序输出”问题。关键在于 n 和 m 都可以到 100000，如果用普通数组存队列，插入到中间位置就得把后面所有元素整体后移，删除也一样，单次操作最坏 O(n)，算上 n-1 次插入和 m 次删除，整体复杂度是 O((n+m)×n)，拿 1e5 的数据去跑，基本没有活路。

1.2 为什么数组直接搞不定

有人可能会说：“我用 vector 的 insert 和 erase 不就行了？”vector 的 insert 在头部或中间插入，确实会帮我们移动元素，但它底层仍然是数组拷贝，复杂度是 O(n)。假设每次都往队头插，第二次插入要挪 1 个元素，第三次要挪 2 个……到第 n 次要挪 n-2 个，累计下来就是 O(n²)。这还只是插入，后面还有 m 次删除，删除中间元素同样要搬移。

所以这道题的本质就是：要在一个序列中频繁地“知道某个编号的左右邻居是谁，并修改它们”，这正是链表的天然优势。但 C 语言的 struct 链表需要动态分配节点，写起来啰嗦，还容易内存泄漏；C++ 的 STL list 虽然能用，但竞赛里用它维护“按编号删除”还得额外存迭代器，代码反而不清爽。

于是就有了最经典的解法：用两个数组 l[i] 和 r[i] 分别记录编号 i 左边和右边的人，用 0 表示空。这就是“数组模拟双向链表”。

2. 核心思路：用数组模拟双向链表，O(1)完成插入和删除

2.1 为什么选“前驱/后继”数组而不是 STL list

我先说说为什么不直接用 list。STL 的 list 确实是双向链表，插入删除也是 O(1)，但它的问题是节点动态分配，常数大；而且题目要求按编号删除某个同学，如果用 list 的迭代器来定位节点，则需要额外维护一个迭代器数组 iter[i]，删除的时候才能 O(1) 找到对应节点。否则，你还得从 head 开始遍历找编号，那样删除一次就是 O(n)。

相比之下，数组模拟双向链表是这样的：

• l[i] 表示编号 i 左边同学的编号，没有则为 0；
• r[i] 表示编号 i 右边同学的编号，没有则为 0；
• vis[i] 记录编号 i 是否已经被删除。

这样我们不仅能用 O(1) 找到任意编号的左右邻居，还能直接用编号访问节点，不需要遍历查找。这种静态链表的方式内存连续，cache 友好，实际运行速度比 STL list 快很多，代码也更好调试。

2.2 插入操作的推导：先接新节点，再拆旧连接

假设当前编号为 i 的同学要插入到编号为 k 的同学左边。也就是说，i 会成为 k 的左邻居。设原来 k 的左邻居是 L = l[k]，那么插入后：

• i 的右边是 k；
• i 的左边是原来的 L；
• 如果 L 不为 0，那么 L 的右边要变成 i；
• k 的左边要变成 i。

写成代码就是：

l[i] = l[k]; r[i] = k; if (l[k]) r[l[k]] = i; l[k] = i;

注意这里有个很关键的细节：如果 k 原来没有左邻居，也就是 l[k] == 0，说明 k 是当前队列的队头，那么 i 插入后就会成为新的队头。所以当 l[k] 为 0 时，我们还得更新 head 为 i。

再来看插入到 k 的右边。设 k 原来的右邻居是 R = r[k]，那么插入后：

• i 的左边是 k；
• i 的右边是原来的 R；
• 如果 R 不为 0，那么 R 的左边要变成 i；
• k 的右边要变成 i。

代码：

l[i] = k; r[i] = r[k]; if (r[k]) l[r[k]] = i; r[k] = i;

插入到 k 的右边不会改变队头，因为队头始终是最左边的元素，而新节点插在了 k 的右边。

这里有一个非常容易踩的雷：修改指针的顺序。如果你先写 r[k] = i，再取原来的 r[k]，那原来的右邻居就丢了。所以一定不要提前破坏老节点的指针。我自己的口诀是“先让新节点 i 的前驱后继指向正确，再修正老节点的连接”。

2.3 删除操作的正确姿势

删除编号为 x 的同学时，如果 vis[x] 已经为 true，说明这个人早就被删过了，直接忽略。

否则，先记录它的左邻居 L = l[x]，右邻居 R = r[x]。删除的本质就是让 L 和 R 直接相连，让 x 从链表中脱离：

• 如果 L 不为 0，那么 L 的右边变成 R；
• 如果 L 为 0，说明 x 是队头，删除后队头变成 R；
• 如果 R 不为 0，那么 R 的左边变成 L；
• 标记 vis[x] = true。

代码：

if (vis[x]) continue; int L = l[x], R = r[x]; if (L) r[L] = R; else head = R; if (R) l[R] = L; vis[x] = true;

这里不需要修改 x 自己的 l[x] 和 r[x]，因为它已经不在链表里了，之后只要保证不会再次访问它就行。

2.4 如何确定队头和最终输出

由于数组模拟链表没有一个“总起点”，我们必须用一个变量 head 记录当前最左边的人是谁。初始时 head = 1，因为队列里只有 1 号。

插入时，只有当“把新节点插入到某个节点的左边，且这个节点本来就是队头”时，head 才会被更新成新节点。插入到右边永远不改变 head。

删除时，如果删除的节点是队头，head 就要变成它的右邻居；如果删除的不是队头，head 不变。

最后输出时，只需要从 head 开始，一路沿着 r[cur] 遍历到 0 为止，即可得到从左到右的完整队列。

这里补充一个更省心的技巧：可以引入一个 0 号哨兵节点，让 0 始终作为虚拟队头，它的右边是真正队头。这样“更新队头”的操作就统一变成“修改 r[0]”，不需要在插入和删除里特判 head。实际编码时，哨兵写法往往更简洁，不容易漏条件。下面我会给出一个带哨兵版本的代码，方便对比。

3. 代码实现：从零写完并 AC

3.1 无哨兵版：用 head 变量维护队头

下面这版是很多人的首选写法，逻辑直观，没有额外哨兵：

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int l[MAXN], r[MAXN]; bool vis[MAXN]; int main() { int n; scanf("%d", &n); // 初始只有 1 号 l[1] = r[1] = 0; int head = 1; for (int i = 2; i <= n; ++i) { int k, p; scanf("%d%d", &k, &p); if (p == 0) { // 将 i 插到 k 的左边 l[i] = l[k]; r[i] = k; if (l[k]) { r[l[k]] = i; } else { head = i; // k 本来是队头，i 变成新的队头 } l[k] = i; } else { // 将 i 插到 k 的右边 l[i] = k; r[i] = r[k]; if (r[k]) { l[r[k]] = i; } r[k] = i; } } int m; scanf("%d", &m); while (m--) { int x; scanf("%d", &x); if (vis[x]) continue; int L = l[x], R = r[x]; if (L) { r[L] = R; } else { head = R; // 删除的是队头 } if (R) { l[R] = L; } vis[x] = true; } for (int cur = head; cur != 0; cur = r[cur]) { printf("%d ", cur); } printf("\n"); return 0; }

这个代码在洛谷上可以直接 AC。唯一的小问题是输出时会多一个末尾空格，但洛谷对行末空格不敏感，所以没有问题。如果你有洁癖，可以先用一个变量统计已经输出的数量，在数字之间加空格。

3.2 带哨兵版：用 r[0] 统一维护队头

再贴一个带 0 号哨兵的写法。它的核心思想是：让 0 永远作为虚拟队头，真正的队头是 r[0]。这样插入到队头左边时，我们只需要把 r[0] 更新成新节点；删除队头时，也只需要修改 r[0]。

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int l[MAXN], r[MAXN]; bool vis[MAXN]; int main() { int n; scanf("%d", &n); // 0 作为虚拟头节点，初始时队头是 1 l[1] = 0; r[1] = 0; r[0] = 1; for (int i = 2; i <= n; ++i) { int k, p; scanf("%d%d", &k, &p); if (p == 0) { // 插入到 k 的左边 l[i] = l[k]; r[i] = k; if (l[k]) { r[l[k]] = i; } else { r[0] = i; // k 是队头，i 成为新的队头 } l[k] = i; } else { // 插入到 k 的右边 l[i] = k; r[i] = r[k]; if (r[k]) { l[r[k]] = i; } r[k] = i; } } int m; scanf("%d", &m); while (m--) { int x; scanf("%d", &x); if (vis[x]) continue; int L = l[x], R = r[x]; if (L) { r[L] = R; } else { r[0] = R; // x 是队头 } if (R) { l[R] = L; } vis[x] = true; } for (int cur = r[0]; cur != 0; cur = r[cur]) { printf("%d ", cur); } printf("\n"); return 0; }

对比之后你会发现，带哨兵版本在“更新队头”这件事上不需要 else 分支里的额外变量赋值，代码看起来更统一。我个人的建议是：初期练习用无哨兵版可以帮助理解指针变化；等你完全理解了，再切换到哨兵版，能减少很多边界条件的思考成本。

3.3 关键代码段逐行解释

以无哨兵版为例，核心就三步。

初始化：

l[1] = r[1] = 0; int head = 1;

1 号同学左右都没有人，所以左右指针都是 0。head 是队头，初始为 1。

插入到左边：

l[i] = l[k]; r[i] = k; if (l[k]) r[l[k]] = i; else head = i; l[k] = i;

第一步先让 i 的前驱指向 k 原来的左邻居，i 的后继指向 k。第二步判断 k 原来有没有左邻居：有的话，让它的右指针指向 i；没有的话，说明 k 是队头，i 顶替它成为新队头。最后把 k 的左指针指向 i。注意，最后一步一定要放在后面，因为前面要利用原来的 l[k] 做判断。

插入到右边：

l[i] = k; r[i] = r[k]; if (r[k]) l[r[k]] = i; r[k] = i;

同理，先让 i 的前驱指向 k，后继指向 k 原来的右邻居，再修改原右邻居的左指针，最后把 k 的右指针指向 i。因为插入到右边不会影响队头，所以这里不需要更新 head。

删除：

int L = l[x], R = r[x]; if (L) r[L] = R; else head = R; if (R) l[R] = L; vis[x] = true;

先用 L、R 把左右邻居存下来，防止后续修改相互干扰。如果 x 有左邻居，就让左邻居的右边变成 R；否则 x 是队头，队头变成 R。然后如果 x 有右邻居，让右邻居的左边变成 L。最后标记删除。这里之所以先保存 L、R，是因为如果 x 是队头，head 要赋新值，而此时还没有修改 R 的左指针，所以顺序不能乱。

4. 容易踩的坑：WA/TLE 现场复盘

4.1 TLE 的元凶：vector 的 insert/erase

这题最有迷惑性的地方就是：题目名字叫“队列安排”，所以很多人真用 queue，或者 deque。但 queue 只能队头出、队尾入，根本没法支持“插到某人左边右边”。deque 虽然支持中间插入，但复杂度同样是 O(n)。vector 的 insert 和 erase 更是重量级，数据小看起来没问题，数据一上 1e5 直接原形毕露。

如果拿这题去对比复杂度，可以看下面这个表：

看到 O(n²) 就应该本能地警惕。竞赛里只要看见 n 到 1e5，基本就要想 O(nlogn) 或 O(n) 的算法；如果出现了 O(n²)，那几乎必挂。

4.2 指针修改顺序错乱：经典 WA

很多人第一次写链表插入，容易写出类似这样的错误代码：

r[i] = r[k]; l[i] = k; r[k] = i; if (r[i]) l[r[i]] = i; // 这行其实用的还是原来的 r[k]？不，r[i] 已经保存了原 r[k]，所以也行

本质上，只要先把 i 的左右指针接好，再修改老节点，就不会丢链。但有人喜欢先改老节点，比如先执行 r[k] = i，然后想通过 r[r[k]] 找到原右邻居，这时候 r[k] 已经变成 i 了，r[r[k]] 就是 r[i]（刚被赋值为原右邻居？不一定，如果还没赋值就出错）。为了避免这种混乱，我建议严格按照下面顺序：

• 先设置新节点的 l[i] 和 r[i]；
• 再修改被插入位置原邻居的指针；
• 最后修改 k 的指针。

只要这个顺序不乱，任何插入都不会丢节点。

4.3 插入方向搞反：p=0 和 p=1 写反

p=0 表示插到左边，p=1 表示插到右边。写代码时，最好先把两种情况在纸上画一下，标清楚：

• 插到 k 左边：i 在 k 前面，所以 r[i] = k，l[i] = l[k]；
• 插到 k 右边：i 在 k 后面，所以 l[i] = k，r[i] = r[k]。

画出来再写，基本不会错。我见过不少人把这两种情况完全写反，结果样例能过，一提交 WA 得莫名其妙，就是因为样例里刚还左右对称。

4.4 输出时遇到已删除节点

如果你删除后没有正确把左右邻居连接起来，或者删除时没有标记 vis，输出时从 head 一路向右遍历，就可能碰到已经删除的节点。更可怕的是，如果删除的节点是队头，你没有更新 head，输出就会从错误的地方开始，甚至死循环。

所以删除操作里，更新 head 的那一行非常关键。很多 WA 都出在这里。建议写完删除逻辑后，自己造一个“删除队头”的测试数据手动跑一遍，确认 head 是否正确更新。

4.5 数组开小和初始化遗漏

N 最大是 100000，所以数组至少要开 100005。有些同学喜欢开 l[100000]、r[100000]，结果 i 到 100000 时直接越界，本地不报错，洛谷上 RE。另外，l[1]、r[1] 以及 head 的初始化不能漏。多组数据题还需要注意清空 vis，但本题只有一组，不需要考虑。

4.6 忽略删除指令可能重复

题目明确说，如果 x 已经不在队列中，则忽略本次指令。也就是说，同一个编号可能被删除两次。如果不加 vis 判断，第二次删除时会再次去操作 l[x] 和 r[x]，此时它们可能已经被清掉了，也可能指向一些奇怪的值，最终导致链表结构被破坏。

正确做法就是在删除前先判断 vis[x]。这是很多新手容易忽略的点，但恰恰是本题一个重要的细节。

5. 延伸：数组模拟链表在竞赛中的通用性

5.1 这个套路还能用在哪

数组模拟链表在算法竞赛里几乎是“基础生存技能”，绝不止 P1160 这一道题。

最典型的应用是图论里的“链式前向星”存图，它本质就是用一个 head 数组加 next 数组来模拟邻接链表，只不过每个节点存的是边的信息。另一个常见场景是约瑟夫问题，用数组模拟环形链表时，可以直接通过 nxt[i] 跳转，删除时只需修改相邻节点的指针，比循环数组方便很多。还有一些“模拟内存分配”“模拟进程调度”之类的题，如果用数组模拟链表，代码会非常简洁。

所以，学会这题的数组模拟双向链表，不只是会了一道题，而是掌握了一种通用的“静态链表”表示法。以后遇到需要 O(1) 插入删除，并且节点编号已知的问题，你都可以往这个方向想。

5.2 如果题目升级：插入后还要按排名查询

数组模拟链表虽然支持 O(1) 插入删除，但有个明显的短板：它不支持快速随机访问第 k 个元素。比如题目变成“在插入删除的过程中，随时查询当前队列第 k 个编号是谁”，链表就无能为力了，只能从头开始数，每次查询 O(n)。

这时候就需要更高级的数据结构了：可以用树状数组维护每个位置是否有元素，然后二分求第 k 个位置；也可以用平衡树（Treap/Splay）直接维护序列。如果你只是想快速知道“某个人左边是谁、右边是谁”，那链表依然是杀手级工具。

从这里也能看出，P1160 其实是一道很好的“数据结构启蒙题”。它的难度不高，但能帮你建立“链表思维”，让你意识到数组和链表是两种互补的存储方式，各有所长。

写在最后的个人体会

我当年第一次做这道题时，也是上来就 vector 一顿操作，样例过了，提交 TLE，整个人都傻了。后来老老实实打开题解区，看到数组模拟链表的思路才恍然大悟：原来 O(1) 的插入删除是靠“记录左右邻居”而不是“物理移动元素”。

现在我每次遇到“频繁中间插入删除”的题，第一反应就是链表；如果节点编号范围不大，就直接开数组模拟。这个习惯帮我解决了很多看似复杂的问题。

最后分享一个小技巧：写完链表操作后，一定自己手画一张图，把每一步指针变化标出来。尤其是指针修改顺序，画着画着就明白了。等你真的把这张图画通，P1160 的代码就再也不容易写错了。