链表是一种数据结构，分为单链表和双链表，有STL模板，但这里主要讲一下数组模拟，属于静态链表。可以引申为邻接表，用于存储图或者树，对于图论有一定的作用。
单链表
单链表通过可以通过结构体或者数组模拟，结构体模拟代码如下
struct Node
{
int val;
Node *next;
};但是因为每次调用需要new Node()，而这是一个非常慢的操作，所以一般不会这么干，尤其是算法竞赛中，很容易TLE。
于是我们会需要使用数组来进行，需要使用以下四个变量
- head：存储头节点的下标
- idx：存储当前用到了第几个节点
- e[]：数组，e[i]代表下标为i的节点的值
- ne[]：数组，ne[i]代表下标为i的节点的下一个指针的坐标
首先需要初始化。受Sunglassman教学线段树时的推荐，使用结构体封装。于是，初始化函数
List()
{
head = -1, idx = 0;
}初始化让头节点的坐标为-1，意思是头节点即为结束。这样就实现了初始化一个空的列表
同时把idx赋值为0，便于之后的新增节点的操作。
将 x 插入头节点
void add_to_head(int x)
{
e[idx] = x; // 赋值
ne[idx] = head; // 当前的点的next指针指向head
head = idx; // head指向新节点的位置
idx ++ ; // 更新idx
}这样的文字表述可能有些抽象，我们画个图来解释一下这段代码
插入前的链表长这样
| head-> | o-> | end | |
| idx | 0 | -1 |
蓝色箭头代表了head = 0，红色箭头代表了ne[0] = -1
那么我们在头部插入新节点就是要让列表变成这样
| head-> | new -> | o-> | end | |
| idx | 1 | 0 | -1 |
这个时候我们的红色箭头不变，把head更新为1，对标head = idx，并且建立新的指针绿色箭头，即ne[1]更新为原来的头节点，对标ne[idx] = head。随后更新idx的状态。这就是在头节点增加元素的操作
将 x 插入下标为 k 的点后面
void add(int k, int x)
{
e[idx] = x; // 赋值
ne[idx] = ne[k]; // 当前的点的 next 指针指向 k 的下一个指针
ne[k] = idx; // 第k个点的下一个指针更新为当前的idx
idx ++ ;
}依旧画图解释
假设插入前的链表长这样
| head -> | o-> | o-> | o -> | o -> | end | |
| idx | 1 | 0 | 2 | 3 |
然后我们要在2号节点后插入一个元素，此时k = 2
变成这样
| head-> | o-> | o -> | o-> | o-> | o-> | end | |
| idx | 1 | 0 | 2 | 4 | 3 |
红色箭头代表了ne[2]我们插入新元素，把ne[2]更新为了4，也就是idx，同时把ne[4]更新为了3，即原来的ne[2]。这样就对标了代码中的先把ne[idx] = ne[k]，再把ne[k] = ne[idx]的操作了。
将下标是 k 的点的后面的点删掉
void remove(int k)
{
ne[k] = ne[ne[k]]; // 当前的点的ne直接指向下一个点的ne
}比较好理解，直接将当前的点的ne指向下一个点的ne即可实现跳过下一个点的效果。造成的空间浪费在算法题中可以忽略。
封装代码
struct List{
// head 头节点下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;
// 初始化
List()
{
head = -1; // 空链表，head指针指向的位置就是end
idx = 0; // 用了第 0 个点
}
// 将 x 插入头节点
void add_to_head(int x)
{
e[idx] = x; // 赋值
ne[idx] = head; // 当前的点的next指针指向head
head = idx; // head指向新节点的位置
idx ++ ; // 更新idx
}
// 将 x 插入下标为 k 的点后面
void add(int k, int x)
{
e[idx] = x; // 赋值
ne[idx] = ne[k]; // 当前的点的 next 指针指向 k 的下一个指针
ne[k] = idx;
idx ++ ;
}
// 将下标是 k 的点的后面的点删掉
void remove(int k)
{
ne[k] = ne[ne[k]]; // 当前的点的ne直接指向下一个点的ne
}
};双链表
时隔一年（好吧其实也就只有五六天），今天继续学习双链表了。双链表与单链表类似，只是需要可以反向查找而已。
<- o ->一个向左，一个向右，即int l[], int r[];
初始化
这里为了偷懒，0号点表示左端点，1号点表示右端点。那么我们初始化的时候就需要构建起0号点和1号点之间的关系，画成图就是这样
0 --- 1很显然，刚刚会区分左右和数数的幼儿园小朋友都知道，0号点的右边是1号点，1号点的左边是0号点。于是初始化代码就成了
void init()
{
r[0] = 1, l[1] = 0;
idx = 2; // 0号点和1号点均被占用
}插入一个点
我们有两种选择，既可以插入到某个点的左边，又可以插入到某个点的右边。先画个图
原来是酱紫：
| o | o | o | o | o | |
| idx | 0 | 2 | 3 | 4 | 1 |
| l[idx] | / | 0 | 2 | 3 | 4 |
| r[idx] | 2 | 3 | 4 | 1 | / |
现在呢，假设我们要在三号点和四号点的中间插入五号点，那么就变成了这样
| o | o | o | o | o | o | |
| idx | 0 | 2 | 3 | 5 | 4 | 1 |
| l[idx] | / | 0 | 2 | 3 | 5 | 4 |
| r[idx] | 2 | 3 | 5 | 4 | 1 | / |
现在发生了什么变化呢？我们发现，l[4]，r[3]都被更新为了新插入的点的idx，新插入的点的 l 变成了原来的左边的点的idx，新插入的点的 r 变成了原来的右边的点的idx。那么我们需要的代码就是如下两个
// 在下标为k的右边插入x
void add_right(int k, int x)
{
e[idx] = x; // 更新值
r[idx] = r[k]; // 更新的点的r变为原来的点的r
l[idx] = k; // 更新的点的l变成原来的点的下标
l[r[k]] = idx; // 原的右边的点的l变为现在的idx
r[k] = idx; // 原来的点的r变为现在的idx
// 顺序很重要，否则会数据污染！
}// 在下标为k的左边插入x
void add_left(int k, int x)
{
e[idx] = x; // 更新值
l[idx] = l[k]; // 更新的点的r变为原来的点的r
r[idx] = k; // 更新的点的l变成原来的点的下标
r[l[k]] = idx; // 原的右边的点的l变为现在的idx
l[k] = idx; // 原来的点的r变为现在的idx
}
//或者
void add_left(int k, int x)
{
add_right(l[k], x);
}
// 也就是说只要实现一个即可顺序务必注意！否则会数据污染！已经踩过一次坑了！
删除
好的，现在我们来看删除操作，依旧先画图。
假设原来这样，我们需要删除三号点
| o | o | o | o | o | |
| idx | 0 | 2 | 3 | 4 | 1 |
| l[idx] | / | 0 | 2 | 3 | 4 |
| r[idx] | 2 | 3 | 4 | 1 | / |
那这个图就变成了这样：
| o | o | o | o | |
| idx | 0 | 2 | 4 | 1 |
| l[idx] | / | 0 | 3 | 4 |
| r[idx] | 2 | 3 | 1 | / |
对比可以发现，相当于在对三号点没有做任何修改的情况下，分别修改2号点和4号点的 l 和 r ， 就能跳过三号点，就相当于从链表中删除了三号点。
那如何修改 l 和 r 呢？只要把 2 号点的 r 改成 4，4号点的 l 改成 2，就可以了。
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}封装代码
//const int N = 1e6 + 10;
struct List
{
int e[N], l[N], r[N], idx;
List()
{
// 0 表示左端点，1 表示右端点
r[0] = 1, l[1] = 0;
idx = 2;
}
// 在下标为k的右边插入x
void add_right(int k, int x)
{
e[idx] = x; // 更新值
r[idx] = r[k]; // 更新的点的r变为原来的点的r
l[idx] = k; // 更新的点的l变成原来的点的下标
l[r[k]] = idx; // 原的右边的点的l变为现在的idx
r[k] = idx; // 原来的点的r变为现在的idx
idx ++ ;
}
void add_left(int k, int x)
{
add_right(l[k], x);
}
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
void output()
{
for (int i = r[0]; i != 1; i = r[i] ) cout << e[i] << ' ';
}
void debug()
{
for (int i = 0; i < idx; i ++ ) cout << e[i] << ' ';
cout << '\n';
for (int i = 0; i < idx; i ++ ) cout << l[i] << ' ';
cout << '\n';
for (int i = 0; i < idx; i ++ ) cout << r[i] << ' ';
cout << '\n';
cout << '\n';
}
};好了，链表就此完结~
更新日志
古登堡编辑器的原生code在当前主题(Kizumi)下无法保持正确的排版，因此选用表格来表示链表的图。而表格不能打开定宽功能，同时表格中不能有多余的空格，否则会发生奇怪的错误。
评论（0）
暂无评论