链式存储是最常用的动态存储方法，为了克服顺序表的缺点，可以采用链式方式存储线性表，通常将采用链式存储结构的线性表称为线性链表。
这里讲一讲链表的一些常识。

链表基础概念

链表是一个常见的基础数据结构，可以理解为是一种线性表，是一种物理存储单元上非连续、非顺序的存储结构。
你可以直接简称它为链式存储的线性表，链表是由多个链表元素（称为节点）组成，而节点之间通过逻辑连接，这样就形成了链式存储结构。
拆分来看，链表分为两个域：
1、数据域（值域）：用于存储节点的值。
2、指针域（链域）：用于存储其后继节点的地址（或位置）。
线性链表正是通过每个节点的指针域将线性表的N个节点按其逻辑顺序链接在一起的，这也就形成了数据元素的逻辑顺序。
我们从一个单链表的结构来图形化这两块：

单链表结构图

链表的分类

从链接方式的角度看，可分为：单链表、双链表、循环链表；
从实现角度看，可分为：静态链表、动态链表。

单链表

1、单链表的的每个节点只有一个next指针域，它是一种顺序存储结构。
2、单链表中每个节点的存储地址存放在其前驱节点（也就是上一个节点）的指针域中，那么问题来了，第一个节点前面没有节点了，所以应该设一个头指针H指向第一个节点。
3、同理，最后一个节点没有直接后继节点了，所以指定单链表的最后一个节点的指针域为空（NULL）。
4、单链表的头指针H标志着整个单链表的开始，所以必须得先知道头指针，才能够顺着每个节点的next指针域去得到单链表中的每个元素。
5、在单链表中要找到第N个节点或者数据元素，必须先找到第N-1个节点，通过它的指针域去拿到N的信息。
6、单链表只可向一个方向遍历。
7、有时候为了操作的统一方便，可以给单链表增加一个头结点，这个头结点数据域存储一些关于线性表的长度等附加信息，指针域用来存储指向第一个结点的指针，也就变成了H —> 头结点数据域/指针域 —> 第一个结点数据域/指针域........

循环链表

带头结点，附设头指针 带头结点，附设尾指针 1、循环列表首尾相接，它是将单链表的最后一个结点的指针域由NULL改为指向表头结点，就得到了单链形式的循环链表，即循环单链表。
2、带头结点的循环单链表的各种操作的实现算法和带头结点的单链表的实现算法基本一致，差别仅在于算法中判断当前结点p是否为表尾结点的条件不同：
（1）单链表：p != NULL或p -> next != NULL；
（2）循环单链表：p != H或p -> next != H。
3、在循环单链表中附设一个尾指针有时比附设头指针会使操作更简单：
（1）附设头指针：找开始结点a0的时间复杂度是O(1)，然而要找到终端结点a(n-1)，则需要从头指针开始遍历整个链表，时间复杂度为O(n)；
（2）附设尾指针：查找开始结点rear -> next -> next；查找终端结点rear，时间复杂度都是O(1)。
所以使用中多采用尾指针表示循环单链表。

双链表

刚才在循环列表中去找开始结点、终端结点这些，如果附设尾指针时间复杂度为O(1)，但是如果需要从任一结点出发，去找到其前驱结点（也就是前一个结点），时间复杂度却还是O(n)，所以双向链表就诞生了。

要想从表中快速确定任一结点的前驱，既然每个结点有个指向后继结点的指针，那给它前面加一个指向前驱结点的指针不就完了吗？
所以，在单链表的基础上给每个结点里再增加一个指向其前驱的指针域prior，这样形成的链表中就有两条方向不同的链，即双（向）链表。

1、由于双向链表中既有前向链又有后向链，寻找任一结点的直接前驱结点和直接后继结点就比较方便了，假设指针p指向双链表中某一节点，则p -> prior -> next == p，p == p -> next -> prior一定成立。
2、与单链表类似，双链表也可以增加头结点使双链表的某些运算更加方便。
3、双链表也可以由循环表，成为双向循环链表。 三种形式双向循环链表

静态链表

前面提到的各种链表都是使用指针类型实现的，链表中的结点空间的分配、回收都是由系统提供的标准函数malloc、free等动态实现，所以都是属于动态链表。
那么问题来了，在一些高级语言里面没有提供指针这个数据类型（比如BASIC），但是仍然想采用链表作存储结构，这个时候静态链表就出来了。
1、静态链表是用类似于数组的方法实现的，是顺序的存储结构。
2、静态链表需要预先分配地址空间大小，所以静态链表的初始长度一般是固定的。
3、静态链表分data域和next域，data域还是一样，存储节点的数据信息；而next域不再存放指针，而是存放游标，游标存放的是后继结点在结构数组中的相对位置（即数组下标值）。
4、在做插入和删除操作时不需要移动元素，仅需修改指针。

动态链表

动态链表是用内存申请函数malloc、new来进行动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址是不连续的，需要通过指针来顺序访问。