C/C++算法竞赛中，一般不使用结构体指针去实现链表，因为当new一个新结点时，动态分配内存会花费大量的时间。

这里我们使用数组来模拟单链表（静态链表）。

变量说明

• head：头指针，指向第一个结点的位置
• idx：下标，相当于动态链表的地址（指针）
• e[i]：i结点的值
• ne[i]：i结点的next指针

总结：除了e[i]其余变量都是地址（指针）

模板题

AcWing 826. 单链表

1. 头插操作

• idx是下标，是地址，这里的写法是每次先使用地址，再申请新地址
• 注意静态链表每次插入后，将链表头更改为当前结点（改的是地址）

静态链表写法：

// 头插法
void head_insert(int x) {
    e[idx] = x;         // 结点申请空间(idx)并赋值
    ne[idx] = head;     // 头插，当前插入结点下一结点为链表头
    head = idx;         // 链表头改为当前插入结点
    idx++;              // 申请下一片空间
}

C语言动态链表写法：

void head_insert(int x) {
    Node *s = (Node*)malloc(sizeof(Node));
    s->val = x;
    s->next = head->next;   // 带头结点的单链表
}

2. 插入操作

• 注意是在第k个插入的数后面插入
• 注意是第k个插入的数而不是链表的第k个数，因此k-1即是地址
• 这里的插入同样要申请地址

// 在第k个插入的数后面插入
void insert(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];    // 将原来的k地址链到新插结点后
    ne[k] = idx++;      // k的next指针指向新插结点
}

3. 删除操作

• 这里的删除操作实际上是将next指针直接跳过要删除的结点，会浪费一个下标的数组空间

• 本题删除操作是删除第k个数后面的数

// 删除第k个插入的数后面的数
void remove(int k) {
    ne[k] = ne[ne[k]];  
}

4. 输入与输出

• 链表头插入的操作与第k个输入的数后插入无法合并为一个操作
• 同样删除链表头与删除第k个数后面的数也得分别操作
• 删除第k个结点与在第k个结点后插入，传入的参数是k-1，因为idx是从0开始创建的

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int head, e[N], ne[N], idx;

void init()
{
    head = -1;
    idx = 0;
}

// 头插法...
// 在第k个插入的数后面插入...
// 在第k个插入的数后面插入...

int main() {
    int m;
    cin >> m;

    init();

    while(m--) {
        char op;
        int k, x;
        cin >> op;

        if(op == 'H') {
            cin >> x;
            head_insert(x);
        }else if(op == 'I') {
            cin >> k >> x;
            insert(k - 1, x);
        }else {
            cin >> k;
            if(k == 0)    // 删除链表头
                head = ne[head];
            else
                remove(k - 1);
        }
    }

    for(int i = head; i != -1; i = ne[i]) 
        cout << e[i] << ' ';

    return 0;
}