原题链接

双链表需要 e[i] l[i] r[i] idx 来存储。

  1. e[i] 表示标号为 i 的节点的值。
  2. l[i] 表示标号为 i 的节点左边的节点标号。
  3. r[i] 表示标号为 i 的节点右边的节点标号。
  4. idx 表示当前分配到的节点标号。new Node() 等价于 e[idx]。

标号为 0、1 两个节点为双链表的起始和终止节点，不存储实际数据。初始化时 r[0] = 1, l[1] = 0, idx = 2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <string.h>

using namespace std;

const int N = 1e5 + 10;

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

int m;

void init() {
    // 编号为 0 的节点是双链表最左侧的节点
    r[0] = 1;
    // 编号为 1 的节点是双链表最右侧的节点
    l[1] = 0;
    // idx 从 2 开始
    idx = 2;
}

// 在编号为 k 的节点右边插入一个节点，值为 x
void add(int k, int x) {
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

void remove(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}
int main() {
    init();
    cin >> m;
    while(m--) {
        char op[4];
        int k,x;
        cin >> op;
        if(!strcmp(op, "L")) {
            cin >> x;
            add(0, x);
        } else if(!strcmp(op, "R")) {
            cin >> x;
            add(l[1], x);
        } else if(!strcmp(op, "D")) {
            cin >> k;
            // idx 是从 2 开始的，idx 的顺序就是插入顺序，题目中的 k 从 1 开始，所以需要使用 k+1 访问对应的节点
            remove(k+1);
        } else if(!strcmp(op, "IL")) {
            cin >> k >> x;
            add(l[k+1], x);
        } else if(!strcmp(op, "IR")) {
            cin >> k >> x;
            add(k+1, x);
        }
    }
    // 双链表起始节点编号为 0，所以要从起始节点右边一个节点开始遍历，一直到终止节点，终止节点编号为 1。
    for(int i=r[0];i!=1;i=r[i]) {
        cout << e[i] << " ";
    }
    return 0;
}