链表

单链表

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] << " ";
}

双链表

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] << " ";
}