1.1.4 线性链表

本节主要考查线性链表的存储方式和基本操作。

1.线性表的链式存储

在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表，如图1-4所示。

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

（1）线性链表的存储结构

用一组任意的存储单元来依次存放线性表的节点，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零散分布在内存中的任意位置上的。因此，链表中节点的逻辑次序和物理次序不一定相同。为了能正确表示节点间的逻辑关系，在存储每个节点值的同时，还必须存储指示其后件节点的地址（或位置）信息，这个信息称为指针（Pointer）或链（Link）。这两部分组成了链表中的节点结构，链表正是通过每个节点的链域将线性表的n个节点按其逻辑次序链接在一起。由于上述链表的每一个节点只有一个链域，故将这种链表称为单链表（Single Linked）。

显然，单链表中每个节点的存储地址存放在其前驱节点Next域中，而开始节点无前驱节点，故应设头指针HEAD指向开始节点。同时，由于终端节点无后继节点，故终端节点的指针域为空，即NULL。

（2）线性链表的基本运算

线性链表的基本运算包括在线性链表中查找指定元素、在线性链表中插入元素、在线性链表中删除元素。

1）在线性链表中查找指定元素：在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，在线性链表中寻找包含指定元素的前一个节点。

在链表中，查找是否有节点值等于给定值x的节点，若有的话，则返回首次找到的其值为x的节点的存储位置；否则返回NULL。查找过程从开始节点出发，顺着链表逐个将节点的值与给定值x做比较。

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

插入运算是将值为x的新节点插入到表的第i-1个节点和第i个节点之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新节点*p，并令节点p的指针域指向新节点，新节点的指针域指向节点ai。

由线性链表的插入过程可以看出，由于插入的新节点取自于可利用栈，因此，只要可利用栈不空，在线性链表插入时总能取到存储插入元素的新节点，不会发生“上溢”的情况。而且，由于可利用栈是公用的，多个线性链表可以共享它，从而可很方便地实现存储空间的动态分配。另外，线性链表在插入过程中不发生数据元素移动的现象，只要改变有关节点的指针即可，从而提高了插入的效率。

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

删除运算是将表的第i个节点删去。因为在单链表中节点ai的存储地址是在其直接前驱节点ai-1的指针域Next中，所以必须先找到ai-1的存储位置p，然后令p->Next指向ai的直接后继节点，即把ai从链上摘下，最后释放节点ai的空间。

从线性链表的删除过程可以看出，从线性链表中删除一个元素后，不需要移动表中的数据元素，只要改变被删除元素所在节点的前驱节点的指针域即可。另外，可利用栈收集计算机中所有的空闲节点，当从线性链表中删除一个元素后，该元素的存储节点就变为空闲，应将空闲节点送回到可利用栈。

2.双向链表的结构及其基本运算

双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向直接后继节点和直接前驱节点，如图1-5所示。所以，从双向链表中的任意一个节点开始，都可以很方便地访问它的前驱节点和后继节点。

（1）双向链表的基本运算

1）插入：在双向链表的第i个元素前插入一个新节点的时候，首先，找到待插入的位置，用指针p指向该节点；然后，将新节点的前驱指针指向p节点的前一个节点；之后，将p节点的前一个节点的后驱指针指向新的节点；接下来，将新节点的后驱指针指向p节点；最后，将p节点的前驱指针指向新节点。

2）删除：在双向链表中删除一个节点时，可用指针p指向该节点。首先，将p节点的前一个节点的Next指向p节点的下一个节点；然后，将p的下一个节点的前驱指针指向p的上一个节点。

（2）双链表的结构及其基本运算

在前面所讨论的线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和对第一个节点的处理必须单独考虑，使空表与非空表的运算不统一。

因此，可以考虑建立这样的链表，具有单链表的特征，但又不需要增加额外的存储空间，仅对表的链接方式稍做改变，使得对表的处理更加方便灵活。从单链表可知，最后一个节点的指针域为NULL，表示单链表已经结束。如果将单链表最后一个节点的指针域改为存放链表中头节点（或第一个节点）的地址，就使得整个链表构成一个环，又没有增加额外的存储空间，而满足这样条件的链表叫循环链表。

循环链表具有以下两个特点：

1）在循环链表中增加了一个表头节点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的节点。循环链表的头指针指向表头节点。

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

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

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