双链表

#include <iostream>
#include <cstring>
#include <algorithm>
#include<cstdio>
using namespace std;


const int N = 1e5+10;
int e[N],l[N],r[N];
int idx;

//将0，1两个点作为最左节点和最右节点的保留字，这样遍历时，if 最右=1 or 最左=0即可退出
void init(){
    r[0]=1;
    l[1]=0;
    idx=2;
}
//右插
void insert(int k,int x){
    e[idx]=x;
    int re=r[k];

    l[idx]=k;
    r[idx]=re;
    r[k]=idx;
    l[re]=idx;
    idx++;
}
void remove(int k){
    int le=l[k],re=r[k];
    r[le]=re;
    l[re]=le;
}

int main()
{
    // char op[3];

    int m;
    scanf("%d", &m);
    init();
    while (m -- ){
        string op;
        cin>>op;
        int k,x;
        if(op=="L")  {
            cin>>x;
            insert(0,x);

        }
        else if(op=="R"){
            cin>>x;
            insert(l[1],x);
        }
        else if(op=="D"){
            cin>>k;
            remove(k+1);
        }
        else if(op=="IL"){
            cin>>k>>x;
            insert(l[k+1],x);
        }
        else if(op=="IR"){
            cin>>k>>x;
            insert(k+1,x);
        }
    }
    for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<" ";

}