数组模拟双向链表

1. cnt表示点的序号
2. 0和1好点是左右端点
3. 每次添加一个点前需要cnt++
4. 在开始的时候cnt=2

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int e[N], l[N], r[N], cnt;

void add(int k, int x) {
    cnt++;
    e[cnt] = x;
    r[cnt] = r[k];
    l[cnt] = k;
    l[r[k]] = cnt;
    r[k] = cnt;
}

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

int main() {
    r[0] = 1;
    l[1] = 0;
    cnt = 2;
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        char c[3];
        int k, x;
        scanf("%s", c);
        if (c[0] == 'L') {
            scanf("%d", &x);
            add(0, x);
        } else if (c[0] == 'R') {
            scanf("%d", &x);
            add(l[1], x);
        } else if (c[0] == 'D') {
            scanf("%d", &k);
            remove(k + 2);
        } else if (c[0] == 'I') {
            scanf("%d%d", &k, &x);
            if (c[1] == 'L') {
                add(l[k + 2], x);
            } else {
                add(k + 2, x);
            }
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) {
        printf("%d ", e[i]);
    }
    return 0;
}