实现一个双链表，双链表初始为空，支持 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
所有操作保证合法。

输入样例：
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>
using namespace std;
int idx,e[100005],l[100005],r[100005];
//idx是指插入的第几个数 
int T;
void init(){
    r[0]=1;
    l[1]=0;
    idx=2;//开始就有两个节点了，首节点和尾结点 
}
//在最左端添加一个数，不是插到头节点上 
void addheadL(int x){
    l[idx]=0;//新节点->pre=head 
    r[idx]=r[0];//新节点->next=head->next; 
    l[r[0]]=idx;//原来头节点的右节点的左节点是新节点 
    r[0]=idx;//原来头节点的右节点是新节点 
    e[idx++]=x;//加了一个x 
}
//在最右端插入一个数，不是插到尾结点上 
void addheadR(int x){
    l[idx]=l[1];//新节点 ->next= tail->pre 
    r[idx]=1;//新节点->pre=tail 
    r[l[1]]=idx;//tail->pre->next=新节点 
    l[1]=idx;//tail->pre=新节点 
    e[idx++]=x;
}
//删除第k个插入的数 
void deleteK(int k){
    r[l[k]]=r[k];//k->pre->next=k->next 
    l[r[k]]=l[k];//k->next->pre=k->pre;
}
//在第k个插入的数左边插入一个数x 
void insertL(int k,int x){
    r[idx]=k;//新节点->next=k 
    l[idx]=l[k];//新节点->pre=k->pre 
    r[l[k]]=idx;//k->pre->next=新节点 
    l[k]=idx;//k->pre=新节点; 
    e[idx++]=x;
}
//在第k个插入的数右边插入一个数x 
void insertR(int k,int x){
    r[idx]=r[k];//新节点->next=k->next; 
    l[idx]=k;//新节点->pre=k 
    l[r[k]]=idx;//k->next->pre=新节点 
    r[k]=idx;//k->next=新节点 
    e[idx++]=x;
}
int main(int argc, char** argv) {
    init();
    scanf("%d",&T);
    while(T--){
        string op;
        cin>>op;
        if(op=="L"){
            int x;
            scanf("%d",&x);
            addheadL(x);
        }else if(op=="R"){
            int x;
            scanf("%d",&x);
            addheadR(x);
        }else if(op=="D"){
            int k;
            scanf("%d",&k);
            deleteK(k+1);
        }else if(op=="IL"){
            int k,x;
            scanf("%d%d",&k,&x);
            insertL(k+1,x);
        }else if(op=="IR"){
            int k,x;
            scanf("%d%d",&k,&x);
            insertR(k+1,x);
        }
    }
    for(int i=r[0];i!=1;i=r[i]){
        printf("%d ",e[i]);
    }
    printf("\n");
    return 0;
}