为什么不叫数据结构而是叫算法呢？因为这里以数组模拟为主。

如果用结构体 + 指针来实现链表，就是一般的方式：

struct Node {
  int val;
  Node* next;
};

这里不讨论这种方式，因为每次创建一个新的 Node的效率很低。在笔试题里面不会用这种方式。

这里讨论使用数组来模拟链表。数组模拟链表也被称为静态链表。第一种是模拟单链表，第二种是模拟双链表。

单链表在算法题里面用的最多的是邻接表。邻接表其实是n个链表。最主要的应用是存储图和树。

双链表主要用来优化某些问题。

数组模拟单链表：一个数组用来记录值，一般用 e[N]；一个数组用来记录指针，一般用 ne[N]。这两个数组用下标进行关联。空节点用 -1表示，所以链表最后一个节点的 ne[i]就是 -1。

第一个节点的值就是 e[0]，第一个节点指向的地方就是 ne[0]也就是 1，即 ne[0] = 1。

#include <iostream>

using namespace std;
const int N = 100010;
int head;
// head 表示头节点的下标
int e[N], ne[N];
int idx;
// idx用来存储当前已经到哪个点了。相当于一个指针，数组下标

void init() { 
    head = -1; // head 先指向空
    idx = 0;
}

void add_to_head(int x) { // 变成头节点
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx ++;
}

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

void shanchu(int k) { // 把下标是k的点后面的点删除
    ne[k] = ne[ne[k]];
}

int main  () {
    init();
    int m;
    scanf("%d", &m);
    while (m -- ) {
        char t;
        int k, x;
        cin >> t;
        if (t == 'H') {
            scanf("%d", &x);
            add_to_head(x);
        } else if (t == 'D') {
            scanf("%d", &k);
            if (!k) { // 如果k为0的话 需要特判一下
                head = ne[head]; 
            } else shanchu(k - 1);
        } else {
            scanf("%d%d", &k, &x);
            add(x, k - 1);
        }
    }

    for (int i = head; i != -1; i = ne[i]) printf("%d ", e[i]);
    printf("\n");
    return 0;
}