1.双链表

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

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


//初始化
void init()
{
    l[1] = 0,r[0] = 1;            //初始化[0]->[1]   第一个点的右边是 1   第二个点的左边是 0
    idx = 2;                      //idx 此时已经用掉两个点了
}




//在第K个点右边插入一个 X 
void add(int k, int x)
{
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];                //todo 这边的 k 不加 1 ， 输入的时候 k+1 就好
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}


//当然在 K 的左边插入一个数 可以再写一个 ， 也可以直接调用我们这个函数，在 k 的左边插入一个 数 等价于在 l[k] 的右边插入一个数 add(l[k],x)




//删除下标为k的点
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}




int main(void)
{
    ios::sync_with_stdio(false);
    cin >> m;
    
    init();

    while(m--)
    {
        string op;
        cin >> op;
        
        int k, x;

        if(op=="L")                     //最左右边插入:直接在[0]的右边插入
        {
            cin >> x;
            add(0, x);
        }
        else if(op=="R")                //最右边插入:[1]的左边点的右边插入
        {
            cin >> x;
            add(l[1], x);                             
        }
        else if(op=="D")                //第k次即下标为k+1
        {
            cin >> k;
            remove(k + 1);
        }
        else if(op=="IL")               //普通左边插入,下标k+1
        {
            cin >> k >> x;
            add(l[k + 1], x);
        }
        else                            //普通右边插入,下标k+1
        {
            cin >> k >> x;
            add(k + 1, x);
        }    
    }
    
    //遍历链表
    for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';

    return 0;
}