1.5　线性链表

视频二维码（扫码观看）

一、线性链表的基本概念

【定义】线性表的链式存储结构称为线性链表。线性链表的数据结构包括两部分，一是数据元素的值，二是数据元素之间的前后件关系。

图1-12　线性链表的一个存储结点

为什么用线性链表？

（1）线性表顺序存储结构存在的缺点：

①插入或删除过程中需要移动大量的数据元素。

②出现线性表的存储空间已满，但还需要插入新的元素时，就会发生“上溢”错误。

③线性表的顺序存储结构不便于存储空间的动态分配。

（2）线性表链式存储结构存在的优点：

在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。

【说明】

①在线性链表中，用一个专门的指针HEAD指向线性链表中第一个数据元素的结点（即存放线性表中第一个数据元素的存储结点的序号）。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空（用NULL或0表示），表示链表终止。

图1-13　线性链表的逻辑结构

②在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。

③当HEAD＝NULL（或0）时称为空表。

图1-14　线性链表例

1双向链表

对线性链表中的每个结点设置两个指针，一个称为左指针（Llink），用以指向其前件结点；另一个称为右指针（Rlink），用以指向其后件结点。

图1-15　双向链表示意图

2带链的栈

栈也是线性表，也可以采用链式存储结构。

图1-16　带链的栈

在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。

图1-17　可利用栈及其运算

3带链的队列

队列也是线性表，也可以采用链式存储结构。

图1-18　带链的队列及其运算

二、线性链表的基本运算

线性链表的运算主要有以下几个：

①插入：在线性链表中包含指定元素的结点之前插入一个新元素。

②删除：在线性链表中删除包含指定元素的结点。

③合并：将两个线性链表按要求合并成一个线性链表。

④分解：将一个线性链表按要求进行分解。

⑤逆转

⑥复制

⑦排序

⑧查找

1在线性链表中查找指定元素

从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。

因此，由这种方法找到的结点p有两种可能：

①当线性链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一个结点序号；

②当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点号。

2线性链表的插入

图1-19　线性链表的插入

3线性链表的删除

图1-20　线性链表的删除

三、循环链表

线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和对第一个结点的处理必须单独考虑，使空表与非空表的运算不统一。

1循环链表的特点

（1）增加了表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。

（2）循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。

图1-21　循环链表的逻辑状态

2循环链表与线性单链表相比主要有以下两个方面的优点：

（1）在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。线性单链表做不到这一点。

（2）由于在循环链表中设置了一个表头结点，因此，在任何情况下循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。