一、基本原理
与单链表类似，不同之处在于，单链表只有从头指向尾的一条链，而双链表除了有从头指向尾的一条链外还有从尾指向头的一条链，所以叫做双链表。
双链表也支持插入和删除操作，可以用三个数组来实现，分别是e数组和l数组和r数组，idx表示节点
e数组用来存放节点idx的值；
l数组用来存放节点idx的上一个节点，也叫做前指针；
r数组用来存放节点idx的下一个节点，也叫做后指针；
通过这三个数组就可以实现双链表，下面来详细解释一下：
二、基本操作
1.初始化操作
我们用0和1来分别来表示头节点尾节点，0表示头节点的节点下标，1表示尾节点的节点下标
因为要实现双链表，所以初始状态下，头节点的下一个节点是尾节点，尾节点的上一个节点是头节点，因为已经有了两个节点，所以idx从2开始，故：
void init()
{
r[0] = 1;
l[1] = 0;
idx = 2;
}
2.插入操作
初始状态：
这里的插入操作是指在插入在第k个数的右侧插入一个数x
第一步：对新节点赋值
e[idx] = x
第二步：让新节点的l前指针指向第k个节点，让新节点的r后指针指向之前第k个节点的下一个节点（也就是第k个节点的r后指针）
l[idx] = k;
r[idx] = r[k];
第三步：让之前第k个节点的下一个节点的l前指针指向新节点（idx）
l[r[k]] = idx;
第四步：让第k个节点的r指针指向新节点（idx）
r[k] = idx;
第五步：idx自加，方便下一次的插入操作
下面是插入操作的完整代码
void insert(int k, int x)
{
e[idx] = x;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx;
idx++;
}
备注：第三步和第四步的顺序不能反了，原因如下：
l[r[k]] = idx;
r[k] = idx;
我们通过上面的代码可以看到，我们第三步用到了r[k]，而第四步修改了r[k]，我们实际上需要的是未修改前的r[k]
假设我们先执行了第四步（修改了r[k]），我们第三步修改的是第k个节点的下一个节点的l前指针，但是我们现在已经无法找到第k个节点的下一个指针了，因为我们先修改了r[k]，第k个节点到之前第k个节点的链子已经断了，因此第三步和第四步的顺序不能反了。
3.删除操作
初始状态：
我们所说的删除操作指的是把第k个节点删除
我们的思路是：让第k个节点的前一个节点的r后指针指向第k个节点的下一个节点，让第k个节点的后一个节点的l前指针指向第k个节点的上一个节点，代码如下：
void del(int k)
{
l[r[k]] = l[k];
r[l[k]] = r[k];
}
三、案例
实现一个双链表，双链表初始为空，支持 55 种操作：
在最左侧插入一个数；
在最右侧插入一个数；
将第 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 所有操作保证合法。
输入样例：
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
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int l[N],r[N],e[N],idx;
void init(){
r[0] = 1;
l[1] = 0;
idx = 2;
}
void add(int k ,int x){
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx++;
}
void del(int k){
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main(){
init();
int m;
cin>>m;
while(m--){
string op;
cin>>op;
int k,x;
if(op == "L"){
cin>>x;
add(0,x);
}
else if(op == "R"){
cin>>x;
add(l[1],x);
}
else if(op == "D"){
cin >> k;
del(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 << endl;
return 0;
}
