数组模拟链表（单链表，双链表）

结构体＋指针实现链表

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

每次创建一个新链表，就要调用new，new Node()这个操作非常慢，在笔试中一般不采用，会超时。

这里介绍用数组模拟链表，也称静态链表。

单链表：邻接表，用来存储图和树。

双链表：优化某些问题。

1.数组模拟单链表

用e[N]数组来存储每个节点的值，用ne[N]数组来存储每个节点的next指针是多少。e数组和ne数组是由下标关联起来。空节点的下标用-1表示。

 初始化单链表

//head 表示头节点的next指向，即ne[头节点]
//e[i] 表示节点i的值
//ne[i] 表示节点i的next指针是多少
//idx 存储当前已经用到哪个点
 
//初始化链表
void init()
{
    head = -1;  //头节点指向空
    idx = 0;
}

插入操作

• 插到头节点的位置

将节点nx插入到head与n0节点中间。

插入操作后

//将x插入到头节点
void add_to_head(int x)  //x为节点x存储的值
{
    e[idx] = x;  //设置x节点的值
    ne[idx] = head; //step1: x节点的next指向head的指向
    head = idx;  //step2-3: head指向x节点
    idx ++;  //当前可用节点后移
}

初始化链表+在头节点处插入一个值为6的节点，代码详细过程

•  插到任意位置

//将x插入到节点k后面
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

删除操作

删除n2节点，让n1的next指向n2的next指向（即n3）。

//删除节点k的下一个节点
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

2. 数组模拟双链表

用l[N]来表示某节点左边指向的一个节点，用r[N]来表示某节点右边指向的一个节点。

初始化双链表

//初始化
void init()
{
    l[1] = 0;  //节点1的左边是节点0
    r[0] = 1;  //节点0的右边是节点1
    idx = 2;
}

插入操作

在节点k的右边插入一个新节点。

step2和step3先后顺序不能变，如果先修改n1的右指针，那么待会儿n1的右指针就不再指向n2，要修改n2的左指针就不能通过step2的方法了。

//在节点k的右边插入一个点
void add(int k, int x)
{
    e[idx] = x;
    l[idx] = k;  //step1,该节点的左指针指向k
    r[idx] = r[k];  //step1,该节点的右指针指向k的右节点
    l[r[k]] = idx;  //step2,节点k的右节点的左指针指向该节点
    r[k] = idx;  //step3,节点k的右指针指向该节点
    idx ++;
}

在节点k的左边插入一个数，即在节点k左节点的右边插入一个数，调用add(l[k],x)即可。

初始化链表+在节点0右边插入一个值为6的节点。

 删除操作

删除节点k。

//删除节点k
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}