静态双链表

与单链表类似，但我们用l和r两个数组存放元素的左边和右边。

并且这次的头和尾都是固定的，不像静态单链表中头是会变化的且是存放值的。

我们设定头为0，尾为1，那么如果要删除第k位置的元素，实际上要删除下标k + 1的位置（假定位置从1开始）：

#include <iostream>
using namespace std;
const int N = 100010;
int e[N], l[N], r[N], idx, head, tail;
int m;
string mode;

void init() {
    head = 0;
    tail = 1;
    //  记得要设定tail的左边是0，head的右边是1（这样初始化的链表才是空的）
    l[tail] = 0;
    r[head] = 1;
    idx = 2;
}
//  在下标k的右边插入x，如果要在左边插入，那就k - 1
void add(int k, int x) {
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}
//  删除k位置的元素
void del(int k) {
    l[r[k]] = l[k];     //k的右边的左边等于k的左边
    r[l[k]] = r[k];     //k的左边的右边等于k的右边
}
void print() {
    for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << " ";
}
int main() {
    cin >> m;
    init();
    while(m--) {
        int k, x;
        cin >> mode;
        if(mode == "R") {
            cin >> x;
            add(l[1], x);   //l[1]是指tail的左边
        } else if(mode == "L") {
            cin >> x;
            add(0, x);      //0是head，这里就是在head的右边插入。即在表头插入
        } else if(mode == "IL") {
            cin >> k >> x;
            add(l[k + 1], x);   //在左侧插入。一开始就有0和1下标被占了，本来第k个，下标就是k - 1，现在就是k + 1
        } else if(mode == "IR") {
            cin >> k >> x;
            add(k + 1, x);  
        } else if(mode == "D") {
            cin >> k;
            del(k + 1);
        }
    }
    print();
}