单链表

                     

贡献者： 有机物

　　 链表是一种用于存储数据的链式数据结构，形如一条链子一样来连接元素，通常用于存储树和图。

　　 与数组不同的是：数组是一种支持随机访问，但不支持在任意位置插入或删除元素的数据结构。但链表支持在任意位置插入或删除，但只能按顺序依次访问其中的元素。

　　 单链表：

　　 可以看到，链表上每个结点都有三个值，分别为：下标、值和 $\text{next}$ 指针。

　　 下标为 $3$ 的结点的下一个结点为空结点，所以 $\text{next}$ 值为 $-1$。

　　 如果用 C++ 的指针和结构体来写链表的话，长成这样子：

struct List
{
    int value;
    List *next;
};

　　 一般在竞赛中很少用上面这种方式来实现链表，因为这种写法效率很低，所以这里我们来讲一下如何使用数组来模拟链表。

　　 数组模拟单链表需要这么几个数组和变量：

int e[N], ne[N], head, idx;
// N 表示数组的大小
// head 表示头结点的下标
// idx 表示是第几个插入的数，后续模拟一下链表就懂了
// e[i] 表示结点 i 的值
// ne[i] 表示结点 i 的 next 指针是多少

　　 单链表通常有这么几个操作：

1. 向链表头插入一个数；
2. 删除第 $k$ 个插入的数后面的数；
3. 在第 $k$ 个插入的数后插入一个数。

　　 我们来模拟一个样例来更好的理解单链表，如要进行如下这些操作：

1. 先在链表头插入一个数 $9$
2. 在第 $1$ 个插入的数后面再插入一个数 $1$
3. 删除第一个插入的数的后面的一个数
4. 删除头结点后面的数
5. 在链表头插入一个数 $6$
6. 在第 $3$ 个插入的数后面再插入一个数 $6$
7. 在第 $4$ 个插入的数后面再插入一个数 $5$
8. 在第 $4$ 个插入的数后面再插入一个数 $5$
9. 在第 $3$ 个插入的数后面再插入一个数 $4$
10. 删除第 $6$ 个插入的数的后面一个数

　　 我们来借助几张图片来模拟一下上面的 $10$ 个操作

　　 经过模拟了 $10$ 次单链表的操作，就可以理解单链表的执行过程了，让我们来看看这些操作具体怎么写。

　　 第一个操作：向头结点插入一个数

　　 代码如下：

void add_to_head(int x) 
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx ++ ;
}
// 熟练掌握了之后就可以写成一行了。

e[idx] = x, ne[idx] = head, head = idx ++ ;

　　 第二个操作：在第 $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 = ne[head]

　　 到目前为止，单链表的基本操作就讲完了。