考点5 线性链表

1.线性链表的基本概念

线性表的链式存储结构称为线性链表。

为了存储线性表中的每一个元素，一方面要存储数据元素的值；另一方面要存储各数据元素之间的前后件关系。为此，在链式存储方式中，每个节点由两部分组成：一部分称为数据域，用于存放数据元素值；另一部分称为指针域，用于存放下一个数据元素的存储序号，即指向后件节点。链式存储结构既可以表示线性结构，也可以表示非线性结构。

线性表链式存储结构的特点是用一组不连续的存储单元存储线性表中的各个元素。因为存储单元不连续，所以数据元素之间的逻辑关系就不能依靠数据元素的存储单元之间的物理关系来表示。

2.线性链表的基本运算

线性链表主要包括以下8种运算：

●在线性链表中包含指定元素的节点之前插入一个新元素；

●在线性链表中删除包含指定元素的节点；

●将两个线性链表按要求合并成一个线性链表；

●将一个线性链表按要求进行分解；

●逆转线性链表；

●复制线性链表；

●线性链表的排序；

●线性链表的查找。

真考链接

考核概率为35%。考生要熟记该考点内容，尤其是线性链表的概念和特点、顺序表和链表的优、缺点等。

3.循环链表及其基本运算

（1）循环链表的定义。

在单链表的第一个节点前增加一个表头节点，队头指针指向表头节点，在最后一个节点的指针域的值由NULL改为指向表头节点，这样的链表称为循环链表。循环链表中，所有节点的指针构成了一个环状链。

（2）循环链表与单链表的比较。

对单链表的访问是一种顺序访问，从其中某一个节点出发，只能找到它的直接后继，但无法找到它的直接前驱。而且对于空表和第一个节点的处理必须单独考虑，空表与非空表的操作不统一。

在循环链表中，只要指出表中任何一个节点的位置，就可以从它出发访问到表中其他所有的节点。由于表头节点是循环链表所固有的节点，因此，即使在表中没有数据元素的情况下，表中也至少有一个节点存在，从而使空表和非空表的运算统一。

真题精选

下列叙述中正确的是______。

A）线性链表是线性表的链式存储结构

B）栈与队列是非线性结构

C）双向链表是非线性结构

D）只有根节点的二叉树是线性结构

【答案】A

【解析】根据数据结构中各数据元素之间前后关系的复杂程序，可将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：①有且只有一个根节点；②每个节点最多有一个前驱，也最多有一个后继，则称该数据结构为线性结构，也叫做线性表。若不满足上述条件，则称之为非线性结构。线性表、栈与队列、线性链表都是线性结构，而二叉树是非线性结构。