1.5　线性链表

【考点1】线性链表的基本概念

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

①在插入或删除元素时，为保证操作后的线性表仍然是顺序存储，需要大量移动数据元素，效率很低。

②在顺序存储结构下，线性表的存储空间不便于扩充，易产生上溢现象。

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

（2）链式存储结点组成：

①数据域：用于存放数据元素值。

②指针域：用于存放指针。

指针用于指向该结点的前一个或后一个结点，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。

链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式结构表示较复杂的非线性结构时，其指针域的个数要多一些。

（3）线性链表

①定义：线性链表是线性表的链式存储结构。

②特点

a．各数据结点的存储序号是不连续的，各结点在存储空间中的位置关系与逻辑关系也不一致；

b．各数据元素之间的前后件关系是由各结点的指针域来指示的；

c．每一个结点只有一个指针域，由这个指针只能找到后件结点，不能找到前件结点，只能顺指针向链尾进行扫描。

为了弥补线性单链表的缺陷，在某些应用中为线性链表每个结点设置两个指针，左指针用以指向其前件结点，右指针指向其后件结点。

（4）带链的栈

带链的栈可以用来收集计算机存储空间中所有空闲的存储结点。

与顺序栈一样，带链栈的基本操作有以下几个：

①栈的初始化：建立一个空栈的顺序存储空间；

②入栈运算：在栈顶位置插入一个新元素；

③退栈运算：取出栈顶元素并赋给一个指定的变量；

④读栈顶元素：将栈顶元素赋给一个指定的变量。

（5）带链的队列

与顺序队列一样，带链队列的基本操作有以下几个：

①队列的初始化：建立一个空队列的顺序存储空间；

②入队运算：在循环队列的队尾加入一个新元素；

③退队运算：在循环队列的排头位置退出一个元素并赋给指定的变量。

（6）双向链表

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

【真题演练】

1下列叙述中正确的是（　　）。[2014年9月真题]

A．所谓有序表是指在顺序存储空间内连续存放的元素序列

B．有序表只能顺序存储在连续的存储空间内

C．有序表可以用链式存储方式存储在不连续的存储空间内

D．任何存储方式的有序表均能采用二分法进行查找

【答案】C

【解析】“有序”是指线性表中的元素按照升序或降序（允许相邻元素相同）的方式排列。有序是一个逻辑概念，与物理存储无关。二分法查找时涉及下标运算，要求有序表必须顺序存储。答案选择C选项。

2线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（　　）。[2014年9月真题]

A．节省存储空间

B．插入与删除运算效率高

C．便于查找

D．排序时减少元素的比较次数

【答案】B

【解析】顺序表可以随机存取，元素间关系隐藏于存储关系中，但插入与删除操作需要移动大量元素，降低了效率；链表查找时需要沿链依次比较，效率低，为了表示元素间关系需要额外的指针域，但插入与删除操作仅需改变指针，比顺序表快。答案选择B选项。

3下列叙述中正确的是（　　）。[2013年9月真题]

A．顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的

B．顺序存储结构只针对线性结构，链式存储结构只针对非线性结构

C．顺序存储结构能存储有序表，链式存储结构不能存储有序表

D．链式存储结构比顺序存储结构节省存储空间

【答案】A

【解析】A项正确，在顺序存储结构中，所有元素所占的存储空间是连续的，而在链式存储结构中，存储数据结构的存储空间可以不连续。BC两项错误，线性表在计算机中的存放可以采用顺序存储结构，也可采用链式存储结构，顺序存储结构和链式存储结构都是既可用于线性结构，也可以用于非线性结构；D项错误，顺序存储时元素间的关系隐藏在物理结构中，采用链式存储结构不仅要存储元素的值，元素间的逻辑关系还需要通过附设的指针字段来表示，因此，链式存储结构需要更多的存储空间。答案选择A选项。

【考点2】线性链表的基本运算

（1）常见的线性表的运算

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

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

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

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

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

⑤逆转

⑥复制

⑦排序

⑧查找

（2）在线性链表中查找指定元素

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

这种方法找到的结点p有两种可能：

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

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

（3）线性链表的插入

①定义：线性链表的插入是指在链式储存结构下的线性表中插入一个新元素。

②插入过程：

在线性链表中包含元素x的结点之前插入一个新元素y。

a．从可利用栈取得一个结点，设该结点号为p，并置结点p的数据域为插入的元素值y。

b．在线性链表中寻找包含元素x的前一个结点，设该结点的存储序号为q。

c．最后将结点p插入到结点q之后。

为了实现这一步，只要改变以下两个结点的指针域内容：

第一，使结点p指向包含元素x的结点；

第二，使结点q的指针域内容改为指向结点p。

③插入特点：

a．不会发生上溢现象；

b．可方便实现存储空间动态分配；

c．不发生数据元素移动现象，只改变结点指针，提高插入效率。

（4）线性链表的删除

①定义：线性链表的删除是指在链式储存结构下的线性表中删除包含指定元素的结点。

②删除过程：

在线性链表中删除包含元素x的结点。

a．在线性链表中寻找包含元素x的前一个结点，设该结点序号为q；

b．将结点q后的结点p从线性链表中删除，也就是让结点q的指针指向包含元素x的结点p的指针指向的结点；

c．将包含元素x的结点p送回可利用栈。

③删除特点：

在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的指针域即可。

【考点3】循环链表

（1）与线性链表相比，循环链表具有的特点：

①在循环链表中增加了一个表头结点，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。

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

（2）与线性单链表相比，循环链表具有两方面优点：

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

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

【说明】循环链表的插入与删除运算要比一般单链表简单，不用考虑在空链表和在第一个结点前插入以及空链表的删除等特殊情况，从而实现了空表与非空表运算的统一。

【真题演练】

下列叙述中错误的是（　　）。[2014年3月真题]

A．在双向链表中，可以从任何一个结点开始直接遍历到所有结点

B．在循环链表中，可以从任何一个结点开始直接遍历到所有结点

C．在线性单链表中，可以从任何一个结点开始直接遍历到所有结点

D．在二叉链表中，可以从根结点开始遍历到所有结点

【答案】C

【解析】C项错误，在线性表的单链式存储结构中，从一个结点出发只能遍历到其后的结点，不能遍历其前的结点。A项正确，双向链表的结点包含前驱和后继的两个指针；B项正确，循环链表的最后一个结点的指针指向头结点；D项正确，二叉链表中所有的结点都是根结点的分支。答案选择C选项。