优化的单链表

y总的模板是不带头结点的（只有一个头指针），以至于插入头结点和在中间插入需要分开。

下面介绍一个带头结点的单链表（不用担心，修改一点点，代码还更少了），可以较大地简化代码。

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

const int N = 1e5 + 10;

int head, idx;
int val[N], nxt[N];

void init() {
    head = 0; //我们把第0个节点作为头结点
    idx = 1; //所以存储数据从下标1开始
    nxt[head] = -1; //头结点nxt指针为空表示当前没有数据节点
}

void insert(int k, int x) { //可以发现我们这里节省了一个add_to_node操作
    val[idx] = x;
    nxt[idx] = nxt[k];
    nxt[k] = idx;
    idx++;
}

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

int main() {
    int m;
    init();
    scanf("%d", &m);
    for(int i = 0; i < m; ++i) {
        char opt[2];
        int k, x;
        scanf("%s", opt);
        if(opt[0] == 'H') {
            scanf("%d", &x);
            insert(0, x);
        }
        else if(opt[0] == 'I') {
            scanf("%d%d", &k, &x);
            insert(k, x);
        }
        else if(opt[0] == 'D') {
            scanf("%d", &k);
            remove(k);
        }
    }

    for(int i = nxt[head]; i != -1; i = nxt[i]) {
        printf("%d ", val[i]);
    }
    return 0;
}