一、算法描述
本篇文章讲述的数据结构是双链表，与上一篇文章一样是算法竞赛中常用的用数组模拟的双链表。
//用数组模拟的双链表定义如下：int e[N], l[N], r[N], idx;/*e[i]表示节点i的值l[i]表示节点i的左边一个节点r[i]表示节点i的右边一个节点idx表示当前用到了哪个节点*/- 跟单链表差不多。
- 多画图，多思考。
接下来介绍双链表的各种操作：初始化操作：
void init(){ r[0] = 1, l[1] = 0, idx = 2;}- 以 \(0\) 和 \(1\) 为两个界限，初始状态就是 \(0\) 的右边是 \(1\) ，\(1\) 的左边是 \(0\)。
- 要注意 \(idx\) 从 \(2\) 开始。
在第k个节点右边插入：
void add(int k, int x)//在第k个节点的右边插入一个新节点{ e[idx] = x; r[idx] = r[k], l[r[k]] = idx; l[idx] = k, r[k] = idx ++ ;}- \(e[idx] = x\) 表示新节点的值为 \(x\)。
- \(r[idx] = r[k], l[r[k]] = idx;\) 表示新节点的下一个节点指向 \(k\) 节点的下一个节点 \(p\) ，然后 \(p\) 的前一个节点又指向新节点。
- \(l[idx] = k, r[k] = idx;\) 表示新节点的左节点为 \(k\) ，\(k\) 节点的右节点指向 新节点。
- \(idx ++ ;\) 表示当前节点已经被用了，待使用的节点是下一个。
- 如何在左边插入呢？显然只需要修改一下参数即可：
add(l[k], x)。 - 建议画图来理解。
删除第 \(k\) 个节点：
void remove(int k){ r[l[k]] = r[k]; l[r[k]] = l[k];}- 数组删除不需要管内存泄漏的问题。
- 假设用 \(p, k, q\) 来表示三个节点：
- \(r[l[k]] = r[k];\) 表示 \(p\) 的右边指向 \(k\) 的右边，即 \(q\)。
- \(l[r[k]] = l[k];\) 表示 \(q\) 的左边指向 \(k\) 的左边，即 \(p\)。
- 画图来理解。
如何遍历呢？
for (int i = r[0]; i != 1; i = r[i])cout << e[i] << ' ';for (int i = l[1]; i != 0; i = l[i])cout << e[i] << ' ';- 第一行是从左往右遍历，第二行是从右往左遍历。
- \(0\) 和 \(1\) 是两个界限，所以是从 \(r[0]\) 和 \(l[1]\) 开始，而不是从 \(0\) 和 \(1\) 开始。
链表的问题都需要读者多画图、多思考，也要多复习。
二、题目描述
实现一个双链表，双链表初始为空，支持 \(5\) 种操作：
- 在最左侧插入一个数；
- 在最右侧插入一个数；
- 将第 \(k\) 个插入的数删除；
- 在第 \(k\) 个插入的数左侧插入一个数；
- 在第 \(k\) 个插入的数右侧插入一个数
现在要对该链表进行 \(M\) 次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第 \(k\) 个插入的数并不是指当前链表的第 \(k\) 个数。例如操作过程中一共插入了 \(n\) 个数，则按照插入的时间顺序，这 \(n\) 个数依次为：第 \(1\) 个插入的数，第 \(2\) 个插入的数，…第 \(n\) 个插入的数。
输入格式
第一行包含整数 \(M\)，表示操作次数。
接下来 \(M\) 行，每行包含一个操作命令，操作命令可能为以下几种：
L x，表示在链表的最左端插入数 \(x\)。R x，表示在链表的最右端插入数 \(x\)。D k，表示将第 \(k\) 个插入的数删除。IL k x，表示在第 \(k\) 个插入的数左侧插入一个数。IR k x，表示在第 \(k\) 个插入的数右侧插入一个数。
输出格式
共一行，将整个链表从左到右输出。
数据范围
\(1≤M≤100000\)
所有操作保证合法。
输入样例：
10R 7D 1L 3IL 2 10D 3IL 2 7L 8R 9IL 4 7IR 2 2 输出样例：
8 7 7 3 2 9 三、题目来源 AcWing算法基础课-827.双链表四、源代码
#include #include using namespace std;const int N = 100010;int e[N], l[N], r[N], idx;void init(){ l[1] = 0, r[0] = 1, idx = 2;}void add(int k, int x){ e[idx] = x; r[idx] = r[k], l[r[k]] = idx; l[idx] = k, r[k] = idx ++ ;}void remove(int k){ r[l[k]] = r[k]; l[r[k]] = l[k];}int main(){ int m; cin >> m; init(); while (m -- ) { char s[10]; cin >> s; int k, x; if (!strcmp(s, "L")) { cin >> x; add(0, x); } else if (!strcmp(s, "R")) { cin >> x; add(l[1], x); } else if (!strcmp(s, "D")) { cin >> k; remove(k + 1); } else if (!strcmp(s, "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] << ' '; return 0;}/*本题目并非完全照抄以上函数，还是需要处理一些问题的。例如：删除第k个数，idx是从2开始使用的，所以删除的时候应该是remove(k + 1);还有其他问题，读者可自行思考。*/