数据结构（2）：链表（上）

顺序表可以随时存取表中的任意一个元素，但插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立起数据元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。

单链表的定义

线性表的链式存储又称单链表，它是通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表节点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。

单链表中结点类型的描述如下：

class LinkList:
    def __init__(self):
        self.data = 0  # 数据域
        self.next = None  # 指针域

利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散的分布在存储空间中，所以单链表是非随机存取的存储结构，因此不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。

通常用头指针来标识一个单链表，如单链表 L，头指针为 None 时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。

头结点和头指针的区分：不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，节点内通常不存储信息。

引入头结点后，可以带来两个优点：

1. 由于第一个数据结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无需进行特殊处理。
2. 无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。

单链表上基本操作的实现

在实现单链表上基本操作之前，首先说一下我是基于什么样的单链表：

1. 带头节点
2. 头结点的数据域记录表长

初始化表

构造一个空的单链表。代码如下：

   def __init__(self):  # 初始化表
        self.data = 0  # 数据域
        self.next = None  # 指针域

因为头结点的 data 记录长度，空表的长度为 0，所以 data 初始化为 0；又因为空表中头结点的指针域为空，所以 next 初始化为 None。

求表长

返回单链表的长度，即单链表中数据元素的个数。代码如下：

   def length(self):  # 求表长
        return self.data

因为我在头结点的数据域记录了表长，所以直接返回即可。此时时间复杂度为 O(1)。如果头结点没有记录表长，就需要从第一个结点开始顺序依次访问表中的每个结点，为此需要设置一个计数器变量，每访问一个结点，计数器加 1，直到访问到空结点为止。算法的时间复杂度为 O(n)。

需要注意的是，因为单链表的长度是不包括头结点的，因此不带头结点和带头结点的单链表在求表长操作上会略有不同。对不带头结点的单链表，当表为空时，要单独处理。

按值查找操作

从单链表的第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值 e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回 None。

按值查找表结点的算法如下：

     def locate_elem(self, e):  # 按值查找操作
        p = self.next
        while p and p.data != e:  # 从第一个结点开始查找 data 域为 e 的结点
            p = p.next
        return p  # 找到后返回该结点的指针，否则返回 None

按值查找操作的时间复杂度为 O(n)。

按位查找操作

在单链表中从第一个结点出发，顺指针 next 域逐个往下搜索，直到找到第 i 个结点为止，否则返回最后一个结点的指针域 None。

按位查找结点值的算法如下：

    def get_elem(self, i):  # 按位查找操作
        j = 1  # 计数，初始为 1
        p = self.next  # 头结点指针赋给 p
        if i == 0:
            return self  # 若 i 等于 0，则返回头结点
        if i < 1:
            return None  # 若 i 无效，则返回 None
        while p and j < i:  # 从第一个结点开始找，查找第 i 个结点
            p = p.next
            j += 1
        return p  # 返回第 i 个结点的指针，若 i 大于表长则返回 None

按位查找操作的时间复杂度为 O(n)。

插入操作

插入结点操作将值为 e 的新结点插入到单链表的第 i 个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第 i-1 个结点，再在其后插入新结点。

算法首先调用按序号查找算法 self.get_elem(i-1)，查找第 i-1 个结点。假设返回的第 i-1 个结点为 p，然后令新结点 s 的指针域指向 p 的后继结点，再令结点 p 的指针域指向新插入的节点 s。

实现插入结点的代码如下：

    def list_insert(self, i, e):  # 插入操作
        p = self.get_elem(i-1)  # 查找插入位置的前驱结点
        s = LinkList()
        s.data = e
        s.next = p.next  # 1
        p.next = s  # 2
        self.data += 1

算法中，语句 1 和语句 2 的顺序不能颠倒，否则，当先执行 p.next = s 后，指向其原后继的指针就不存在，再执行 s.next = p.next 时，相当于执行了 s.next = s，显然是错误的。本算法主要的时间开销在于查找第 i-1 个元素，时间复杂度为 O(n)。若在给定结点的后面插入新结点，则时间复杂度仅为 O(1)。

删除操作

删除结点操作是将单链表的第 i 个结点删除。先检查删除位置的合法性，后查找表中第 i-1 个结点，即被删节点的前驱节点，再将其删除（Python 会自动给你删掉）。其操作过程如图所示。

假设 p 为找到的被删结点的前驱结点，为实现这一操作后的逻辑关系的变化，仅需修改 p 的指针域。即将 p 的指针域 next 指向 q 的下一节点。

实现删除结点的代码如下：

     def list_delete(self, i):  # 删除操作
        p = self.get_elem(i-1)  # 查找删除位置的前驱结点
        q = p.next  # 令 q 指向被删除结点
        p.next = q.next  # 将 q 从链中断开
        self.data -= 1

和插入算法一样，该算法的主要时间也耗费在查找操作上，时间复杂度为 O(n)。

输出操作

按前后顺序输出单链表中的所有元素值。实现输出操作的代码如下：

    def print_list(self):  # 输出操作
        p = self.next
        if p:
            s = 'LinkList('
            while p.next:
                s += f'{p.data}->'
                p = p.next
            s += f'{p.data})'
            print(s)
        else:
            print('LinkList()')

判空操作

若为空表，则返回 True，否则返回 False。实现判空操作的代码如下：

     def empty(self):  # 判空操作
        return False if self.data else True

采用头插法建立单链表

该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。

头插法建立单链表的算法如下：

   def list_head_insert(self):  # 逆向建立单链表
        x = int(input())  # 输入结点的值
        while x != 9999:  # 输入 9999 表示结束
            s = LinkList()  # 创建新结点
            s.data = x
            s.next = self.next  # 将新结点插入表中，self 为头指针
            self.next = s
            self.data += 1
            x = int(input())

采用头插法建立单链表时，读入数据的顺序与生成链表中的元素的顺序是相反的。每个节点插入的时间为 O(1)，设单链表长为 n，则总时间复杂度为 O(n)。

采用尾插法建立单链表

头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致，则可采用尾插法。该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针 r，使其始终指向当前链表的尾结点。

尾插法建立单链表的算法如下：

    def list_tail_insert(self):  # 正向建立单链表
        r = self  # r 为表尾指针
        x = int(input())  # 设元素类型为整型，输入结点的值
        while x != 9999:  # 输入 9999 表示结束
            s = LinkList()
            s.data = x
            r.next = s
            r = s  # r 指向新的表尾结点
            self.data += 1
            x = int(input())
        r.next = None  # 尾结点指针置空

因为附设了一个指向表尾结点的指针，故时间复杂度和头插法相同。

双链表

单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个节点的前驱结点（插入、删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为 O(1)，访问前驱结点的时间复杂度为 O(n)。

为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针 prior 和 next，分别指向其前驱结点和后继结点。

双链表中结点类型的描述如下：

class DLinkList:
    def __init__(self):
        self.data = 0  # 数据域
        self.prior = self.next = None  # 前驱和后继指针

双链表在单链表的结点中增加了一个指向其前驱的 prior 指针，因此双链表中的按值查找和按位查找的操作与单链表的相同，但双链表在插入和删除操作的实现上，与单链表有着较大的不同。这是因为“链”变化时也需要对 prior 指针做出修改，其关键是保证在修改过程中不断链。此外，双链表可以很方便的找到其前驱结点，因此，插入、删除操作的时间复杂度仅为 O(1)。

双链表的插入操作

在表中第 i 个位置上插入指定元素 e。插入操作的代码如下：

     def list_insert(self, i, e):
        p = self.get_elem(i-1)
        s = DLinkList()
        s.data = e
        s.next = p.next  # 将节点 s 插入到结点 p 之后
        p.next = s
        s.prior = p

双链表的删除操作

删除表中第 i 个位置的元素。删除操作的代码如下：

      def list_delete(self, i):
        p = self.get_elem(i-1)
        q = p.next
        p.next = q.next
        if q.next:
            q.next.prior = p

在建立双链表操作中，也可以采用如同单链表的头插法和尾插法，但在操作步骤上需要注意指针的变化和单链表有所不同。

循环链表

循环单链表

在循环单链表中，表尾结点 r 的 next 域指向 L，故表中没有指针域为 None 的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。

循环单链表的插入、删除算法与单链表几乎一样，所不同的是若操作在表尾进行，则执行的操作不同，以让单链表继续保持循环的性质。当然，正是因为循环单链表是一个“环”，因此在任何一个位置上的插入和删除操作都是等价的，无需判断是否是表尾。

在单链表中只能从表头结点开始往后遍历整个链表，而循环单链表可以从表中的任意一个结点开始遍历整个链表。有时对单链表常做的操作是在表头和表尾进行的，此时对循环单链表不设头指针而设尾指针，从而使操作效率更高。其原因是，若设的是头指针，对表尾进行操作需要 O(n) 的时间复杂度，而若设尾指针 r，r->next 即为头指针，对表头和表尾进行操作都只需要 O(1) 的时间复杂度。

循环双链表

由循环单链表的定义不难推出循环双链表。不同的是在循环双链表中，头结点的 prior 指针还要指向表尾结点，如图所示。

在循环双链表 L 中，某结点 p 为尾结点时，p->next==L；当循环双链表为空表时，其头结点的 prior 域和 next 域都等于 L。

静态链

静态链表借助数组来表述线性表的链式存储结构，结点也有数据域 data 和指针域 next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间。

静态链表结构类型描述如下：

class LNode:
    def __init__(self):
        self.data = None  # 存储数据元素
        self.next = -1  # 下一个元素的数组下标


class SLinkList:
    def __init__(self, max_size=50):
        self.list = [LNode()for _ in range(max_size)]

静态链表以 next==-1 作为其结束的标志。静态链表的插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动元素。总体来说，静态链表没有单链表使用起来方便，但在一些不支持指针的高级语言（如 Basic）中，这是一种非常巧妙的设计方法。

顺序表和链表的比较

存取（读写）方式

顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。例如在第 i 个位置上执行存或取的操作，顺序表仅需一次访问，而链表则需从表头开始依次访问 i 次。

逻辑结构与物理结构

采用顺序存储时，逻辑上相邻的元素，对应的物理位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理位置上则不一定相邻，对应的逻辑关系是通过指针链接来表示的。

查找、插入和删除操作

对于按值查找，顺序表无序时，两者的时间复杂度均为 O(n)；顺序表有序时，可采用折半查找，此时的时间复杂度为 O(log₂n)。

对于按序号查找，顺序表支持随机访问，时间复杂度仅为 O(1)，而链表的平均时间复杂度为 O(n)。顺序表的插入、删除操作，平均需要移动半个表长的元素。链表的插入、删除操作，只需修改相关结点的指针域即可。由于链表的每个结点都带有指针域，故而存储密度不够大。

空间分配

顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。链式存储的结点空间只在需要时申请分配，只要内存有空间就分配，操作灵活、高效。

在实际应用中应该怎样选取存储结构呢？

1. 基于存储的考虑：难以估计线性表的长度或存储规模时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度低，显然链式存储结构的存储密度是小于 1 的。
2. 基于运算的考虑：在顺序表中按序号访问 a[i] 的时间复杂度为 O(1)，而链表中按序号访问的时间复杂度为O(n)，因此若经常做的运算是按序号访问数据元素，则显然顺序表优于链表。在顺序表中进行插入、删除操作时，平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中进行插入、删除操作时，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然链表优于顺序表。
3. 基于环境的考虑：顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的，相对来讲，前者实现较为简单，这也是用户考虑的一个因素。

总之，两种存储结构各有长短，选择哪一种由实际问题的主要因素决定。通常较稳定的线性表选择顺序存储，而频繁进行插入、删除操作的线性表（即动态性较强）宜选择链式存储。

注意：只有熟练掌握顺序存储和链式存储，才能深刻理解它们各自的优缺点。