本节书摘来自华章出版社《数据结构与算法：Python语言描述》一书中的第3章，第3.3节，作者 裘宗燕，更多章节内容可以访问云栖社区“华章计算机”公众号查看

3.3链接表

本节考虑线性表的另一种实现技术。

3.3.1线性表的基本需要和链接表

回忆一下线性表的定义，它就是一些元素的序列，维持着元素之间的一种线性关系。实现线性表的基本需要是：

能够找到表中的首元素（无论直接或者间接，这件事通常很容易做到）。从表里的任一元素出发，可以找到它之后的下一个元素。把表元素保存在连续的存储区里（顺序表），自然能满足这两个需求，其中元素间的顺序关联是隐含的。但是，要满足这两种需求，并不一定需要连续存储元素。显然，对象之间的链接也可以看作一种顺序关联，基于它也可以实现线性表。实现线性表的另一种常用方式就是基于链接结构，用链接关系显式表示元素之间的顺序关联。基于链接技术实现的线性表称为链接表或者链表。采用链接方式实现线性表的基本想法如下：把表中的元素分别存储在一批独立的存储块（称为表的结点）里。保证从组成表结构中的任一个结点可找到与其相关的下一个结点。在前一结点里用链接的方式显式地记录与下一结点之间的关联。这样，只要能找到组成一个表结构的第一个结点，就能顺序找到属于这个表的其他结点。从这些结点里可以看到这个表中的所有元素。下面将只考虑在每个结点里只存储一个表元素的情况，在一个结点里存储多个表元素的实现方式请读者自己考虑。本章最后有些讨论。链接技术是一类非常灵活的数据组织技术，实现链表有多种不同的方式。下面首先讨论最简单的单链表，其中在每个表结点里记录着存储下一个表元素的结点的标识（引用/链接）。后面将介绍另外一些结构的链表，它们各有所长，支持不同的需要。在下面的讨论中，将把“存储着下一个表元素的结点”简称为“下一结点”。实际上，要建立（复杂的）链接结构需要功能强大的存储管理技术支持。在C语言等编程语言里，开发这方面的程序时涉及的技术细节很多，编程中也容易出错，完成的链表使用起来也比较麻烦。在Python等新型编程语言里，对于与链接结构有关的高级技术的支持非常全面，在这里可以很方便地建立和使用各种复杂的链接结构。实际上，利用Python语言编写简单的程序时已经广泛用到了各种链接结构（它们由Python语言默认提供和处理），后面会看到这方面的一些例子。

3.3.2单链表

单向链接表（下面将简称为单链表或者链表）的结点是一个二元组，形式如图3.7a所示，其表元素域elem保存着作为表元素的数据项（或者数据项的关联信息），链接域next里保存同一个表里的下一个结点的标识。

在最常见形式的单链表里，与表里的n个元素对应的n个结点通过链接形成一条结点链，如图3.7b所示。从引用表中首结点的变量（图3.7b中变量p）可以找到这个表的首结点，从表中任一结点可以找到保存着该表下一个元素的结点（表中下一结点），这样，从p出发就能找到这个表里的任一个结点。要想掌握一个单链表，就需要（也只需要）掌握这个表的首结点，从它出发可以找到这个表里的第一个元素（即在这个表结点里保存的数据，保存在它的elem域中），还可以找到这个表里的下一结点（有关信息保存在这个结点的next域中）。按照同样的方式继续下去，就可以找到表里的所有数据元素。

也就是说，为了掌握一个表，只需要用一个变量保存着这个表的首结点的引用（标识或称为链接）。今后将把这样的变量称为表头变量或表头指针。

总结一下：一个单链表由一些具体的表结点构成。每个结点是一个对象，有自己的标识，下面也常称其为该结点的链接。结点之间通过结点链接建立起单向的顺序联系。为了表示一个链表的结束，只需给表的最后结点（表尾结点）的链接域设置一个不会作为结点对象标识的值（称为空链接），在Python里自然可以用系统常量None表示这种情况，在图3.7里用接地符号“⊥”表示链表结束，下面将一直这样表示。通过判断一个（域或变量的）值是否为空链接，可知是否已到链表的结束。在顺序扫描表结点时，应该用这种方法确定操作是否完成。如果一个表头指针的值是空链接，就说明“它所引用的链表已经结束”，这是没有元素就已结束，说明该表是空表。在实现链表上的算法时，并不需要关心在某个具体的表里各结点的具体链接值是什么（虽然保存在表结构里的值都是具体的），只需要关心链表的逻辑结构。对链表的操作也只需要根据链表的逻辑结构考虑和实现。为方便下面的讨论，现在定义一个简单的表结点类：

class LNode:    def __init__(self, elem, next_=None):        self.elem = elem        self.next = next_

这个类里只有一个初始化方法，它给对象的两个域赋值。方法的第二个参数用名字next_，是为了避免与Python标准函数next重名。这也是Python程序中命名的一个惯例。第二个参数还提供了默认值，只是为了使用方便。

基本链表操作现在考虑链表的基本操作及其实现方式。创建空链表：只需要把相应的表头变量设置为空链接，在Python语言中将其设置为None，在其他语言里也有惯用值，例如有的语言里用0作为这个特殊值。删除链表：应丢弃这个链表里的所有结点。这个操作的实现与具体的语言环境有关。在一些语言（如C语言）里，需要通过明确的操作释放一个个结点所用的存储。在Python语言中这个操作很简单，只需简单地将表指针赋值为None，就抛弃了链表原有的所有结点。Python解释器的存储管理系统会自动回收不用的存储。判断表是否为空：将表头变量的值与空链接比较。在Python语言中，就是检查相应变量的值是否为None。判断表是否满：一般而言链表不会满，除非程序用完了所有可用的存储空间。加入元素现在考虑给单链表加入元素的操作，同样有插入位置问题，可以做首端插入、尾端插入或者定位插入。不同位置的操作复杂度可能不同。首先应该注意，在链表里加入新元素时，并不需要移动已有的数据，只需为新元素安排一个新结点，然后根据操作要求，把新结点连在表中的正确位置。也就是说，插入新元素的操作是通过修改链接，接入新结点，从而改变表结构的方式实现的。表首端插入：首端插入元素要求把新数据元素插入表中，作为表的第一个元素，这是最简单的情况。这一操作需要通过三步完成：1）创建一个新结点并存入数据（图3.8a表示要向表头变量head的链表加入新首元素13，为它创建了新结点，变量q指着该结点。这是实际插入前的状态）。

2）把原链表首结点的链接存入新结点的链接域next，这一操作将原表的一串结点链接在刚创建的新结点之后。

3）修改表头变量，使之指向新结点，这个操作使新结点实际成为表头变量所指的结点，即表的首结点（图3.8b表示设置链接的这两步操作完成后的状态，新结点已成为head所指链表的首结点，13成为这个表的首元素。注意，示意图中链接指针的长度和形状都不表示任何意义，只有图中的链接指向关系有意义）。注意，即使在插入前head指向的是空表，上面三步也能正确完成工作。这个插入只是一次安排新存储和几次赋值，操作具有常量时间复杂度。示例代码段：

q = LNode(13)q.next = head.nexthead = q

一般情况的元素插入：要想在单链表里的某位置插入一个新结点，必须先找到该位置之前的那个结点，因为新结点需要插入在它的后面，需要修改它的next域。如何找到这个结点的问题将在后面讨论，先看已经找到了这个结点之后怎样插入元素。

设变量pre已指向要插入元素位置的前一结点，操作也分为三步：1）创建一个新结点并存入数据（图3.9a是实际插入前的状态）。2）把pre所指结点next域的值存入新结点的链接域next，这个操作将原表在pre所指结点之后的一段链接到新结点之后。3）修改pre的next域，使之指向新结点，这个操作把新结点链入被操作的表，整个操作完成后的状态如图3.9b所示。

注意，即使在插入前pre所指结点是表中最后一个结点，上述操作也能将新结点正确接入，作为新的表尾结点。示例代码段：

q = LNode(13)q.next = pre.nextpre.next = q

删除元素

删除链表中元素，也可通过调整表结构删除表中结点的方式完成。这里也区分两种情况：删除表头结点的操作可以直接完成，删除其他结点也需要掌握其前一结点。删除表首元素：删除表中第一个元素对应于删除表的第一个结点，为此只需修改表头指针，令其指向表中第二个结点。丢弃不用的结点将被Python解释器自动回收。图3.10a展示了这个操作。示例代码只有一个语句：

head = head.next

一般情况的元素删除：一般情况删除须先找到要删元素所在结点的前一结点，设用变量pre指向，然后修改pre的next域，使之指向被删结点的下一结点。

图3.10b展示了这个操作。实际删除代码也只有一个语句：

pre.next = pre.next.next

显然，这两个操作都要求被删结点存在。

如果在其他编程语言里删除结点，还可能要自己释放存储。Python的自动存储管理机制能自动处理这方面的问题，使编程工作更简单，也保证了安全性。

扫描、定位和遍历在一般情况下插入和删除元素，都要求找到被删结点的前一结点。另外，程序里也可能需要定位链表中的元素、修改元素、逐个处理其中元素等。这些操作都需要检查链表的内容，实际上是检查表中的一些（或全部）结点。由于单链表只有一个方向的链接，开始情况下只有表头变量在掌握中，所以对表内容的一切检查都只能从表头变量开始，沿着表中链接逐步进行。这种操作过程称为链表的扫描，这种过程的基本操作模式是：

p = headwhile p is not None and 还需继续的其他条件:    对p所指结点里的数据做所需操作    p = p.next

循环的继续（或结束）条件、循环中的操作由具体问题决定。循环中使用的辅助变量p称为扫描指针。注意，每个扫描循环必须用一个扫描指针作为控制变量，每步迭代前必须检查其值是否为None，保证随后操作的合法性。这与连续表的越界检查类似。

上面表扫描模式是最一般的链表操作模式，下面介绍几个常用操作的实现。按下标定位：按Python惯例，链表首结点的元素应看作下标0，其他元素依次排列。确定第i个元素所在结点的操作称为按下标定位，可以参考表扫描模式写出：

p = headwhile p is not None and i > 0:    i -= 1    p = p.next

假设循环前变量i已有所需的值，循环结束时可能出现两种情况：或者扫描完表中所有结点还没有找到第i个结点，或者p所指结点就是所需。通过检查p值是否为None可以区分这两种情况。显然，如果现在需要删除第k个结点，可以先将i设置为k―1，循环后检查i是0且p.next不是None就可以执行删除了。

按元素定位：假设需要在链表里找到满足谓词pred的元素。同样可以参考上面的表扫描模式，写出的检索循环如下：

p = headwhile p is not None and not pred(p.elem):    p = p.next

循环结束时或者p是None；或者pred(p.elem)是True，找到了所需元素。

完整的扫描称为遍历，这样做通常是需要对表中每个元素做一些事情，例如：

p = headwhile p is not None:    print(p.elem)　 　p = p.next

这个循环依次输出表中各元素。只以条件p is not None控制循环，就能完成一遍完整的遍历。同样模式可用于做其他工作。

链表操作的复杂度总结一下链表操作的时间复杂度。创建空表：O(1)。删除表：在Python里是O(1)。当然，Python解释器做存储管理也需要时间。判断空表：O(1)。加入元素（都需要加一个T(分配)的时间）：首端加入元素：O(1)。尾端加入元素：O(n)，因为需要找到表的最后结点。定位加入元素：O(n)，平均情况和最坏情况。删除元素：首端删除元素：O(1)。尾端删除元素：O(n)。定位删除元素：O(n)，平均情况和最坏情况。其他删除：通常需要扫描整个表或其一部分，O(n) 。扫描、定位或遍历操作都需要检查一批表结点，其复杂度受到表结点数的约束，都是O(n) 操作。其他在工作中有此类行为的操作也至少具有O(n)时间复杂度。求表的长度在使用链表时，经常需要求表的长度，为此可以定义一个函数：

def length(head):    p, n = head, 0    while p is not None:        n += 1        p = p.next　　 return n

这个函数采用表扫描模式，遍历表中所有结点完成计数。

显然，这个求表长度的算法所用时间与表结点个数成正比，具有O(n)时间复杂度。实现方式的变化以求表的长度为例，如果程序经常需要调用上面函数，O(n)复杂度就可能成为效率问题。如果表很长，执行该函数就可能造成可察觉的停顿。解决这个问题的一种方法是改造单链表的实现结构，增加一个表长度记录。显然，这个记录不属于任何表元素，是有关表的整体的信息。表示这件事的恰当方法是定义一种链表对象，把表的长度和表中的结点链表都作为这个表对象的数据成分，如图3.11所示。图中变量p指向表对象，这个对象的一个数据域记录表中元素个数（图中的20表示这个表当时有20个结点），另一个域引用着该表的结点链。采用了这种表示方式，求表长度的操作就可以简单返回元素计数域的值。但另一方面，这种表的每个变动操作都需要维护计数值。从整体看有得有失。这种调整消除了一个线性时间操作，可能在一些应用中很有意义。

3.3.3单链表类的实现

前一节讨论了链表的各种操作，以及重要的链表扫描模式。本节基于上面讨论，研究如何所用Python语言实现一个链表类。

3.3.2节定义了链表的结点类LNode，下面是一段简单使用代码：

llist1 = LNode(1)p = llist1for i in range(2, 11):    p.next = LNode(i)    p = p.nextp = llist1while p is not None:    print(p.elem)    p = p.next

第一个循环逐步建立起一个链表，结点元素取整数1到10的值，第二个循环输出表中各结点的元素值。后一循环是前面讨论的扫描循环的实例，前一个for循环用迭代器控制，把一个个新结点链接在已有的表结点链的最后。

根据Python语言的规定，这里的p is not None可以简单地只写一个p。但为清晰起见，本书中没做这种简化。自定义异常为能合理地处理一些链表操作中遇到的错误状态（例如，方法执行时遇到了无法操作的错误参数），首先为链表类定义一个新的异常类：

class LinkedListUnderflow(ValueError):   pass

这里把LinkedListUnderflow定义为标准异常类ValueError的子类，准备在空表访问元素等场合抛出这个异常。在这些情况下抛出ValueError也没问题，但定义了自己的异常类，就可以写专门的异常处理器，在一些情况下可能有用。

Python语言提供了一套预定义的标准异常，每个异常都是一个类，按继承关系形成了一个层次结构，具体情况可以参看2.4节。按Python语言的规定，程序里所有自定义的异常类必须是标准异常类的派生类，更确切地说，它们都应该继承异常类Exception或者它的直接或间接派生类。如果在程序里需要定义异常，就应该从标准异常类中选一个最接近所需的异常，在定义自己的异常时继承这个异常类。LList类的定义，初始化函数和简单操作现在基于结点类LNode定义一个单链表对象的类，在这种表对象里只有一个引用链接结点的_head域，初始化为None表示建立的是一个空表。注意，这个链表基本上是图3.11的设计，但表对象里没有元素计数，增加元素计数域的变形留作练习。判断表空的操作检查 _head；在表头插入数据的操作是prepend，它把包含新元素的结点链接在最前面；操作pop删除表头结点并返回这个结点里的数据：

class LList:    def __init__(self):        self._head = None           def is_empty(self):       return self._head is None       def prepend(self, elem):       self._head = LNode(elem, self._head)           def pop(self):       if self._head is None:  # 无结点，引发异常           raise LinkedListUnderflow("in pop")       e = self._head.elem       self._head = self._head.next       return e

这里把LList对象的_head域作为对象的内部表示，不希望外部使用。再强调一次，Python程序中属于这种情况的域按照习惯用单个下划线开头的名字命名。上面定义里的几个操作都很简单，只有pop操作需要检查对象的状态，表中无元素时引发异常。

后端操作在链表的最后插入元素，必须先找到链表的最后一个结点。其实现首先是一个扫描循环，找到相应结点后把包含新元素的结点插入在其后。下面是定义：

def append(self, elem):    if self._head is None:       self._head = LNode(elem)       return    p = self._head    while p.next is not None:       p = p.next    p.next = LNode(elem)

这里需要区分两种情况：如果原表为空，引用新结点的就应该是表对象的_head域，否则就是已有的最后结点的next域。两种情况下需要修改的数据域不一样。许多链表变动操作都会遇到这个问题，只有表首端插入/删除可以统一处理。

现在考虑删除表中最后元素的操作，也就是要删除最后的结点。前面说过，要从单链表中删除一个结点，就必须找到它的前一结点。在尾端删除操作里，扫描循环应该找到表中倒数第二个结点，也就是找到p.next.next为None的p。下面定义的pop_last函数不仅删去表中最后元素，还把它返回（与pop统一）。在开始一般性扫描之前，需要处理两个特殊情况：如果表空没有可返回的元素时应该引发异常。表中只有一个元素的情况需要特殊处理，因为这时应该修改表头指针。一般情况是先通过循环找到位置，取出最后结点的数据后将其删除：

def pop_last(self):    if self._head is None: # 空表        raise LinkedListUnderflow("in pop_last")    p = self._head    if p.next is None: # 表中只有一个元素        e = p.elem        self._head = None        return e    while p.next.next is not None: # 直到p.next是最后结点        p = p.next    e = p.next.elem    p.next = None    return e

其他操作

LList类的下一个方法是找到满足给定条件的表元素。这个方法有一个参数，调用时通过参数提供一个判断谓词，该方法返回第一个满足谓词的表元素。显然，这个操作也需要采用前面的基本扫描模式。定义如下：

def find(self, pred):    p = self._head    while p is not None:        if pred(p.elem):            return p.elem        p = p.next

最后一个方法非常简单，但实际中可能很有用。在开发一个表类的过程中，人们会经常想看看被操作的表的当时情况：

def printall(self):    p = self._head    while p is not None:        print(p.elem, end='')        if p.next is not None:            print(', ', end='')        p = p.next    print('')

最后的print只是为了输出一个换行符号，其参数是空串。

下面是一段简单的使用链表的代码：

mlist1 = LList()for i in range(10):    mlist1.prepend(i)for i in range(11, 20):    mlist1.append(i)mlist1.printall()

这里先建立一个空表，而后通过循环在表首端加入9个元素（9个整数），又通过循环在表尾端加入9个元素（整数），最后顺序输出表里的所有元素。

表的遍历人们把线性表一类的对象称为汇集（collection）对象，它们本身是对象，其中又包含着一组元素对象。显然，Python内置的list、tuple等都是汇集对象类。对于汇集对象，最典型的使用方法之一就是逐个使用其中的元素，这种操作称为遍历。上面printall是一个完成特定工作的遍历操作，它逐个输出表中元素。实际使用链接表时，可能需要对其元素做各种操作，因此，链表类应该以某种方式支持这一类使用。传统的遍历方式是为汇集对象类定义一个遍历函数，它以一个操作为参数，将其作用到汇集对象的每个元素上。例如，可以考虑为LList定义下面方法：

def for_each(self, proc):    p = self._head    while p is not None:        proc(p.elem)        p = p.next

proc的实参应该是可以作用于表元素的操作函数，它将被作用于每个表元素。假如list1是以字符串为元素的表，下面语句将一行一个地输出这些字符串：

list1.foreach(print)

在经典编程语言的程序里，常常可以看到上面这种传统技术，其优点是比较规范，主要缺点是使用不够灵活，不容易与其他编程机制配合使用。为了解决使用中的不便，人们经常用lambda表达式定制出在这里使用的操作参数。

遍历一组数据是程序中最重要的一类工作方式，新型编程语言都为这类操作提供了专门的支持工具，特别是希望能把对用户定义类型的处理纳入统一的编程形式中。Python语言为内部汇集类型提供的遍历机制是迭代器，标准使用方式是放在for语句头部，在循环体中逐个处理汇集对象的元素，这样就可以很方便地实施各种操作。LList是汇集类型，因此也应该为它提供类似的操作方式，使之能用在标准的操作框架里。在Python语言里，要想定义迭代器，最简单的方式是定义生成器函数。在类里也可以定义具有这种性质的方法。下面是为LList类定义对象的一个迭代器：

def elements(self):    p = self._head    while p is not None:        yield p.elem        p = p.next

有了这个方法，在代码里就可以写：

for x in list1.elements()   print(x)

以这种方式处理链接表，在形式上与处理list或tuple差不多。

筛选生成器如果深入思考，就会看出前面的find方法有点尴尬，经常不适用，因为用它只能取得满足pred的第一个元素。但在被操作的表里可能有多个这样的元素。在经典的编程语言里，这个问题没有很自然的解决方案，但在Python语言（和一些新型语言）中，这件事很容易处理：只需简单改造find方法，定义一个功能与之类似的迭代器。把这种迭代器放在for语句头部，就能在循环体里逐个处理满足条件的表元素了。由于方法的意义改变了，原方法名find已经不合适，下面将新方法命名为filter，表示要基于给定的谓词筛选出表中满足pred的元素。方法定义的改动非常简单：

def filter(self, pred):    p = self._head    while p is not None:        if pred(p.elem):            yield p.elem        p = p.next

这个方法不再是一个普通的方法了。它也是一个生成器方法，使用方式与前面的elements类似，只是需要多提供一个谓词参数。

本节定义了一个简单的链表类，它提供了一些有用的操作。从这些操作的定义中可以看到链表操作函数定义的许多特点。可以根据需要为LList增加其他操作，如定位插入和删除等，这些都留作读者的练习。作为提示，请读者查看Python基本类型list的操作，看看LList里缺了什么，考虑如何为LList类实现它们。