1.5.1 线性链表的基本概念
　　1.5.2 线性链表的基本运算
　　1.5.3 循环链表及其基本运算

　　1.5.1 线性链表的基本概念　

　　前面主要讨论了线性表的顺序存储结构以及在顺序存储结构下的运算。线性表的顺序存储结构具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结构的优越性更为突出。但是，线性表的顺序存储结构在某些情况下就显得不那么方便，运算效率不那么高。实际上，线性表的顺序存储结构存在以下几方面的缺点：
　  ① 在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证 插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量数据元素。在平均情况下，为了在顺序存储的线性表中插入或删除一个元素，需要移动线性表中约一半的元素，在最坏情况下，则需要移动线性表中所有的元素。因此，对于大的线性表，特别是元素的插入或删除很频繁的情况下，采用顺序存储结构是很不方便的，插入与删除运算的效率都很低。
　  ② 当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入新的元素时，就会发生“上溢”错误。在这种情况下，如果在原线性表的存储空间后找不到与之连续的可用空间，则会导致运算的失败或中断。显然，这种情况的出现对运算是很不利的。也就是说，在顺序存储结构下，线性表的存储空间不便于扩充。
　  ③在实际应用中，往往是同时有多个线性表共享计算机的存储空间，例如，在一个处理中，可能要用到若干个线性表（包括栈与队列）。在这种情况下，存储空间的分配将是一个难题。如果将存储空间平均分配给各线性表，则有可能造成有的线性标表空间不够用，而有的线性表的空间根本用不着或用不满，这就使得在有的线性表空间无用的而处于空闲的情况下，另外一些线性表的操作由于“上溢”而无法进行。这种情况实际上是计算机的存储空间得不到充分利用。如果多个线性表共享存储空间，对每一个线性表的存储空间进行动态分配，则为了保证每一个线性表的存储空间连续且顺序分配，会导致在对某个线性表进行动态分配存储空间时，必须要移动其他线性表中的数据元素。这就是说，线性表的顺序存储结构不便于对存储空间的动态分配。
　  由于线性表的顺序存储结构存在以上缺点，因此，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用下面要介绍的链式存储结构。
　  假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。
　  在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。
　  在链式存储方式中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
　  链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式结构表 示较复杂的非线性结构时，其指针域的个数要多一些。
　   1.  线性链表
　  线性表的链式结构称为线性链表。
　  为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一个小块占若干字节，通常称这些小块为存储结点。
　  为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。为此目的，将存储空间中的每一个存储结点分为两部分： 一部分用于存放数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号（即存储结点的地址），即指向后件结点，称为指针域。由此可知，在线性链表中，存储空间的结构如图 1.15 所示。
　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　图1.15 线性链表的存储空间　　　　　　  
　  在线性链表中，用一个专门的指针 HEAD 指向线性链表中第一个数据元素的结点 （即存放线性表中第一个数据元素的存储结点的序号）。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空（用 NULL 或 0 表示），表示链表终止。线性表的逻辑结构如图 1.16 所示。
　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　图1.16　线性链表的一个存储节点
　   线性链表中存储结点的结构如图 1.17 所示
　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　图1.17　线性链表的逻辑结构
　　下面举一个例子来说明线性链表的存储结构。
　　设线性表为（ a1, a2, a3, a4, a5 ）存储空间具有 10 个存储结点，该线性表在存储空间中的存储情况如图 1.18 （ a ）所示。为了直观地表示该线性链表中的各元素之间的前后关系，还可以用如图 1.18 （ b ）所示的逻辑状态来表示，其中每一个结点上面的存储序号（简称结点号）。
　　　　　　　　　　　　　　　　　　　　　
　　　　　
　　　　　　　　　　　　　　　　　　　　　　(b)　线性链表的逻辑状态
　　　　　　　　　　　　　　　　　　　　　　图1.18 线性链表的物理状态和逻辑状态
　　一般来说，在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。在线性链表中，各数据元素之间的前后件关系是由各结点的指针域来指示的，指向线性表中第一个结点的指针 HEAD 称为头指针，当 HEAD=NULL （或 0 ）时称为空表。
　  对于线性链表，可以从头指针开始，沿各结点的指针扫描到链表中的所有结点。下面的算法是从头指针开始，依次输出各结点的值。
　  上面讨论的线性链表又成为线性单链表。在这种链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点。因此，在这种线性链表中，只能顺指针向链尾方向进行扫描，这对于某些问题的处理会带来不便，因为在这种链接方式下，由某一结点出发，只能找到它的后件，而为了找出它的前件，必须从头指针开始重新寻找。
　  为了弥补线性单链表的这个缺点，在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针（ Link ），用以指向其前件结点；另一个称为右指针（ Rlink ），用以指向其后件结点。这样的线性链表称为双向链表，其逻辑状态如图 1.19 所示。
　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　图1.19 双向链表示意图
　　2.带链的栈
　  栈也是线性表，也可以采用链式存储结构。图 1.20 是栈在链式存储时的逻辑状态示意图。
　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　图1.20　带链的栈
　　　　　
　　　　　　　　　　　　　　　　　　　　　　　图 1.21 可利用栈及其运算

　　1.5.2 线性链表的基本运算

　　线性链表的运算主要有以下几个：
　　•  在线性链表中包含指定元素的结点之前插入一个新元素。
　　•  在线性链表中删除包含指定元素的结点。
　　•  将两个线性链表按要求合并成一个线性链表。
　　•  将一个线性链表按要求进行分解。
　　•  逆转线性链表。
　　•  复制线性链表。
　　•  线性链表的排序。
 　 •  线性链表的查找。
　  本小节主要讨论线性链表的插入与删除。
　　1.在线性链表中查找指定元素
　  在对线性链表进行插入与删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，在线性链表中寻找包含指定元素值的前一个结点。当找到包含指定元素的前一个结点后，就可以在该结点后插入新结点或删除该结点后的一个结点。
　  在非空线性链表中寻找包含指定元素值 x 的前一个结点 p 的基本方法如下：
　  从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一结点的数据域为 x 为止。因此，由这种方法找到的结点 p 有两种可能：当线性链表中不存在包含元素 x 的结点时，则找到的 p 为线性链表中的最后一个结点号。
　　2.线性链表的插入
　  线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。
　  为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点，以便用于存储该元素的值。新结点可以从可利用栈中取得。然后将存放新元素值的结点链接到线性链表中指定的位置。
　  假设可利用栈与线性链表如图 1.23 （ a ）所示。现在要在线性链表中包含元素 x 的结点之前插入一个新元素 b 。其插入过程如下：
　  •  从可利用栈取得一个结点，设该结点号为 p （即取得结点的存储序号存放在变量 p 中），并置结点 p 的数据域为插入的元素值 b 。经过这一步后，可利用栈的状态如图 1.23 （ b ）所示。
　  •  在线性链表中寻找包含元素 x 的前一个结点，设该结点的存储序号为 q 。
　  线性链表如图 1.23 （ b ）所示。
　  •  最后将结点 p 插入到 q 之后。为了实现这一步，只要改变以下两个结点的指针域内容：
　　 •  使结点 p 指向包含元素 x 的结点（即结点 q 的后件结点）。
　　 •  使结点 q 的指针域内容改为指向结点 p 。
　  这一步的结果如图 1.23 （ c ）所示。此时插入就完成。
　　　　
　　　
　　　　　　　　　　　　　　　　　　　　　　　　图1.23　线性链表的插入
　　由线性链表的插入过程可以看出，由于插入的新结点取自于可利用栈，因此，只要可利用栈不空，在线性链表插入时总能取到存储插入元素的新结点，不会发生“上溢”的情况。而且，由于可利用栈是公用的，多个线性链表可以共享它，从而很方便地实现了存储空间的动态分配。另外，线性链表在插入过程中不发生数据元素移动的现象，只需改变有关结点的指针即可，从而提高了插入的效率。
　  3.线性链表的删除
　  线性链表的删除是指在链式存储结构下的线性表中删除包含指定元素的结点。
　  为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。
　  假设可利用栈与线性链表如图 1.24 （ a ）所示。现在要在线性链表删除包含元素 x 的结点，其删除过程如下：
　  （ 1 ）在线性链表中寻找包含元素 x 的前一个结点，设该结点序号为 q.
　  （ 2 ）将结点 q 后的结点 p 从线性链表中删除，即让结点 q 的指针指向包含元素 x 的结点 p 的指针指向的结点。
　  经过上述两步后，线性链表如图 1.24 （ b ）所示 .
　  （ 3 ）将包含元素 x 的结点 p 送回可利用栈。经过这一步后，可利用栈的状态如图 1.24 （ c ）所示。此时，线性链表的删除运算完成。
　　　
　　　　　　　　　　　　　　　　　　　　　　　　　图 1.24 线性链表的删除
　　从线性链表的删除过程可以看出，在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的指针域即可。另外，由于可利用栈是用于收集计算机中所有的空闲结点，因此，当从线性链表中删除一个元素后，该元素的存储结点变为空闲，应该将空闲结点送回到可利用栈。

　　1.5.3 循环链表及其基本运算　

　　前面所讨论的线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和第一个结点的处理必须单独考虑，使空表与非空表的运算不统一。为了克服线性链表的这个缺点，采用一种链接方式，即循环链表（ circular linked list ）的结构。
　  循环链表的结构与前面所讨论的线性表相比，具有以下两个特点：
　   （ 1 ）在循环的链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。
　   （ 2 ）循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。
　  图 1.25 是循环链表的示意图。其中图 1.25 （ a ）是一个非空的循环链表，图 1.25 （ b ）是一个空的循环链表。在此，所谓的空表与非空表是针对线性表中的元素而言。
　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　图1.25 循环链表的逻辑状态
　　在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。
　  另外，由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。
　  循环链表的插入和删除的方法与线性单链表基本相同。但由循环链表的特点可以看出，在对循环链表进行插入和删除的过程中，实现了空表与非空表的运算统一。