### 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 &gt;= 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 只实现了链表的插入功能，作为练习，读者可以尝试为程序增加查找、删除等 功能。 以上介绍的是最简单的单链表。为了更有效地处理链表，还可以设计双链表、循环链表 等结构。事实上，利用链接，还可以设计各种各样的非线性数据结构，如树和图等等。有关 内容可阅读数据结构教材。