双链表

1：idx从2开始，因为0存的是r头结点，1存的是l头结点
2：insertX 是在X位置的右侧插入，所以，在最左边插入就是在0后面插入即在r链表头结点插入，在最右边插入就是l[1]位置插入，l[1]中保存的就是最右边的节点
3：在K位置右侧插入，insertK(k + 1 , x);在K位置左侧插入: insertK(l[k + 1] , x)，即先找到K元素左边的元素，然后在左边元素的后面插入

C++ 代码

#include <iostream>
using namespace std;
const int N = 100010;

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

void initial(){
    idx = 2;
    l[1] = 0;
    r[0] = 1;
}

void insertX(int k ,int a){
    e[idx] = a;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

void deleteK(int k){
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

int main(){
    int n;
    cin >> n;
    initial();
    while(n--){
        string c;
        int k , x;
        cin >> c;
        if(c == "L"){
            cin >> x;
            insertX(0,x);
        }else if(c == "R"){
            cin >> x;
            insertX(l[1],x);
        }else if(c == "IL"){
            cin >> k >> x;
            insertX(l[k + 1] , x);
        }else if(c == "IR"){
            cin >> k >> x;
            insertX(k + 1 , x);
        }else{
            cin >> k ;
            deleteK( k + 1 );
        }
    }

    for(int i = r[0]; i != 1;i = r[i]){
        int j = e[i];
        cout << j << " ";
    }
    cout << endl;
    return 0;


}