C 代码

#define N 100010

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

void init() {
    // 规定 0号是最左边的哨兵， 1号是最右边的哨兵，可用的idx从2开始
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

// 在下标为k的点的右边插入x
void add(int k, int x) {
    v[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

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

int main() {
    int m;
    scanf("%d", &m);
    init();

    while (m--) {
        char op[3];
        int k, x;

        scanf("%s", op);
        if (op[0] == 'L') {
            scanf("%d", &x);
            add(0, x); // 0号是最左边的哨兵，指向链表的最左端节点，所以"L x" 相当于在0号哨兵的右边插入x
        } else if (op[0] == 'R') {
            scanf("%d", &x);
            add(l[1], x); // 1号是最右边的哨兵，指向链表的最右端节点，所以"R x" 相当于在1号哨兵的左边插入x，即在l[1]的右边插入x
        } else if (op[0] == 'D') {
            scanf("%d", &k);
            remove(k + 1); // 第k个插入的数在数组中下标为k+1
        } else {
            if (op[1] == 'L') {
                scanf("%d%d", &k, &x);
                add(l[k + 1], x);
            } else {
                scanf("%d%d", &k, &x);
                add(k + 1, x);
            }
        }
    }

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