写在前面

线性表：由n（n>=0）个数据特性相同的元素构成的有限序列
线性表的长度：线性表中元素的个数，n=0时称为空表
对于非空的线性表或线性结构，其特点是：
（1）存在唯一一个被称作“第一个”的数据元素
（2）存在唯一一个被称作“最后一个”的数据元素
（3）除第一个数据元素外，结构中的每个数据元素均只有一个前驱
（4）除最后一个数据元素外，结构中的每个数据元素均只有一个后驱

线性表的链式表示：单链表、循环链表、双向链表

单链表

单链表存图的写法主要有两种：一维数组模拟和结构体

一维数组写法

// head 表示头节点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx存储当前已经用到了哪个点

初始化

void Init(){
    head = -1;
    idx = 0;
}

删除头结点

void remove(){
    head = ne[head];
}

头结点处插点

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

在下标为k的点后面插点

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

将下标为k的点后面的点删除

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

遍历单链表

for (int i = head; i != -1; i = ne[i]){
    cout << e[i] << ' ';
}

双向链表

双向链表存图的写法主要有两种：一维数组模拟和结构体

单链表的每个结点中只有一个指示直接后继的指针域，换句话说，从某个点出发
只能顺时针向后遍历其它结点。如果想要查询某结点的直接前驱，就必须从前往
后挨个查找，O(n)的复杂度显然不是理想的，所以诞生了双向链表。

顾名思义，在双向链表中的结点有两个指针域，一个指向直接后继，另一个指向
直接前驱。

// e[]表示节点的值
// l[]表示节点的左指针
// r[]表示节点的右指针
// idx表示当前用到了哪个节点

初始化

void Init(){
    r[0] = 1, l[1] = 0;
    idx = 2;
}

在节点k的右边插入一个数x

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

删除结点k

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

遍历双向链表

for (int i = r[0]; i != 1; i = r[i])
    cout << e[i] << ' ';