一般都是用结构体和指针来模拟链表。
但是，这里要用数组模拟链表。

单链表

单链表是个什么东西

单链表，一开始有个头结点，指向空节点
$head$ –> $\varnothing$
插入元素后就变成
$head$ –> 〇 –> 〇 –> 〇 –> 〇 –> $\varnothing$
每一个点都会存一个值(val)和一个指针(next)指向下一个点

做法：

准备e[N]数组存每一个点的val，ne[N]数组存每一个点的next，他们用下标关联起来。
我们给每个点标号，比如第一个点的标号为0，那么它的val是e[0]，next是ne[0]。
假如一共四个点的标号分别为0,1,2,3，val分别为3,5,7,9，然后按顺序连在一起，那么
e[0]=3,ne[0]=1,e[1]=5,ne[1]=2,e[2]=7,ne[2]=3,e[3]=9,ne[3]=-1-1代表空集。
用head当头节点。
结束。

每个操作对应的代码：

初始化

int head, e[N], ne[N], idx; // idx用来存储当前用到了哪个地址，head是头节点的下标。
void init(){
    head = -1;
    idx = 0;
}

插入

将x插入到头结点

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

将x插到下标为k的这个点后面

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

删除，把下标是k的点后面那个点删掉

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

最后，单链表最常见的用处是邻接表，主要用来存树和图，邻接表就是多个单链表，有多个head节点。具体会在第三讲 搜索与图论里讲。

双链表

双链表是什么东西

单链表只有next指针指向下一个节点，双链表，可以指向左右两个节点。
形状就是这样
$head$ <—> 〇 <—> 〇 <—> 〇 <—> 〇 <—> $\varnothing$

做法：

准备e[N]数组存每一个点的val，l[N]数组存每一个点的左边的点，r[N]数组存每一个点的右边的点，剩下的跟单链表一样。
偷个懒，不定义头、尾节点，让0是头节点，1是尾节点

每个操作对应的代码：

初始化

int e[N], l[N], r[N], idx;
void init(){
    // 0是左端点，1是右端点。
    r[0] = 1, l[1] = 0;
    idx = 2;
}

插入

将x插到下标为k的这个点右面

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

将x插到下标为k的这个点左面

add(l[k], x)

删除，把下标是k的点后面那个点删掉

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