C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N=100010;

int e[N],l[N],r[N],idx;

//初始化
void init()
{
    //0表示左端点，1表示右端点。

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

    idx=2;//因为0和1已经被占用过了 ，所以idx从2开始
}

//将结点坐标为k的数删除
void remove(int k)
{
    r[l[k]]=r[k];

    l[r[k]]=l[k];

}
//在结点坐标为k的结点左侧插入一个数
//在最左端插入一个数相当于在右侧插入一个数同理R
void add_l(int k, int x)
{
    e[idx]=x;

    r[l[k]]=idx;

    r[idx]=k;

    l[idx]=l[k];

    l[k]=idx;

    idx++;

}

//在结点坐标为k的结点右侧插入一个数
void add_r(int k, int x)
{
     e[idx]=x;

     l[idx]=k;

     l[r[k]]=idx;//注意这里不能将r[k]写成k+1;

     r[idx]=r[k];

     r[k]=idx;

     idx++;


}
int main()
{
    int m;

    cin>>m;

    init();

    while(m--)
    {

        int x,k;

        string op;

        cin>>op;

        if(op=="L") 
        {
            cin>>x;

            add_r(0,x);

        }
        else if(op=="R")
        {
            cin>>x;
            add_l(1,x);
        }
        else if (op=="D")
        {

            cin>>k;

            remove (k+1);
        }
        else if(op=="IL")
        {

            cin>>k>>x;

            add_l(k+1,x);
        }
          else 
        {
            cin>>k>>x;

            add_r(k+1,x);//因为idx从2开始所以第k个插入数坐标是k+1
        }


    }

    for(int i=r[0];i!=1;i=r[i]) cout <<e[i]<<' ';//左右端点不输出

    return 0;


}