单链表

用结构体实现链表的方式这里不讲，大致写一下：

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

太慢了。

• 单链表：主要应用有 邻接表，存储树和图
• 双链表：优化某些问题

介绍单链表的数组实现：

• head：头指针，指向首节点的下标
• e[i]：当前下标 i 存储的数，类似 val
• ne[i]：当前下标 i 指针指向的节点下标，类似 next
• idx：当前操作用到的下标（不断分配新的节点）

把节点插入到头节点位置：

void add_to_head(int val) {
    e[idx] = val;
    ne[idx] = head;
    head = idx;
    idx ++;
}

把节点插入到下标为 $k$ 的节点后面：

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

将下标为 $k$ 的点后面的节点删除：

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

一定记得初始化

双链表

不用定义头节点 head，而是下标为 0 的点为头节点，1 的点为尾节点。