《计算思维与算法入门》 —2.4 链表

2.4    链表

链表（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  单向链表示意图

由于单向链表中所有节点都知道节点本身的下一个节点在哪里，但是对于前一个节点却没有办法知道，因此在单向链表的各种操作中，“链表头指针”就显得相当重要，只要存在链表头指针，就可以遍历整个链表，进行链表节点的加入和删除等操作。注意，除非必要，否则不要移动链表头指针。

2.4.1  单向链表的串接算法

对于两个或两个以上链表的串接（Concatenation，也称为级联），它的实现方法很容易：只要将链表的首尾相连即可，如图2-25所示。

图2-25  单向链表的链接