线性链表的基本运算

2.5.2　线性链表的基本运算

线性链表的运算主要有以下几种：

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

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

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

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

⑤逆转线性链表；

⑥复制线性链表；

⑦线性链表的排序；

⑧线性链表的查找。

本小节主要讨论线性链表的插入与删除。

1．在线性链表中查找指定元素

在对线性链表进行插入或删除的运算中，必须找到插入或删除的位置，这就需要对线性链表进行扫描查找，在线性链表中寻找包含指定元素值的前一个节点。当找到包含指定元素的前一个节点后，就可以在该节点后插入新节点或删除该节点后的一个节点。

在非空线性链表中寻找包含指定元素值x的前一个节点p的基本方法如下：

从头指针指向的节点开始往后沿指针进行扫描，直到后面已没有节点或下一个节点的数据域为x为止。因此，由这种方法找到的节点p有两种可能：当线性链表中存在包含元素x的节点时，则找到的p为第一次遇到的包含元素x的前一个节点序号；当线性链表中不存在包含元素x的节点时，则找到的p为线性链表中的最后一个节点号。

2．线性链表的插入

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

为了要在线性链表中插入一个新元素，首先要给该元素分配一个新节点，以便用于存储该元素的值。新节点可以从可利用栈中取得。然后将存放新元素值的节点链接到线性链表中指定的位置。

假设可利用栈与线性链表如图2-22(a)所示。现在要在线性链表中包含元素x的节点之前插入一个新元素b。其插入过程如下：

（1）从可利用栈取得一个节点，设该节点号为p（即取得节点的存储序号存放在变量p中），并置节点p的数据域为插入的元素值b。经过这一步后，可利用栈的状态如图2-22(b)所示。

（2）在线性链表中寻找包含元素x的前一个节点，设该节点的存储序号为q。线性链表如图2-22(b)所示。

（3）最后将节点p插入到节点q之后。为了实现这一步，只要改变以下两个节点的指针域内容：

①使节点p指向包含元素x的节点（即节点q的后件节点）。

②使节点q的指针域内容改为指向节点p。

这一步的结果如图2-22(c)所示。此时插入就完成了。

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

图2-22　线性链表的插入

3．线性链表的删除

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

为了在线性链表中删除包含指定元素的节点，首先要在线性链表中找到这个节点，然后将需要删除的节点放回到可利用栈。

假设可利用栈与线性链表如图2-23（a）所示。现在要在线性链表中删除包含元素x的节点，其删除过程如下：

（1）在线性链表中寻找包含元素x的前一个节点，设该节点序号为q。

（2）将节点q后的节点p从线性链表中删除，即让节点q的指针指向包含元素x的节点p的指针指向的节点。

经过上述两步后，线性链表如图2-23（b）所示。

（3）将包含元素x的节点p送回可利用栈。经过这一步后，可利用栈的状态如图2-23（c）所示。此时，线性链表的删除运算完成。

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

图2-23　线性链表的删除