链表

单链表

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
void solve() {
    int n;
    cin >> n;
    int idx = 0;
    vector<int> nex(n + 1), e(n + 1);
    nex[0] = -1;
    int &head = nex[0];
    auto insert = [&](int x, int k) {  // 在地址为k的数后插入x
        idx++;
        nex[idx] = nex[k];
        e[idx] = x;
        nex[k] = idx;
    };
    auto del = [&](int k) {  // 删除地址为k的数
        nex[k] = nex[nex[k]];
    };
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        if (s == "H") {
            int x;
            cin >> x;
            insert(x, 0);
        } else if (s == "D") {
            int k;
            cin >> k;
            del(k);
        } else {
            int k, x;
            cin >> k >> x;
            insert(x, k);
        }
    }
    for (int i = head; i != -1; i = nex[i]) cout << e[i] << " ";
}

双链表

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
void solve() {
    int n;
    cin >> n;
    int idx = 1;
    vector<int> pre(n + 2), nxt(n + 2), e(n + 2);
    nxt[0] = 1;
    pre[1] = 0;
    int &head = nxt[0];
    int &tail = pre[1];
    auto insert = [&](int x, int k) {  // 地址为k的后面插入x
        idx++;
        e[idx] = x;
        pre[idx] = k;
        nxt[idx] = nxt[k];
        pre[nxt[k]] = idx;
        nxt[k] = idx;
    };
    auto del = [&](int k) {
        nxt[pre[k]] = nxt[k];
        pre[nxt[k]] = pre[k];
    };
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        if (s == "L") {  // 头节点插入
            int x;
            cin >> x;
            insert(x, 0);
        } else if (s == "R") {  // 尾节点插入
            int x;
            cin >> x;
            insert(x, tail);
        } else if (s == "D") {  // 删除地址为k+1的数
            int k;
            cin >> k;
            del(k + 1);
        } else if (s == "IL") {  // 在地址为k的数前面插入x
            int k, x;
            cin >> k >> x;
            k++;
            insert(x, pre[k]);
        } else {  // 在地址为k的数后面插入x
            int k, x;
            cin >> k >> x;
            k++;
            insert(x, k);
        }
    }
    for (int i = head; i != 1; i = nxt[i]) cout << e[i] << " ";
}