头插法, 数组模拟链表

#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;

int h = -1, e[N], ne[N], idx = 0;

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

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

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


int main () {
    int m; cin >> m;
    while (m--) {
        char op; cin >> op;
        int x, k;
        if (op == 'H') {
            cin >> x;
            add(x);
        } else if (op == 'I') {
            cin >> k >> x;
            add(k, x);
        } else if (op == 'D') {
            cin >> k;
            if (k == 0) h = ne[h];
            else remove(k);
        }
    }
    for (int i = h; ~i; i = ne[i]) cout << e[i] << ' ';
    return 0;
}