链表

链表是线性表的一种。

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

链表有很多种不同的类型：单向链表，双向链表以及循环链表。如C# 默认提供 LinkedList<T> 就是一个双向链表。

特点

线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个”结点”，表示线性表中一个数据元素。线性表的链式存储表示，有一个缺点就是要找一个数，必须要从头开始找起，十分麻烦。

存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。

单链表

结构描述：

1，Data 数据 + Next 指针，组成一个单链表的内存结构；
2，第一个内存结构称为链头，最后一个内存结构称为链尾；
3，链尾的 Next 指针设置为 NULL [指向空]；
4，单链表的遍历方向单一【只能从链头一直遍历到链尾】

插入/删除操作：

双向链表

结构描述：
1，Data 数据 + Next 指针 + Prev 指针，组成一个双向链表的内存结构；
2，第一个内存结构称为链头，最后一个内存结构称为链尾；
3，链头的 Prev 指针设置为 NULL，链尾的 Next 指针设置为 NULL；
4，Prev 指向的内存结构称为前驱， Next 指向的内存结构称为后继；
5，双向链表的遍历是双向的，即如果把从链头的 Next 一直到链尾的[NULL] 遍历方向定义为正向，那么从链尾的 Prev 一直到链头 [NULL ]遍历方向就是反向；

循环链表

1，循环链表分为单向、双向两种；
2，单向的实现就是在单链表的基础上，把链尾的 Next 指针直接指向链头，形成一个闭环；
3，双向的实现就是在双向链表的基础上，把链尾的 Next 指针指向链头，再把链头的 Prev 指针指向链尾，形成一个闭环；
4，循环链表没有链头和链尾的说法，因为是闭环的，所以每一个内存结构都可以充当链头和链尾；