单链表

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N = 1e5+5;
    4. //head:头节点下标，idx:存储当前用到了哪个点 
    5. //e[i]:表示节点i的值
    6. //ne[i]:表示节点i的next指针
    7. int n, idx; 
    8. int head, e[N], ne[N];
    9. void init() {
    10.     head = -1;
    11.     idx = 0;
    12. } 
    13. //将x插到头节点 
    14. void add_to_head(int x) {
    15.     e[idx] = x;
    16.     ne[idx] = head;
    17.     head = idx++;
    18. }
    19. //将x插到下标是k的点的后面 
    20. void add(int k, int x) {
    21.     e[idx] = x;
    22.     ne[idx] = ne[k];
    23.     ne[k] = idx++;
    24. }
    25. //删掉下标为k的点后面的点 
    26. void del(int k) {
    27.     ne[k] = ne[ne[k]];
    28. }
    29. signed main() {
    30.     init();
    31.     scanf("%d", &n);
    32.     for (int i = 1; i <= n; i++) {
    33.         char op[2];
    34.         int x, k;
    35.         scanf("%s", op);
    36.         if (*op == 'H') {
    37.             scanf("%d", &x);
    38.             add_to_head(x);
    39.         } else if (*op == 'D') {
    40.             scanf("%d", &k);
    41.             if (!k) {
    42.                 head = ne[head];
    43.             } else {
    44.                 del(k-1);
    45.             }
    46.         } else {
    47.             scanf("%d%d", &k, &x);
    48.             add(k-1, x);
    49.         }
    50.     }
    51.     for (int i = head; i != -1; i = ne[i])
    52.         cout << e[i] << ' ';
    53.     puts("");     
    54.     return 0;
    55. }

    双链表
    image.png

    #include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n, idx;
int e[N], l[N], r[N]; 
void init() {
    r[0] = 1, l[1] = 0;
    idx = 2;
} 
//在节点k的右边插入一个数x 
void insert(int k, int x) {
    e[idx] = x;
    l[idx] = k, r[idx] = r[k];
    l[r[k]] = idx, r[k] = idx++; 
}
//删除节点k 
void del(int k) {
    l[r[k]] = l[k];
    r[l[k]] = r[k];
} 
signed main() {
    init();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        string op;
        cin >> op;
        int k, x;
        if (op == "L") {
            scanf("%d", &x);
            insert(0, x);
        } else if (op == "R") {
            scanf("%d", &x);
            insert(l[1], x);
        } else if (op == "D") {
            scanf("%d", &k);
            del(k+1);
        } else if (op == "IL") {
            scanf("%d%d", &k, &x);
            insert(l[k+1], x);
        } else {
            scanf("%d%d", &k, &x);
            insert(k+1, x);
        }
    }
    for (int i = r[0]; i != 1; i = r[i])
        cout << e[i] << ' ';
    puts("");
    return 0;
}