线性表是最简单也是最基本的一种线性数据结构。在程序中,如果需要将一组(通常是
同为某一种类型)数据元素作为有序序列进行整体管理和使用时,则往往创建线性表这种数
据结构。因此,一个线性表不仅是某类元素的一个集合,而且记录着元素之间的一种顺序关
系。它通常有两种存储表示方法:顺序表和链表,它的主要基本操作是插入、删除和查找
等。线性表在实际程序中应用非常广泛,还往往被用作更复杂数据结构的实现基础。在
Python语言中,内置的列表类型list可以支持这种类型的操作需求,常用来作为线性表的
顺序实现方式。本章将学习线性表的基本概念及其两种存储表示方式、链表的变形及一些
应用实例。
3.线性表的概念
1
3.1.1
基本术语和概念
线性表是
n
个(n=0称为空表)数据元素的集合:表中各个数据元素具有相同特
n≥0,
性,表中相邻的数据元素之间存在“一对一的序偶”关系。通常记为
(e2,…,i+1,…,)
e1,e-een1,n
i1,i,e-e
其中,-1领先于ei,称e-1是e的直接前驱元素,是e-1的直接后继元素。在非空线性
表中,存(e) 在着唯一的一个表(i) 首元素(i) 和唯一的一个表尾(e) 元素。(i) 除表首元素之外,(i) (i) 表中的其他元
素均有且仅有一个直接前驱元素;除表尾元素之外,表中的其他元素均有且仅有一个直接后
继元素。
例如,某个集合中只有4个整数1、2、3、4,而且1与2之间、2与3之间、3与4之间都存
在一对一的顺序关系,那么就说这个集合是一个线性表。
可以表示为
E1={1,2,3,4}
R1={(1,2),(2,3),(3,4)}
L1=(E1,R1)
该线性表实例如图3.在这个例子中,3是2的直接后继。对
1所示,2是3的直接前驱,
于表首元素1来说,只有直接后继元素2;而尾元素4则只有直接前驱元素3。
图3.线性表的实例
1
3.1.2
线性表的操作
作为一种包含元素的数据结构,线性表通常都会支持一些基本操作,例如,如何创建和
销毁一个线性表、如何判断表是否为空、如何没有重复和没有遗漏地访问表中的每一个元
素、如何往表中插入或者从表中删除一个元素等。在很多实际问题的求解中,如果用到了线
性表,对表的操作往往能转换成一个或者多个基本操作的组合或者升华,从而完成程序中的
各类应用要求。
从作用性质来看,线性表结构的基本操作可以分为以下三类。
(1)构造操作:用于构造出该数据结构的一个新实例
。
initList():表构造操作,创建一个新表
。
destroyList():表销毁操作,销毁已存在的一个表
。
(2)访问操作:用于从已有该数据结构的实例中提取某些信息,但不创建新结构实例,
也不修改被操作的结构实例。
is_empty():判断是否为一个空表。
len():获得表的长度。
search(elem):查找元素elem在表中出现的位置,不出现时返回-1。
getelem(:取出表中第
i
个元素,ne。
i)
i
不合法时返回No
traverse():依次访问表中的每个元素
。
(3)变动操作:用于修改已有的该数据结构实例
。
prepend(elem):将元素elem加入表中作为第一个元素
。
append(elem):将元素elem加入表中作为最后一个元素
。
inserelem,
l
t(i):将eem加入表中作为第
i
个元素,其他元素的顺序不变
。
delFirst():删除表中的首元素
。
delLast():删除表中的尾元素
。
dei)
l(:删除表中第
i
个元素。
foral(op):对表中的每个元素执行操作op。
上述各个操作的定义仅对抽象的线性表而言,定义中尚未涉及线性表的存储结构以及
实现这些操作所用的编程语言,不同的编程语言也可能会影响需要实现的基本操作集合,例
如,Python能自动回收不用的对象,因此不需要专门实现销毁结构的操作。目前,利用这些
基本操作可以避开技术细节完成研究算法、分析问题等工作。
64
从支持操作类型的角度看,线性表结构又可以分为以下两类。
(1)不变数据结构:该结构只支持构造操作和访问操作,不支持变动操作。创建之后,
结构和存储的元素信息都不改变,所有得到该类结构的操作都是创建新的结构实例。例如,
Python中的tuple和frozenset类型。
(2)变动数据结构:该结构支持变动操作。在创建之后的存续期间,其结构和所保存
的信息都可能变化。例如,Python中的list、dict、set等类型。
3.1.3
线性表的实现基础
对于3.2节中介绍的线性表需要实现的基本操作,
1.都要依托于线性表的具体存储结
构加以实现,通常情况下,基于计算机内存中存储数据的特点以及各种重要操作实现的效
率,提出了以下两种线性表的存储表示方法。
(1)顺序存储表示:将表中元素顺序地存放在一大块连续的存储区里,采用这种存储
结构的线性表称为“顺序表”。
(2)链式存储表示:将表元素存放在通过链接构造起来的一系列存储块里,采用这种
存储结构的线性表称为“链表”。
3.顺序表
2
3.2.1
顺序表的定义
在计算机中表示线性表的最简单直观的方法是将表中的数据元素按顺序存放在一片足
够大的地址连续的存储单元里,即从首元素开始将线性表中的数据元素一个挨着一个地存
放在某个存储区域中,这种存储方式称为线性表的顺序存储表示。相应地,把采用这种存储
结构的线性表称为顺序线性表,简称为顺序表。
顺序表中元素之间的逻辑顺序关系与元素在存储区里的物理位置保持一致,因此只要
是一个表里保存的元素类型相同,则采用顺序表结构可以方便地实现元素随机存取,即表中
任何元素的位置计算非常简单,可以在O(1)时间内完成随机访问操作。
设有一个顺序表对象,存储在一片连续的内存区域中,该存储区的起始地址为L0,存储
oe0)
在L0 处的元素为e0,即Lc(=L0,若表中每一个元素
需要用的存储单元个数为a,则表中第
i
个元素ei
的地址计
算公式为(
Loe=L0+i×a
i
从0开始)
c(i)
2所示。
顺序表的元素存储布局情况如图3.
如果表元素大小不统一,则若按照上述方式将表元素
依序存放在一个存储区域中,则无法使用以上方式来计算
元素地址,这时可以采取以下策略完成顺序结构的定义,即
将实际元素的引用链接保存在一个顺序表中。由于每个链
接所需的存储大小相同,则还是可以通过上述公式,计算出
65
图3.2顺序表的元素存
储布局示意
各个索引的元素链接的存放位置,对链接做一次间接访问,即可得到实际元素的数据了,具
体实现方法就不展开详述了。
3.2.2
顺序表的基本实现
建立了线性表之后,一项重要的操作是可以往其中动态地加入或者删除元素,也就是
说,在一个表存续期间,其长度可能会发生变化。那么在建立表时应采用多大的连续存储区
则是一个必须要考量的问题,因为对于顺序存储,存储块一旦分配,就有了大小确定的元素
容量。若要考虑变动的表,就需要区分存储区容量和表中元素个数这两个概念。因此,可以
增设两个变量max和n,分别记录元素存储区的容量,以及当前表中实际的元素个数。在
发生插入或删除等表元素变化的操作时,可同步更新
n
的值,这就是顺序表的一般结构,如
图3.
3所示。
在以上结构中,采用了列表作为顺序表存储对象,max表示表的容量,
n
记录表中实际
元素的个数。在此基础之上,线性表的一些基本操作则很容易实现,本节只讨论顺序表的几
个主要操作的实现算法。
1.
创建和访问操作
创建空表:即构造一个空的顺序表。需分配一块元素存储区域,记录表的容量并将元
素计数值设置为0,如图3.在创建表的同时,
4中是一个容量为8的空表, 应将表信息域的
max和
n
设置好,保证顺序表的合法性。
图3.3
顺序表的一般结构示例4
图3.新建的空顺序表
简单判断操作:即判断表是否为空或者是否为满的操作。因为顺序表结构拥有记录表
的容量和元素计数值的信息域max和n,所以判断表空和表满的操作都很简单,表空即判
断
n
是否为0,表满即判断
n
是否等于max,两个操作的时间复杂度均为O(1)。
访问指定索引元素操作:即给定索引i,访问顺序表第
i
个元素。通常首先需要进行
i
值的合法性判断,即0≤i≤n-1。若超出该范围则是非法访问,若索引合法,则可利用3.2.
节中的地址计算公式,由内定位置得到元素的值,前文已经分析了,该操作不依赖于表的大
小,时间复杂度为O(1)。
查找元素操作:即在顺序表中查找其值与给定的值相等的数据元素,并返回其在元素
表中出现的索引,该操作又称为检索。通常会从表中的第一个元素开始,依次和所给的值进
行比较,一旦找到一个与该值相等的数据元素,则返回它在表中的“位序”(即索引)。如果直
66
到表内所有元素都比较完也没有找到相等元素,则返回一个特殊值(如“-1”)。有时候也会
要求查找在表中某一指定位置
k
之后是否存在所查找的对象,可只需要从k+1 位置的元
素开始比较即可,查找元素操作的时间复杂度为O()。
n
2.
变动操作
删除元素:即从已有顺序表中删除指定索引位置的元素。这种删除操作通常都会要求
实现保序定位删除,即不仅需要保证删除操作结束后,剩余元素在内存中仍然是连续存放
的,而且还需要保持剩余元素的相对顺序。因此,一个可行的实现办法就是从待删元素的下
一位置起,逐个顺序地将元素上移覆盖。如图3.开始有5个元素,
5所示的这个顺序表, 计
划要删除位置2处的108,则可以将位置3上的44 上移到位置2,将位置4上的1024 上移
到位置3,最后将元素计数变量
n
减1,有效元素更新为4个,对应存放在位置0到位置3,
而位置4上的元素就不是表中的有效元素了,通过这种方式实现顺序表的删除操作。这种
删除操作实现的时间主要花费在元素的挪动上面。对于元素个数为
n
的表,删除表首元素
需要挪动n-1个元素,是效率最低的;而删除表尾元素则无须挪动元素,是效率最高的。
假设在任一位置上删除元素的概率相同,则删除顺序表中的某一元素平均需要挪动约一半
的元素,因此, n
该操作的时间复杂度为O()。
图3.顺序表删除元素操作
5
插入元素:即在已有顺序表中指定索引位置插入一个元素。这种插入操作通常也都会
要求实现保序定位插入,即不仅需要保证操作后所有的元素是连续的,而且原来元素的相对
顺序不变。只是在具体实现插入时为了避免错误覆盖,需要逆序,即从最后一个元素起到原
来插入位置上的元素,从后往前,逐个往后挪一位,从而腾出位置给待插入的新元素。如
图3.以在目前这个元素个数为4的表中, 在插入元
6所示, 在位置2处插入元素108 为例,
素之前,需要先把位置2上的44 往后挪到位置3处,但是,位置3上有元素1024,所以需要
先把1024 往后挪,这里恰好1024 就是表中最后一个元素,因此,可以把它直接往后挪动一
个位置,位置3上的1024 后移之后,位置3就相当于可以被覆盖了,这时就可以把44 后移
到位置3上,此时,位置2这个指定插入位置就准备就绪了。将待插入的元素108 放进去即
可。插入新元素后,需将元素计数变量
n
加1。对于元素个数为
n
的表,在表首插入元素需
要挪动
n
个元素,是效率最低的;而在表尾插入元素则无须挪动元素,是效率最高的。假设
在任一位置上插入元素的概率相同,则在顺序表中插入某一元素平均也需要挪动约一半的
元素,因此, n
该操作的时间复杂度也为O()。
对于插入操作需要注意的一点是:在插入元素前需要检查表是不是已经满了。如果
67
68
图3.6 顺序表插入元素操作
是,插入前就需要更换一片更大的存储空间,然后把已有的元素一个个都“腾挪”过去,这也
是需要消耗时间的。由于Python中的列表类型在内存中占据的即是一个地址连续的存储
区域,因此可以直接采用Python的列表来描述顺序表中数据元素的存储区域。Python的
列表类型采用一种等比扩容的策略,如图3.7所示,比如最初分配的表容量是4,第一次满时
扩到8,第二次满时扩到16,以此类推,容量呈指数增长。在这种策略下,可以保证尾端操作
的平均复杂度仍为O(1)。
图3.7 Python列表的空间分配策略
由于Python列表不需要预先分配大小,所以通常情况下直接定义一个列表结构,并采
用列表的相关函数和方法就可以完成顺序表的一些基本操作,必要时也可额外设置变量
max表示表的最大范围。这里就不给出在Python里定义顺序表的实际代码了。
3.2.3 顺序表例题
例3.1 (力扣27)移除元素。
【题目描述】
给定一个可能包含重复元素的无序列表nums和一个确定的数值val,设计算法实现原
地移除数组中所有数值等于给定值val的元素,并返回移除后数组的新长度k。算法空间复
杂度要求为O(1)。
例如,当nums=[3,2,2,3],val=3时,应返回2;而当nums=[0,1,2,2,3,0,4,2],
val=2时,应返回5。
【解题思路】
由于题目明确要求算法空间复杂度为O(1),则不能采取新建顺序表,将原表中不等于
val的元素添加到新表中的策略,只能采取原表操作,需遍历顺序表的同时删除与val相等
的元素。若此时选择从前往后遍历,当遇到同val相等的元素删除时,后边的元素会自动覆
盖到被删除元素的位置上,此时循环会略过这个前移的元素往下走,造成遍历的遗漏。因
此,应采用逆序遍历来实现移除过程。
【参考代码】
def removeElement(self, nums: List[int], val: int) -> int:
for i in nums[::-1]:
69
if i == val:
nums.remove(i)
return len(nums)
例3.2 跑道上的小朋友。
【题目描述】
在一条总长为m 米的直线跑道上,每隔1米就站着一个小朋友。这条跑道可以被想象
成一条数轴,其中,数轴的起点位于0,终点位于m ;数轴上的每个整数值点,即0,1,2,…,
m ,都对应着一个小朋友的位置。现在,由于学校活动需要,部分跑道区域将被划为比赛区
域。这些比赛区域可以通过它们在数轴上的起始和终止位置来界定。每个区域的起始和终
止位置都是整数,并且不同的区域可能会有重叠部分。这些区域可以通过一个包含多组起
始和终止位置的列表ls来标识。设计算法计算在移除所有比赛区域内的小朋友(包括区域
边界上的小朋友)之后,跑道上剩余的小朋友总数。
例如,当m =400,ls=[(25,75),(50,150),(158,358)]时,应返回74。
【解题思路】
定义一个恰好含有m +1个元素的顺序表flag表示每个位置上有无小朋友,flag[i]为
1表示i 号位置有小朋友,否则表示无小朋友。则让小朋友离开该点的操作,仅需将flag中
对应的元素变为0。最后统计flag中1的个数(对flag列表求和)即可。
【参考代码】
def childCount(m, ls):
flag = [1]* (m + 1)
for begin, end in ls:
flag[begin : end + 1]= [0]* (end - begin + 1)
return sum(flag)
3.3 单链表
3.3.1 单链表的定义
3.2节介绍的顺序表是使用一组连续的存储单元来存放线性表中的元素,元素间的顺
序关联是由元素在物理存储器中的相对位置来自然满足的。本节介绍的单链表数据结构同
样是一种线性表,但它是链式存储结构,可以用一组地址任意的存储单元来存放线性表中的
数据元素,在这种存储机制下,需要为每个元素附加链接来指示其直接后继的存储位置,即
用链接显式地表示元素之间的顺序关联。单链表的元素存储布局情况如图3.8所示。
图3.8 单链表的元素存储布局
单链表有一个至关重要的表头变量(也常称为表头指针),它记录了单链表中第一个结
点的位置信息,通过它就可以顺着链找到每一个结点。对于表尾元素,虽没有直接后继,但
70
为了保持一致性,也给它添加一个链接,在Python中它的值就设为None,图示时用^表示。
通常,对于一个已经建好的单链表,只需要记住其表头变量就可以了,因此也常用表头变量
来代表一个单链表。
单链表的优点是不需要大片连续的存储区域,内存动态管理灵活,在指定结点后插入结
点或者删除指定结点的直接后继时效率很高,复杂度是O(1)。但是,单链表在查找或访问指
定索引值的结点时,需要从表头一个一个循链接遍历下去,因此效率比较低,复杂度为O(n)。
3.3.2 单链表的基本实现
单链表是由一个个数据结点构成的。每个结点含有两个信息域,一个表示元素本身,称
图3.9 单链表结点构成
为元素域;另一个表示直接后继的存储位置,称为链接域。结点构成
如图3.9所示。
Python并没有提供现成的单链表类型,要想使用单链表,需要
自定义相应的类。由于单链表是由一个个结点链接而成的,所以,首先需要定义表示结点的
类型。这里使用class保留字定义一个名为ListNode的类来表示单链表中的结点。它包含
两个属性:val和next,分别表示结点的元素值和直接后继链接,其定义如下。
class ListNode:
def _ _init_ _(self, val, next_=None):
self.val = val
self.next = next_
ListNode类里只包含一个初始化方法,用于实现给实例对象的val和next两个属性赋
值。该方法的最后一个形参命名为next_,是为了避免与Python标准函数next重名,这也
符合Python的命名惯例。
定义了结点类之后,即可通过以下逐一建立结点的方法生成一个简单的单链表。该链
表有4个结点,结点元素值从头到尾依次为1、2、3、4,表头变量用head来表示。
node4 = ListNode(4)
node3 = ListNode(3, node4)
node2 = ListNode(2, node3)
node1 = ListNode(1, node2)
head = node1
在上面的代码中,每个结点的链接域存放的是它的直接后继的对象名。在建立一个结
点之前,如果该结点的后继结点已存在,则该结点的链接域的设置就会十分简单,因此,逆序
创建链表是一个很自然的选择。上述代码的执行过程如图3.10所示。首先实例化一个
ListNode类的对象node4表示结点4,该结点的链接域next_属性采用默认值None,对象名
node4中就包含该结点在内存中的地址信息,因此可以将该对象名作为结点3的链接域来
创建结点3,以此类推,创建了结点2和结点1,而结点1的对象名node1也对应着链表首结
点的位置,因此,将其赋给表头变量head来表示整个单链表。
如果需要创建一个含有更多个结点的单链表,也可以采用类似的方式,并且可以使用循
环来简化相似的代码。例如,要想创建结点元素值依次为1~n 的单链表head,可以使用以
下代码来实现逆序创建过程。
71
图3.10 单链表的逆序创建
p = None
for i in range(n, 0, -1):
p = ListNode(i, p)
head = p
也可以采用顺序方式创建结点元素值依次为1~n 的单链表,过程比逆序创建略微复
杂,需要设置一个辅助变量p,用于记录当前创建的结点位置,实现代码如下。
head = ListNode(1)
p = head
for i in range(2, n + 1):
p.next = ListNode(i)
p = p.next
这段代码的执行流程如图3.11所示。首先创建结点1,让表头变量head指向它,结点
1的链接域为空,同步创建变量p 让其指向结点1;接着创建第二个结点,并设置p.next的
值为新建立的结点2,即让第一个结点链接上了第二个结点。然后,通过执行p=p.next,让
变量p 指向当前创建完毕的第二个结点。以此类推,让结点顺序被创建,逐个被链接,形成
最终的单链表。
图3.11 单链表的顺序创建
72
单链表建立之后,若要实现从头到尾顺序遍历单链,则也可以借助一个p 指针,从链表
头开始,依次后移,通过循环的方式实现。代码如下,在该遍历过程中实现了以每行一个元
素的方式输出表中各元素的值。
p = head
while p:
print(p.val)
p = p.next
3.3.3 单链表基本操作的实现
本节讨论单链表的几个主要操作的实现算法。
1. 创建和访问操作
创建链表:从3.3.2节中得知要掌握一个单链表,需要且仅需要掌握该表的表头变量。
因此,可以按如下方式定义一个单链表类LList。
class LList:
def _ _init_ _(self):
self._head = None
LList类只包含一个名为_head的属性,表示表头变量,在LList类的初始化函数里,它
被直接设置为空链接(None)。因此,可以通过诸如mlist=LList()的方式来实例化一个空
链表mlist。
但若想实现根据传入的列表来构建一个单链表,让单链表中结点自表头起依次存放列
表中自表头起的每一个元素,则需要修改LList类的初始化函数,为其增加一个形参ls用以
接收传入的列表。同时,可以采用逆序方式或者顺序方式根据ls中的元素值逐个创建
ListNode型的结点,从而建立单链表,并将表头变量赋给self._head即可。其代码实现参考
代码清单3.1中的魔术方法__init__。
判断是否为空表:判断是否为空链表只需要判断表头变量的值是否为None即可。其
代码实现参考代码清单3.1中的实例方法is_empty。该操作的时间复杂度为O (1)。而对
于单链表,是不需要判断表是否已满的,因为结点可以存放在任意位置上,不存在表满一说,
除非所有存储空间用完。
求表长:在顺序表中,求表长的时间复杂度是O(1),因为表中设置了专门的元素个数
计数变量。但求单链表的表长需要从表头开始,顺着链表一个结点一个结点地数,直到最后
一个结点被数完为止。其代码实现参考代码清单3.1中的魔术方法_ _len_ _。该方法的时
间复杂度为O(n)。
将单链表转换字符串:在实际应用中,常常需要将表中的元素转换为某种形式的字符
串,如“[1,2,3,4]”这种列表形式的字符串。这也需要从表头开始,顺着链表一个结点一个
结点地将其元素值以要求的字符串形式拼接在一起,直到最后一个结点被拼完为止。其代
码实现参考代码清单3.1中的魔术方法__str__。该方法的时间复杂度为O(n)。
2. 变动操作
定位插入元素:定位插入元素操作即要求在表中第i 个结点之后插入一个新元素。在
73
链表中加入新元素时,并不需要移动已有的元素,只需要建立一个新结点,然后根据位置要
图3.12 在单链表表
头插入元素
求以修改链接的方式将新结点插入链表即可。定位插入元素操作
的代码实现参考代码清单3.1中的实例方法insert。但针对不同位
置的操作复杂度可能不同。
假定传入的i 值合法,也就是它的值大于或等于0并且小于或
等于表长。当i 等于0时,表示插到表头结点之前,成为新的表头结
点。例如,目前表中有3、4两个结点,要想在表头插入结点q,则可
以通过将q 的后继链上表头结点,然后将表头变量更新为q 即可,
实现过程如图3.12所示。
而对于一般的情况,即i 大于0且小于或等于表长时,则需要通
过从表头结点开始计数,来找到第i 个结点。这里的计数类似于求
表长的操作,不同之处在于count的初值设为1,表示表头结点是第
1个结点。设p 初始指向头结点,循环条件count<i 则表示还没有数到第i 个结点时就继
续循环;p 指针不断后移,当循环停止时,p 所指的就是第i 个结点。之后,将q 插到p 之
后,也就是将p 的后继变成q 的后继,而q 本身成为p 的后继即可,实现过程如图3.13
所示。
图3.13 在单链表第i(i 大于0且小于或等于表长)个位置插入元素
从以上分析可以得出,对于单链表的插入操作,在表头插入最快,其时间复杂度为O(1),
在表尾插入最慢,在任意位置处插入时,平均需要寻找约一半的结点,其时间复杂度为O(n)。
借助以上定位插入元素的方法,可便捷地使用单链表类逆序创建一个元素依次为1~n
的单链表,实现代码如下。
mlist = LList() #实例化一个空表mlist
n = int(input()) #n 个元素,值依次为1,2,3,…,n
for i in range(n, 0, -1): #逆序,在表头插入元素
mlist.insert(0, i)
74
定位删除元素:定位删除元素操作即要求删除表中第i 个元素对应的结点,并返回该
元素值。该操作的前提是:表非空,且i 是1和表长之间的任意值。同样,在链表中删除元
素时,也不需要移动已有的元素,只需要定位到待删除结点的前驱结点,然后重置其后继结
点为待删除结点的后继结点即可。定位删除元素操作的代码实现参考代码清单3.1中的实
例方法delete。针对不同位置的操作复杂度也不同。
假定传入的i 值合法,当i 等于1时,表示要删除当前的表头元素,则只需取出表头元
素值,并将表头变量后移一位即可,实现过程如图3.14所示。
图3.14 删除单链表表头结点
而对于一般的情况,即i 大于1且小于或等于表长时,则先需要通过从1开始的计数来
找到第i-1个结点,并令p 指向该结点;然后,通过设置p.next=p.next.next的方式实现
将第i 个结点删除的目的。以删除这个单链表的第4个结点为例,其实现过程如图3.15
所示。
图3.15 删除单链表第i(i 大于1且小于或等于表长)个结点
从以上分析可以得出,对于单链表的删除操作,仍然是在表头删除最快,其时间复杂度
为O(1),在表尾删除最慢,在任意位置处删除元素,平均也需要寻找约一半的结点,其时间
复杂度也为O(n)。
代码清单3.1 定义单链表LList类
#定义单链表结点类
class ListNode:
def _ _init_ _(self, val, next_=None):
self.val = val
self.next = next_
75
class LList:
def _ _init_ _(self, ls=None): #根据传入的列表ls 逆序创建单链表
p = None
for item in ls[::-1]:
p = ListNode(item, p)
self._head = p
def is_empty(self): #用于判断表是否空
return self._head is None
def _ _len_ _(self): #计算表长并返回
p = self._head
count = 0
while p is not None:
count += 1
p = p.next
return count
def _ _str_ _(self): #将单链表转换为列表形式的字符串
p = self._head
s = ""
while p is not None:
s += str(p.val) + ","
p = p.next
return "[" + s[:-1]+ "]"
def insert(self, i, val): #在表中第i 个结点后插入元素值为val 的新结点
q = ListNode(val)
if i == 0:
q.next = self._head
self._head = q
return
p = self._head
count = 1
while count < i:
p = p.next
count += 1
q.next = p.next
p.next = q
def delete(self, i): #删除表中的第i 个结点,并将其元素值返回
if i == 1:
e = self._head.val
self._head = self._head.next
return e
p = self._head
count = 1
while count < i - 1:
p = p.next
count += 1
e = p.next.val
p.next = p.next.next
return e
3.3.4
单链表例题
例3.(力扣206)反转链表。
3
【题目描述】
给定单链表的头结点head,设计算法反转链表,并返回反转后的链表。注意,空链表反
转后仍为空链表;本题链表中结点的数目范围是[0,5000],5000≤Nod.al≤5000 。
-ev
例如,图3.
16 中显示了一个链表反转前后的形态。
图3.反转链表示例
16
【解题思路】
本题采用头部删除加头部插入策略,则无须创建额外空间,算法空间复杂度为O(1), 实
现过程如下。
(1)定义变量p,用于记录结果链表的表头。初始时设置
p
为None。
(2)遍历单链表head,循环执行以下操作直至head为None。
① 定义变量q,用于指向当前待操作结点,每次循环开始都指向当前表头结点即可。
② 从单链表hed中删除表头结点(即hed=hanxt,让表头变量had顺链后移一
个结点即可), 注意,
a
此时表头结点仅剩变量
q
a
来指向
e
。
d.ee
新的表头
将
。
q
所指结点插到结果链表
p
的表头结点之前(即q.
q
就成为结果链表
③ next=p),
④ 更新p,让它始终指向结果链表的表头结点(即p=q)。
链表反转过程如图3.17 所示,每次从原链表中删除首结点,再将其插到结果链表的表
头,从而实现链表的逆序。
图3.链表反转过程
17
76
77
【参考代码】
def reverseList(self, head: ListNode) -> ListNode:
p = None
while head is not None:
q = head
head = head.next
q.next = p
p = q
return p
例3.4 (力扣LCR136)删除链表的结点。
【题目描述】
给定单向链表的头指针head和一个要删除的结点的值val,设计算法删除该结点。返
回删除后的链表的头结点(题目保证链表中结点的值互不相同,且val一定存在于链表中)。
例如,图3.18显示了在一个单链表中删除值为5的结点前、后的形态。
【解题思路】
本题采用首先定位结点再修改引用的策略,实现过程为:遍历单链表head,直到某一结
点的元素域和所给val值相等,即可定位目标结点cur。设结点cur的前驱结点为pre,后继
结点为cur.next,则执行pre.next=cur.next,即可实现删除cur结点,删除过程如图3.19
所示。
图3.18 删除链表的结点示例
图3.19 链表中删除给定值结点
可以通过从头开始遍历、逐个结点地查看其元素值是否为val的方式找到结点cur,该
操作时间复杂度为O(n)。还有个关键问题是:如何确定cur的直接前驱结点pre。因为在
单链表中,可以通过结点的链接域以O (1)的复杂度定位其直接后继,但是并无链接域以
O(1)的复杂度定位其直接前驱。若想找到其直接前驱,一个自然的思路也是从头开始遍
历,逐个结点地查看其后继是否为指定结点cur。显然,可以在查找结点cur的同时,亦步亦
趋地记录下cur的前驱pre。即开始时初始化pre=None以及cur=head,然后,当每次cur
需要顺链后移(即cur=cur.next)时,先让pre=cur,然后cur再后移。这样当找到了cur结
点的时候,也记录下了其直接前驱pre。
本题算法中这种以亦步亦趋的方式同时记录了当前结点及其前驱结点,并同步沿着
链表向后边探索边移动的方法,称为“蠕动”,是解决单链表指定元素查找和删除的常用
方法。
78
【参考代码】
def deleteNode(self, head: ListNode, val: int) -> ListNode:
cur = head
pre = None
while cur.val != val:
pre = cur
cur = cur.next
if not pre:
head = head.next
else:
pre.next = cur.next
return head
例3.5 (力扣24)两两交换链表中的结点。
【题目描述】
给定一个链表head,设计算法两两交换其中相邻的结点,并返回交换后链表的头结点。
图3.20 两两交换链表
中的结点示例
注意:必须在不修改结点内部的值的情况下完成本题(即
只能进行结点交换)。
例如,图3.20显示了两两交换一个单链表中的结点
前、后的形态。
【解题思路】
可以从前往后依次对相邻的每对结点进行交换处理,
为了让第一对结点也和后面的处理模式相同,可以在
head前先设置一个虚拟的头结点dummy_head,另设置一个p 表示当前到达的结点,初始
时p=dummy_head,每次需要交换p 后面的两个结点。如果p 的后面没有结点或者只有
一个结点,则没有更多的结点需要交换,因此结束交换。否则,获得p 后面的两个结点分别
记作a 和b,通过更新结点的指针关系实现两两交换结点,交换过程如图3.21所示。
图3.21 单次交换结点p 后的两个结点a、b 的过程
【参考代码】
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy_head = ListNode(0, head) #在头head 前增加一个虚拟的头结点
p = dummy_head
while p.next and p.next.next:
79
a = p.next #a 表示目前正在交换的结点对中的第一个结点
b = p.next.next #b 表示目前正在交换的结点对中的第二个结点
a.next = b.next #第一个结点先抓住第二个结点的后继
b.next = a #然后第二个结点抓住第一个结点
p.next = b #与前面连上
p = a #准备处理下一对结点
return dummy_head.next
例3.6 (力扣19)删除链表的倒数第N 个结点。
图3.22 删除倒数第2个结点示例
【题目描述】
删除链表的倒数第n 个结点,并且返回链表
的头结点。链表长度范围为[1,30],0≤Node.
val≤100。
例如,图3.22显示了在一个单链表中删除n
为2的结点(即倒数第2个结点)前、后的形态。
【解题思路】
本题的核心问题是找到链表倒数第n 个结点的前驱结点,一种容易想到的方法是,首
先从头结点开始对链表进行一次遍历,得到链表的长度L,随后再从头结点开始对链表进行
一次遍历,当遍历到第L-n+1个结点时,它就是需要删除的结点。
若想提高效率,也可以在不预先求出链表的长度的情形下通过一趟扫描解决本题,可以
采用“快慢指针”的方法,用两个指针fast和slow同时对链表进行遍历,并且fast比slow超
前n 个结点,当fast遍历到链表的末尾时,slow 就恰好处于倒数第n 个结点。而对于删除
结点操作,关键是要找到待删除结点的前驱(即倒数第n+1个结点),因此应设法让fast比
slow超前n+1个结点。同时,为了避免对“要删除的结点恰好是表头结点head”这种特殊
情况进行单独处理,可以先设置一个虚拟的头结点,指向该结点的指针为dummy_head。快
指针从head出发,走n 步,接着让慢指针从dummy_head出发,这样,快指针比慢指针领先
n+1个结点。再令快慢指针一起同步移动,当快指针走到链表的末尾(即指向None)时,慢
指针指向的就是倒数第n 个结点的前驱结点,如图3.23所示。
图3.23 快慢指针法定位待删除结点前驱
80
【参考代码】
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy_head = ListNode(0, head)
fast, slow = head, dummy_head
for i in range(n):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy_head.next
3.4 链表的变形与操作
观察3.3节介绍的单链表结构的线性表发现,由于有表头变量直接标记着头结点,所以
在表头进行加入和删除等操作的时间复杂度均为O(1),但是,想要在单链表的尾端加入或
删除元素效率却很低,因为需要先从头开始以顺链逐个结点遍历的方式来定位尾结点或其
前驱,然后才能链接新结点或删除尾结点。在实际应用中,如果经常需要在表的两端进行一
些变动操作,则可以通过一些链表的变形来提高操作的效率。
3.4.1 带尾结点引用的单链表
希望能够快速地定位到表尾,最直观的处理方式是可以直接给表对象增加一个对表尾
结点的引用,这样在尾端加入元素,也能做到O(1)的复杂度,如图3.24所示。
图3.24 带有尾结点引用的单链表
定义带有首尾结点的单链表,可以通过继承3.3节中定义的单链表并在初始化操作中
增加一个尾结点的设置来实现,也可以直接重新定义一个新的单链表类LList1,并在初始
化操作中分别设置首尾结点即可,具体定义方法如下。
class LList1:
def _ _init_ _(self):
self._head = None
self._rear = None
链表的这一新的设计与之前单链表的结构近似,这种结构变化对非变动操作影响不大,
一般只影响到表的变动操作,以下重点讨论带尾结点引用的单链表的首端和尾端的插入、删
除操作的实现算法。
首端插入:在链表非空时,前端插入不影响_rear,但在表为空表时,要考虑给_rear赋
值,如图3.25所示。
81
图3.25 带有尾结点引用的单链表的首端插入
该首端插入元素操作时间复杂度为O(1),完整代码如下。
def prepend(self, val):
if self._head is None:
self._head = ListNode(val)
self._rear = self._head
else:
self._head = ListNode(val, self._head)
尾端插入:在链表非空时,将尾结点的后继指向新结点,并更新_rear指向新的尾结点,
如图3.26所示。但在表为空表时,仍然要考虑给_rear赋值,应使用和前端插入一样的
操作。
图3.26 带有尾结点引用的单链表的尾端插入
该尾端插入元素操作时间复杂度也为O(1),完整代码如下。
def append(self, val):
if self._head is None:
self._head = ListNode(val)
self._rear = self._head
else:
self._rear.next = ListNode(val)
self._rear = self._rear.next
首端删除:假定链表非空,首端删除很简单,只需取出表头元素,并重置表头指针即可,
如图3.27所示。
图3.27 带有尾结点引用的单链表的首端删除
82
该首端删除元素操作时间复杂度为O(1),完整代码如下。
def pop(self):
e = self._head.val
self._head = self._head.next
return e
尾端删除:假定链表非空,尾端删除相对比较复杂,需要先记录下表尾结点的元素值,
还需要找到倒数第二个结点,也就是表尾结点的直接前驱,并将它设为新的表尾,这种处理
需要表中至少有两个结点。当表中只有一个结点时,删除结点就相当于把表变为空表,而判
断是否为空表只需要看表头变量的值是否为None,所以此时将_head置为None即可;而当
原表不止一个结点的时候,就需要寻找表尾的前驱。依旧只能从表头开始,一个个结点进行
检查,直至某个结点的后继是_rear为止,如图3.28所示。
图3.28 带有尾结点引用的单链表的尾端删除
该尾端删除元素的操作由于要从头遍历查找表尾的前驱,因此时间复杂度为O(n),完
整代码如下。
def pop_last(self):
e = self._rear.val
if self._head.next is None: #表中只有一个结点
self._head = None
else:
p = self._head
while p.next is not self._rear:
p = p.next
self._rear = p
return e
3.4.2 循环单链表
单链表还有一种常见的变形设计也能够实现表头、表尾的快速定位,即循环单链表,简
称循环链表,只需要将原来单链表中表尾结点的next域由None改为指向表的第一个结点
即可,如图3.29所示。
图3.29 标识头结点的循环单链表