链表

链表的概念

定义：链表是一种物理存储单元上非连续、非顺序的存储结构，由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

在链表的储存上，每个结点不仅包含所存的元素信息，还包含元素间的逻辑信息。

链表的特性

• 不支持随机访问：不能通过知道第一个元素的地址（即储存空间的首地址）可以轻松访问储存的所有数据。
• 节点的储存空间利用率相对顺序表较低：链表中的每分一个结点需要划出一部分空间来储存指向下一个结点位置的指针
• 支持储存空间的动态分配：链表中当前结点的位置是由其前驱结点中的地址信息所指示的。其结点可以散落在内存中的任意位置，且不需要一次性地划分所有结点所需的空间给它。
• 在链表中进行插入操作无需移动元素（而顺序表需要）

链表的形式

单链表

在每个结点除了包含的数据域外，还包含一个指针域，用以指向其后继结点。

• 带头结点的单链表

带头结点的单链表中，头指针head指向头结点，头结点的值域不含任何信息，从头结点的后继结点开始储存信息。头指针head 始终不等于NULL，head->next等于NULL的时候，链表为空。

带头节点的单链表（图片来自网络）

• 不带头结点的单链表

不带头结点的单链表中的头指针head直接指向开始结点，当head等于NULL时，链表为空。

不带头节点的单链表

双链表

双链表就是在单链表结点上增添了一个指针域，指向当前节点的前驱。

相比于单链表，双链表能够从终端结点反向走到开始结点。

双链表（图片源自网络）

循环链表

• 循环单链表

只需要将单链表最后一个指针域（空指针）指向链表中的第一个结点即可。（如果循环单链表带头结点，则指向头结点；不带头结点，则指向开始结点）。

循环单链表可以实现从任何一个结点出发，访问链表中任何结点。（注意：此处应该区分与顺序表随机访问的特点。循环单链表指的是从一个结点出发，而不是知道一个结点从而迅速找到任何一个结点，因此循环单链表不具有随机访问特性。）

带头结点的循环单链表，当head等于head->next时，链表为空；不带头结点的循环单链表，当head等于NULL时，链表为空。

• 循环双链表

双链表终端节点的next指针指向链表中第一个结点，将链表中的第一个结点的prior指针指向终端结点。

不带头结点的循环双链表，head等于NULL，链表为空

带头结点的循环双链表是没有空指针的，其为空状态下，head->next与head->prior必然都等于head，故一下四种语句都可判断为空

head->next == head;
head->prior == head;
head->next == head && head->prior == head;
head->next == head || head->prior == head;

静态链表

静态链表借助一维数组表示。

静态链表结点空间来自于一个结构体数组（一般链表结点空间来自整个内存），数组中每个结点含两个分量：

• 数据元素分量data
• 指针分量（指示了当前结点直接后继节点在数组中的位置）

注意：静态链表的指针不是通常所说储存内存地址的指针型变量，而是储存数组下标的整型变量，其功能类似于指针，故在此称为指针

顺序表与链表区别

基于空间比较

• 储存的分配方式

顺序表储存空间时一次性分配的，链表的是多次分配的

• 存储密度

（注： 存储密度 = 结点值域所占存储量/结点结构所占存储总量）

顺序表存储密度 = 1

链表存储密度 < 1

基于时间的比较

• 存取方式

顺序表可以随机存取，也可以顺序存取

链表只能顺序存取

• 插入/删除时移动元素个数

顺序表平均需要移动一半元素

链表不需要移动元素，仅需修改指针