6.5.1 链表
最后更新于：2022-04-02 00:29:44
### 6.5.1 链表
如前所述，列表是由许多数据按次序排列形成的一种数据结构，列表成员之间的逻辑关 系是由他们的排列次序表示的。例如，如果一群人按姓氏笔画坐在一排相邻的椅子上，那么 这些人的排列次序就表示了他们姓氏笔画的关系，排在 1 号座位的人肯定是笔画最少的，排 在 i 号座位上的人肯定比排在 i+1 号座位上的人笔画要少（参见图 6.4）。
图 6.4 用排列次序表示数据间逻辑关系
这种连续排列的数据结构的优点是：仅凭排列次序（或相邻关系）就知道成员数据之间的逻辑关系，而不需要另外存储表示成员间逻辑关系的信息；可以通过位置信息（索引）对 任何成员进行随机访问，而不需要从头开始一个一个查看。但连续存储结构有也有缺点：如 果需要增加新成员，必须移动大量数据以便为新成员腾出空间；如果要删除某个数据，删除 后必须移动大量数据以便填补空缺、保持连续性。仍以图 6.4 所示场景为例，如果新来了一 个姓“冯”的人要加入队列，按数据逻辑关系他应当坐在“王”“孙”之间，因此必须使“王” 以后的所有人向右移动一个座位；如果“郑”离开了，那么“周”和其后的所有人必须左移 一个座位。可见，插入、删除操作的代价很大。
再看另一种场景：仍然是一群人要按姓氏笔画顺序排列，但这些人是东一个西一个随便 站立着的，因此无法仅凭这些人所处的位置来判断谁笔画多谁笔画少。这种情形下还有没有 办法表示他们的姓氏笔画顺序信息呢？当然有，例如我们可以让每个人用手指着应该排在他 后面的那个人（图 6.5）。这样，虽然这群人站得杂乱无章，但是通过他们的手指，事实上形 成了一个有序的排列。注意，最后一个人没有可指的对象，我们不妨让他以手指地，表示这 是排列的末尾。
图 6.5 用链接表示数据间逻辑关系
图 6.5 形象地表示了一种以链接方式组织的列表，这种数据结构称为链表（linked list）。 在链表中，成员之间的逻辑关系不是通过存储位置的相邻来表示，而是通过专门的链接信息 来表示。我们将链表中的成员称为结点，每个结点都由两部分信息组成：结点的数据和结点 的链接。结点的数据是实际应用要处理的数据，而结点的链接是对另一个结点的引用（或称 指针），用于表示数据间的逻辑关系。链表中最后一个成员的链接必须设置为表示“无所指” 的某个特殊值。链表结构的第一个结点是整个链表的入口，通常用一个专门的变量来记录链 表入口。链表的形状如图 6.6 所示。
图 6.6 链表
链表可以很好地解决连续存储列表的缺点。例如，如果图 6.5 中新来了“冯”，那我们 只需让“王”的手指改为指向“冯”，并让“冯”指向“孙”；如果“郑”要离开，我们只需 让“吴”的手指改为指向“周”！
然而，与普通列表相比，链表在访问其成员数据时比较麻烦，因为无法通过位置信息来 随机访问链表成员。例如，我们无法直接读取“链表的第 5 个结点”，为了进行这个操作， 必须从链表的头开始，顺着链接向后逐个检查结点。
编程实例：链表的表示和处理
有的编程语言提供了指针类型（存储单元的物理地址），可以很方便地表示链表结点之间的链接。但链接实际上是逻辑层的概念，不必非得用物理层的指针来实现。下面通过前述 按姓氏笔画排序的例子来说明链表的表示及操作方法，其中链接是以结点在列表中的位置索 引实现的。
我们用包含两个成员的列表[(name,strokes),link]来表示结点，其中第一个成员本身是二 元组，分别存储姓氏 name 和笔画数 strokes，第二个成员是链接 link。所有结点存储在列表people 中，这里 people 相当于动态分配的存储空间，结点在 people 中的位置索引就是结点 的“存储地址”，结点的 link 值就是另一个结点的位置索引。因此，虽然结点是按随机次序 存储的，但所有结点按其 link 值前后相连就形成了一个链表。图 6.7(a)展示了存储空间中各 结点的物理存储次序和由链接决定的逻辑次序，其中各个结点的值如图 6.7(b)所示。我们另 外用变量 head 指向链表头（此处即索引为 3 的“孙”结点）。
(a) (b)
图 6.7 链表的表示
读者应该注意到，people 中存储的第一个结点很特别，这是我们设计的代表链表尾的特 殊结点。链表尾结点包含一个笔画数高达 100 的假想姓氏 X，目的是使将来新结点总能在链 表尾之前找到插入位置，这样可以使程序代码更简明。
现在来看如何在链表中插入新结点。我们首先利用 people.append()方法在存储空间的尾 部建立新结点 N，然后再将 N 插入到链表中。具体插入过程是：从链表头 head 开始，沿着 链接 link 查看链表，将沿途各结点与 N 比较，直至找到第一个笔画数大于 N 的结点 M。然 后使 N 的 link 指向 M，而原先指向 M 的结点改为指向 N（参见图 6.8）。这样的 M 肯定能 找到，因为最坏情况下会找到链表尾，而那里有一个笔画数为 100 的结点①。
图 6.8 向链表中插入新结点
如图 6.8 所示，为了在结点 L 和结点 M 之间插入结点 N，需要调整 L 和 N 的 link 值， 为此需要在查找链表的过程中记下连续两个结点 L 和 M 的地址，这正是下列代码中变量 p 和 q 的任务。插入结点的主要代码如下：
```
p = head
q = -1
while True:
if people[p][0][1] <= people[tail][0][1]:
q = p
p = people[p][1]
else:
people[tail][1] = p
if q >= 0:
people[q][1] = tail
else:
head = tail
break
```
> ① 据说笔画数最多的汉字是由四个“龍”组成的，共 64 画。
解决了结点插入链表的问题，则链表的创建问题就变得很平凡了。从空链表（实际上有 一个特殊的链表尾结点）开始，每次根据用户输入的姓氏和笔画数建立新结点，并调用结点 插入算法，重复这个过程即可创建整个链表。程序 6.4 实现了这个功能。
【程序 6.4】linkedlist.py
```
from string import split
def insert(llist,head,tail):
p = head
q = -1
while True:
if llist[p][0][1] <= llist[tail][0][1]:
q = p
p = llist[p][1]
else:
llist[tail][1] = p
if q >= 0:
llist[q][1] = tail
else:
head = tail
break
return head
def main():
people = [[('X',100),-1]]
head = 0
s = raw_input("Enter name and strokes: ")
while s != "":
s2 = split(s,',')
name,strokes = s2[0],eval(s2[1])
people.append([(name,strokes),-1])
tail = len(people)-1
head = insert(people,head,tail)
s = raw_input("Enter name and strokes: ")
print "Physical order:",
for i in range(1,len(people)):
print people[i][0][0],
print
print "Logical order:",
p = head
while people[p][1] >= 0:
print people[p][0][0],
p = people[p][1]
main()
```
主程序首先创建空链表（实际上包含特殊的链表尾结点），然后由用户按“姓氏，笔画”格 式输入数据，程序在 people 末尾建立对应的新结点（相对于为新结点分配存储空间），接着 调用 insert 函数将新结点插入到链表中。重复输入数据、存储新结点、插入新结点的过程直 至输入为空，最后分别按 people 中的结点次序（物理存储次序）和链接的次序（逻辑次序） 显示所有结点的姓氏。下面是程序的一次执行过程和结果：
```
Enter name and strokes: 赵,9
Enter name and strokes: 钱,10
Enter name and strokes: 孙,6
Enter name and strokes: 李,7
Enter name and strokes: 周,8
Enter name and strokes: 吴,7
Enter name and strokes: 郑,8
Enter name and strokes: 王,4
Enter name and strokes:
Physical order: 赵 钱 孙 李 周 吴 郑 王
Logical order: 王 孙 李 吴 周 郑 赵 钱
```
图 6.9 是最终结果的示意图。
图 6.9 输入 8 个姓氏之后的结果
程序 6.4 只实现了链表的插入功能，作为练习，读者可以尝试为程序增加查找、删除等 功能。
以上介绍的是最简单的单链表。为了更有效地处理链表，还可以设计双链表、循环链表 等结构。事实上，利用链接，还可以设计各种各样的非线性数据结构，如树和图等等。有关 内容可阅读数据结构教材。
';