$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$
笔记：
单链表的作用：存储树和图。
这里讲的是用数组模拟链表，又称静态链表。
首先在单链表中，我们定义一个头节点$head$。
对于每次插入操作，我们依次进行以下操作：

1. 存储节点权值$val$。
2. 把新的节点修改为头节点$head$。相当于把新的节点的下一个节点，也就是$next$指针，指向当前的表头$head$。
3. 把表头$head$设为这个点的编号。

代码：

//数组模拟链表（静态链表）
//动态链表慢的原因是每次都要new。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int head, val[N], nxt[N], idx;
//head 头结点下标
//val[i] i节点的值
//nxt[i] i的下一个节点的编号
//idx 存储当前用到了哪个节点
void init() { head = -1, idx = 0; }
void add_to_head(int x) {  //插入操作
    val[idx] = x;  //存储节点权值
    nxt[idx] = head;  //把新的节点改为头节点
    head = idx++;    //更新表头
}
void add(int x, int k) {   //将节点x插入编号为k的点后面
    val[idx] = x;
    nxt[idx] = nxt[k];
    nxt[k] = idx++;
}
void remove(int k) { nxt[k] = nxt[nxt[k]]; }  //删除第k个点后面插入的数
void print() {  //打印整个链表
    for (int i = head; i != -1; i = nxt[i]) printf("%d ", val[i]);
    puts("");
}
int main() {
    int m; scanf("%d", &m);
    init();
    while (m--) {
        int k, x; char opt;
        cin>> opt;
        if (opt == 'H') {
            cin >> x;
            add_to_head(x);
        }
        else if (opt == 'D') {
            cin >> k;
            if (k == 0) head = nxt[head];
            remove(k - 1);
        }
        else {
            cin >> k >> x;
            add(x, k - 1);
        }
    }
    print();
    return 0;
}