线性链表的基本概念

2.5.1　线性链表的基本概念

前面主要讨论了线性表的顺序存储结构以及在顺序存储结构下的运算。线性表的顺序存储结构具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表来说，采用顺序存储结构的优越性更为突出。但是，线性表的顺序存储结构在某些情况下就显得不那么方便，运算效率不那么高。实际上，线性表的顺序存储结构存在以下几方面的缺点：

①在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量的数据元素。在平均情况下，为了在顺序存储的线性表中插入或删除一个元素，需要移动线性表中一半的元素；在最坏情况下，则需要移动线性表中所有的元素。因此，对于大的线性表，特别是在元素的插入或删除很频繁的情况下，采用顺序存储结构是很不方便的，插入与删除运算的效率都很低。

②当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入新的元素时，就会发生“上溢”错误。在这种情况下，如果在原线性表的存储空间后找不到与之连续的可用空间，则会导致运算的失败或中断。显然，这种情况的出现对运算是很不利的。也就是说，在顺序存储结构下，线性表的存储空间不便于扩充。

③在实际应用中，往往是同时有多个线性表共享计算机的存储空间。例如，在一个处理中，可能要用到若干个线性表（包括栈与队列）。在这种情况下，存储空间的分配将是一个难题。如果将存储空间平均分配给各线性表，则有可能造成有的线性表的空间不够用，而有的线性表空间根本用不着或用不满，这就使得在有的线性表空间无用而处于空闲的情况下，另外一些线性表的操作由于“上溢”而无法进行。这种情况实际上是计算机的存储空间得不到充分利用。如果多个线性表共享存储空间对每一个线性表的存储空间进行动态分配，为了保证每一个线性表的存储空间连续且顺序分配，必须要移动其他线性表中的数据元素。这就是说，线性表的顺序存储结构不便于对存储空间的动态分配。

由于线性表的顺序存储结构存在以上这些缺点。因此，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用下面要介绍的链式存储结构。

假设数据结构中的每一个数据节点对应一个存储单元，这种存储单元称为存储节点，简称节点。

在链式存储结构中，要求每个节点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该节点的前一个或后一个节点（即前件或后件）。

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

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

1．线性链表

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

为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储节点。

为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。为此目的，将存储空间中的每一个存储节点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号（即存储节点的地址），即指向后件节点，称为指针域。由此可知，在线性链表中，存储空间的结构如图2-14所示。

图2-14　线性链表的存储空间

线性链表中存储节点的结构如图2-15所示。

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

图2-15　线性链表的一个存储节点

图2-16　线性链表的逻辑结构

下面举一个例子来说明线性链表的存储结构。

设线性表为（a_l，a₂，a₃，a₄，a₅），存储空间具有10个存储节点，该线性表在存储空间中的存储情况如图2-17(a)所示。为了直观地表示该线性链表中各元素之间的前后件关系，还可以用如图2-17(b)所示的逻辑状态来表示，其中每一个节点上面的数字表示该节点的存储序号（简称节点号）。

图2-17　线性链表例

一般来说，在线性表的链式存储结构中，各数据节点的存储序号是不连续的。并且各节点在存储空间中的位置关系与逻辑关系也不一致。在线性链表中，各数据元素之间的前后件关系是由各节点的指针域来指示的，指向线性表中第一个节点的指针HEAD称为头指针，当HEAD=NULL（或0）时称为空表。

对于线性链表，可以从头指针开始，沿各节点的指针扫描到链表中的所有节点。

上面讨论的线性链表又称为线性单链表。在这种链表中，每一个节点只有一个指针域，由这个指针只能找到后件节点，但不能找到前件节点。因此，在这种线性链表中，只能顺指针向链尾方向进行扫描。这对于某些问题的处理会带来不便，因为在这种链接方式下，由某一个节点出发，只能找到它的后件，而为了找出它的前件，必须从头指针开始重新寻找。

为了弥补线性单链表的这个缺点，在某些应用中，对线性链表中的每个节点设置两个指针。一个称为左指针（Llink），用以指向其前件节点；另一个称为右指针（Rlink），用以指向其后件节点。这样的线性链表称为双向链表，其逻辑状态如图2-18所示。

图2-18　双向链表示意图

2．带链的栈

栈也是线性表，也可以采用链式存储结构。如图2-19所示是栈在链式存储时的逻辑状态示意图。

图2-19　带链的栈

在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储节点，这种带链的栈称为可利用栈。由于可利用栈链接了计算机存储空间中所有的空闲节点。因此，当计算机系统或用户程序需要存储节点时，就可以从中取出栈顶节点，如图2-20(b)所示；当计算机系统或用户程序释放一个存储节点（该元素从表中删除）时，则要将该节点放回到可利用栈的栈顶。如图2-20(a)所示。由此可知，计算机中的所有可利用空间都可以以节点为单位链接在可利用栈中。随着其他线性链表中节点的插入与删除，可利用栈处于动态变化之中，即可利用栈经常要进行退栈与入栈操作。

图2-20　可利用栈及其运算

3．带链的队列

与栈类似，队列也是线性表，也可以采用链式存储结构。如图2-21(a)所示是队列在链式存储时的逻辑状态示意图。如图2-21(b)所示是将新节点p插入队列的示意图。如图2-21(c)所示是将排头节点p退出队列的示意图。

图2-21　带链的队列及其运算