下载掌阅APP，畅读海量书库
立即打开
链表（Linked List）又称为动态数据结构，使用不连续内存空间来存储，是由许多相同数据类型的数据项按特定顺序排列而成的线性表。链表的特性是其各个数据项在计算机内存中的位置是不连续且随机（Random）存放的，其优点是数据的插入或删除都相当方便。
当有新数据加入链表后，就向系统申请一块内存空间，而在数据被删除后，就把这块内存空间还给系统，在链表中添加和删除数据都不需要移动大量的数据。链表的缺点是设计数据结构时较为麻烦，另外在查找数据时，也无法像静态数据（如数组）那样可以随机读取数据，必须按序查找到该数据为止。在日常生活中有许多链表抽象概念的运用，例如可以把链表想象成火车，有多少人就挂多少节车厢，当假日人多、需要较多车厢时就多挂些车厢，平日里人少时就把车厢的数量减少，这种做法非常有弹性，如图2-22所示。
图2-22 链表类似于火车及其挂接的车厢
我们最常使用的是“单向链表”（Single Linked List）。一个单向链表节点基本上由两个元素组成，即数据字段和指针，其中的指针指向链表中下一个节点在内存中的地址，如图2-23所示。
图2-23 单向链表的节点示意图
在单向链表中，第一个节点是“链表头指针”，指向最后一个节点的指针设为NULL，表示它是“链表尾”，不指向任何地方。例如列表A={a，b，c，d，x}，其单向链表的数据结构如图2-24所示。
图2-24 单向链表示意图
由于单向链表中所有节点都知道节点本身的下一个节点在哪里，但是对于前一个节点却没有办法知道，因此在单向链表的各种操作中，“链表头指针”就显得相当重要，只要存在链表头指针，就可以遍历整个链表，进行链表节点的加入和删除等操作。注意，除非必要，否则不要移动链表头指针。
对于两个或两个以上链表的串接（Concatenation，也称为级联），它的实现方法很容易：只要将链表的首尾相连即可，如图2-25所示。
图2-25 单向链表的链接
在单向链表类型的数据结构中，如果要在链表中删除一个节点，如同从一列火车中移走原有的某节车厢，这时根据所删除节点的位置会有三种不同的情况。
只要把链表头指针指向第二个节点即可，如图2-26所示。
图2-26 删除链表的第一个节点
只要将指向最后一个节点ptr的指针直接指向NULL（空节点）即可，如图2-27所示。
图2-27 删除链表的最后一个节点
只要将删除节点的前一个节点的指针指向要删除节点的下一个节点即可，如图2-28所示。
图2-28 删除链表中间的一个节点
在单向链表中添加新节点如同在一列火车中加入新的车厢，有三种情况：加到第一个节点之前、加到最后一个节点之后以及加到此链表中间任一位置。接下来我们使用图解方式来说明。
只需把新节点的指针指向链表原来的第一个节点，再把链表头指针指向新节点即可，如图2-29所示。
图2-29 将新节点加到第一个节点之前
只需把链表的最后一个节点的指针指向新节点，新节点的指针再指向NULL即可，如图2-30所示。
图2-30 将新节点加到最后一个节点之后
例如要插入的节点在X与Y之间，只要将X节点的指针指向新节点，新节点的指针指向Y节点即可，如图2-31和图2-32所示。
图2-31 新节点的指针指向Y节点
图2-32 X节点的指针指向新节点
了解单向链表节点的删除和添加之后，大家会发现在这种具有方向性的链表结构中增删节点是相当容易的一件事。而要从头到尾输出整个单向链表也不难，但若要反转过来输出单向链表，则需要某些技巧。我们知道单向链表中的节点特性是知道下一个节点的位置，可是却无从得知它的上一个节点的位置。如果要将单向链表反转，就必须使用三个指针变量，如图2-33所示。
图2-33 单向链表的反转
在算法invert（X）中，我们使用了p、q、r三个指针变量，它的运算过程如下：
（1）执行while循环前，如图2-34所示。
图2-34 执行while循环前链表和各
（2）第一次执行while循环，如图2-35所示。
图2-35 第一次执行while循环后链
（3）第二次执行while循环，如图3-36所示。
图2-36 第二次执行while循环后链
当执行到p=NULL时，单向链表就整个反转过来了。