【模板】单链表

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 998244353;
int m, e[N]/*存值*/, ne[N]/*存下一节点位置*/, head/*表头位置*/, idx/*当前已使用的节点数量*/;

void init() {//初始化
    head = -1, idx = 0;
}

void add_to_head(int x) {
    e[idx] = x, ne[idx] = head, head = idx++;
}

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

void add(int k, int x) {
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> m;
    init();
    while (m--) {
        char op;
        int k, x;
        cin >> op;
        switch (op) {
            case 'H':
                cin >> x;
                add_to_head(x);
                break;
            case 'D':
                cin >> k;
                if (!k) head = ne[head];//若删表头，则直接将head重赋值为下一节点
                else remove(k - 1);//因为是从0开始标号，使用需要k-1
                break;
            case 'I':
                cin >> k >> x;
                add(k - 1, x);//同上
                break;
            default:
                break;
        }
    }
    for (int i = head/*从头开始遍历链表*/; i != -1/*直到无下一节点*/; i = ne[i]) cout << e[i] << ' ';
    return 0;
}