数据结构（2）：链表（上）
数据结构（2）：链表（上）
顺序表可以随时存取表中的任意一个元素，但插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立起数据元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。
单链表的定义
线性表的链式存储又称单链表，它是通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表节点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。
单链表中结点类型的描述如下：
class LinkList:
def __init__(self):
self.data = 0 # 数据域
self.next = None # 指针域
利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散的分布在存储空间中，所以单链表是非随机存取的存储结构，因此不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。
通常用头指针来标识一个单链表，如单链表 L，头指针为 None 时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。
头结点和头指针的区分：不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，节点内通常不存储信息。
引入头结点后，可以带来两个优点：
- 由于第一个数据结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无需进行特殊处理。
- 无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。
单链表上基本操作的实现
在实现单链表上基本操作之前，首先说一下我是基于什么样的单链表：
- 带头节点
- 头结点的数据域记录表长
初始化表
构造一个空的单链表。代码如下：
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 的。
- 基于运算的考虑：在顺序表中按序号访问 a[i] 的时间复杂度为 O(1)，而链表中按序号访问的时间复杂度为O(n)，因此若经常做的运算是按序号访问数据元素，则显然顺序表优于链表。在顺序表中进行插入、删除操作时，平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中进行插入、删除操作时，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然链表优于顺序表。
- 基于环境的考虑：顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的，相对来讲，前者实现较为简单，这也是用户考虑的一个因素。
总之，两种存储结构各有长短，选择哪一种由实际问题的主要因素决定。通常较稳定的线性表选择顺序存储，而频繁进行插入、删除操作的线性表（即动态性较强）宜选择链式存储。
注意：只有熟练掌握顺序存储和链式存储，才能深刻理解它们各自的优缺点。
本文分享自 Python机器学习算法说书人 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！