2017年计算机二级公共基础辅导讲义：线性链表

　　1.5 线性链表
　　1、线性表顺序存储的缺点：(1)插入或删除的运算效率很低。在顺序存储的线性表中，插入或删除数据元素时需要移动大量的数据元素;(2)线性表的顺序存储结构下，线性表的存储空间不便于扩充;(3)线性表的顺序存储结构不便于对存储空间的动态分配。
　　2、线性链表：线性表的链式存储结构称为线性链表，是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的。因此，在链式存储方式中，每个结点由两部分组成：一部分用于存放数据元素的值，称为数据域;另一部分用于存放指针，称为指针域，用于指向该结点的前一个或后一个结点(即前件或后件)，如下图所示：
　　线性链表分为单链表、双向链表和循环链表三种类型。
　　在单链表中，每一个结点只有一个指针域，由这个指针只能找到其后件结点，而不能找到其前件结点。因此，在某些应用中，对于线性链表中的每个结点设置两个指针，一个称为左指针，指向其前件结点;另一个称为右指针，指向其后件结点，这种链表称为双向链表，如下图所示：

　　3、线性链表的基本运算
　　(1)在线性链表中包含指定元素的结点之前插入一个新元素。
　　*：在线性链表中插入元素时，不需要移动数据元素，只需要修改相关结点指针即可，也不会出现“上溢（注释1）”现象。
　　(2)在线性链表中删除包含指定元素的结点。
　　*：在线性链表中删除元素时，也不需要移动数据元素，只需要修改相关结点指针即可。
　　(3)将两个线性链表按要求合并成一个线性链表。
　　(4)将一个线性链表按要求进行分解。
　　(5)逆转线性链表。
　　(6)复制线性链表。
　　(7)线性链表的排序。
　　(8)线性链表的查找。
　　*：线性链表不能随机存取（注释2）。
　　4、循环链表及其基本运算
　　在线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和对第一个结点的处理必须单独考虑，使空表与非空表的运算不统一。为了克服线性链表的这个缺点，可以采用另一种链接方式，即循环链表。
　　与前面所讨论的线性链表相比，循环链表具有以下两个特点：1)在链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点，而循环链表的头指针指向表头结点;2)循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。
　　下图a是一个非空的循环链表，图b是一个空的循环链表：

　　循环链表的优点主要体现在两个方面：一是在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点;二是由于在循环链表中设置了一个表头结点，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。
　　*：循环链表是在单链表的基础上增加了一个表头结点，其插入和删除运算与单链表相同。但它可以从任一结点出发来访问表中其他所有结点，并实现空表与非空表的运算的统一。
　　注释1：当为一个线性表分配顺序存储结构后，如果出现线性表的存储空间已满，但还需要插入新的元素时，就会发生“上溢”现象。
　　注释2：在链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺着链域逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存储结构。计算机等级考试