6.5.1 链表

如前所述，列表是由许多数据按次序排列形成的一种数据结构，列表成员之间的逻辑关 系是由他们的排列次序表示的。例如，如果一群人按姓氏笔画坐在一排相邻的椅子上，那么 这些人的排列次序就表示了他们姓氏笔画的关系，排在 1 号座位的人肯定是笔画最少的，排 在 i 号座位上的人肯定比排在 i+1 号座位上的人笔画要少（参见图 6.4）。

6.5.1 链表 - 图1

图 6.4 用排列次序表示数据间逻辑关系

这种连续排列的数据结构的优点是：仅凭排列次序（或相邻关系）就知道成员数据之间的逻辑关系，而不需要另外存储表示成员间逻辑关系的信息；可以通过位置信息（索引）对 任何成员进行随机访问，而不需要从头开始一个一个查看。但连续存储结构有也有缺点：如 果需要增加新成员，必须移动大量数据以便为新成员腾出空间；如果要删除某个数据，删除 后必须移动大量数据以便填补空缺、保持连续性。仍以图 6.4 所示场景为例，如果新来了一 个姓“冯”的人要加入队列，按数据逻辑关系他应当坐在“王”“孙”之间，因此必须使“王” 以后的所有人向右移动一个座位；如果“郑”离开了，那么“周”和其后的所有人必须左移 一个座位。可见，插入、删除操作的代价很大。

再看另一种场景：仍然是一群人要按姓氏笔画顺序排列，但这些人是东一个西一个随便 站立着的，因此无法仅凭这些人所处的位置来判断谁笔画多谁笔画少。这种情形下还有没有 办法表示他们的姓氏笔画顺序信息呢？当然有，例如我们可以让每个人用手指着应该排在他 后面的那个人（图 6.5）。这样，虽然这群人站得杂乱无章，但是通过他们的手指，事实上形 成了一个有序的排列。注意，最后一个人没有可指的对象，我们不妨让他以手指地，表示这 是排列的末尾。

6.5.1 链表 - 图2

图 6.5 用链接表示数据间逻辑关系

图 6.5 形象地表示了一种以链接方式组织的列表，这种数据结构称为链表（linked list）。 在链表中，成员之间的逻辑关系不是通过存储位置的相邻来表示，而是通过专门的链接信息 来表示。我们将链表中的成员称为结点，每个结点都由两部分信息组成：结点的数据和结点 的链接。结点的数据是实际应用要处理的数据，而结点的链接是对另一个结点的引用（或称 指针），用于表示数据间的逻辑关系。链表中最后一个成员的链接必须设置为表示“无所指” 的某个特殊值。链表结构的第一个结点是整个链表的入口，通常用一个专门的变量来记录链 表入口。链表的形状如图 6.6 所示。

6.5.1 链表 - 图3

图 6.6 链表

链表可以很好地解决连续存储列表的缺点。例如，如果图 6.5 中新来了“冯”，那我们 只需让“王”的手指改为指向“冯”，并让“冯”指向“孙”；如果“郑”要离开，我们只需 让“吴”的手指改为指向“周”！

然而，与普通列表相比，链表在访问其成员数据时比较麻烦，因为无法通过位置信息来 随机访问链表成员。例如，我们无法直接读取“链表的第 5 个结点”，为了进行这个操作， 必须从链表的头开始，顺着链接向后逐个检查结点。

编程实例：链表的表示和处理

有的编程语言提供了指针类型（存储单元的物理地址），可以很方便地表示链表结点之间的链接。但链接实际上是逻辑层的概念，不必非得用物理层的指针来实现。下面通过前述 按姓氏笔画排序的例子来说明链表的表示及操作方法，其中链接是以结点在列表中的位置索 引实现的。

我们用包含两个成员的列表[(name,strokes),link]来表示结点，其中第一个成员本身是二 元组，分别存储姓氏 name 和笔画数 strokes，第二个成员是链接 link。所有结点存储在列表people 中，这里 people 相当于动态分配的存储空间，结点在 people 中的位置索引就是结点 的“存储地址”，结点的 link 值就是另一个结点的位置索引。因此，虽然结点是按随机次序 存储的，但所有结点按其 link 值前后相连就形成了一个链表。图 6.7(a)展示了存储空间中各 结点的物理存储次序和由链接决定的逻辑次序，其中各个结点的值如图 6.7(b)所示。我们另 外用变量 head 指向链表头（此处即索引为 3 的“孙”结点）。

6.5.1 链表 - 图4

(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.5.1 链表 - 图5

图 6.8 向链表中插入新结点

如图 6.8 所示，为了在结点 L 和结点 M 之间插入结点 N，需要调整 L 和 N 的 link 值， 为此需要在查找链表的过程中记下连续两个结点 L 和 M 的地址，这正是下列代码中变量 p 和 q 的任务。插入结点的主要代码如下：

  1. p = head 
  2. q = -1
  3. while True:
  4.     if people[p][0][1] <= people[tail][0][1]: 
  5.         q = p
  6.         p = people[p][1] 
  7.     else:
  8.     people[tail][1] = p 
  9.     if q &gt;= 0:
  10.         people[q][1] = tail 
  11.     else:
  12.         head = tail 
  13.     break

6.5.1 链表 - 图6

① 据说笔画数最多的汉字是由四个“龍”组成的，共 64 画。

解决了结点插入链表的问题，则链表的创建问题就变得很平凡了。从空链表（实际上有 一个特殊的链表尾结点）开始，每次根据用户输入的姓氏和笔画数建立新结点，并调用结点 插入算法，重复这个过程即可创建整个链表。程序 6.4 实现了这个功能。

【程序 6.4】linkedlist.py

  1. from string import split
  2. def insert(llist,head,tail): 
  3.     p = head
  4.     q = -1
  5.     while True:
  6.         if llist[p][0][1] <= llist[tail][0][1]: 
  7.             q = p
  8.             p = llist[p][1] 
  9.         else:
  10.         llist[tail][1] = p 
  11.         if q >= 0:
  12.             llist[q][1] = tail 
  13.         else:
  14.             head = tail 
  15.         break
  16.     return head
  17. def main():
  18.     people = [[('X',100),-1]]
  19.     head = 0
  20.     s = raw_input("Enter name and strokes: ") 
  21.     while s != "":
  22.         s2 = split(s,',')
  23.         name,strokes = s2[0],eval(s2[1]) 
  24.         people.append([(name,strokes),-1]) 
  25.         tail = len(people)-1
  26.         head = insert(people,head,tail)
  27.         s = raw_input("Enter name and strokes: ")
  28.     print "Physical order:",
  29.     for i in range(1,len(people)): 
  30.         print people[i][0][0],
  31.     print
  32.     print "Logical order:", 
  33.     p = head
  34.     while people[p][1] >= 0: 
  35.         print people[p][0][0], 
  36.         p = people[p][1]
  37. main()

主程序首先创建空链表（实际上包含特殊的链表尾结点），然后由用户按“姓氏，笔画”格 式输入数据，程序在 people 末尾建立对应的新结点（相对于为新结点分配存储空间），接着 调用 insert 函数将新结点插入到链表中。重复输入数据、存储新结点、插入新结点的过程直 至输入为空，最后分别按 people 中的结点次序（物理存储次序）和链接的次序（逻辑次序） 显示所有结点的姓氏。下面是程序的一次执行过程和结果：

  1. Enter name and strokes: 赵,9 
  2. Enter name and strokes: 钱,10 
  3. Enter name and strokes: 孙,6 
  4. Enter name and strokes: 李,7 
  5. Enter name and strokes: 周,8 
  6. Enter name and strokes: 吴,7 
  7. Enter name and strokes: 郑,8 
  8. Enter name and strokes: 王,4
  9. Enter name and strokes:
  10. Physical order: 赵 钱 孙 李 周 吴 郑 王
  11. Logical order: 王 孙 李 吴 周 郑 赵 钱

图 6.9 是最终结果的示意图。

6.5.1 链表 - 图7

图 6.9 输入 8 个姓氏之后的结果

程序 6.4 只实现了链表的插入功能，作为练习，读者可以尝试为程序增加查找、删除等 功能。

以上介绍的是最简单的单链表。为了更有效地处理链表，还可以设计双链表、循环链表 等结构。事实上，利用链接，还可以设计各种各样的非线性数据结构，如树和图等等。有关 内容可阅读数据结构教材。