在顺序存储模式下，可以根据数据元素的序号随机访问表中的任意元素，但同时在插入和删除操作中需要移动大量元素，导致算法效率低下。解决这个问题的一个方法是对线性表使用链式存储。本文将介绍链式存储结构的特点以及各种基本操作的实现。需要什么可以参考。
:
目录
0.学习目标1。线性表的链式存储结构1.1指针相关概念1.2指针结构1.3节点1.4节点类2。单链表的实现2.1单链表的初始化2.2获取单链表的长度2.3读取指定位置元素2.4查找指定元素2.5在指定位置插入新元素2.6删除指定位置元素2.7其他有用的操作3 .单链表的应用3.1单链表的应用示例3.2使用
0. 学习目标
在顺序存储模式下，可以根据数据元素的序号随机访问表中的任意元素，但同时在插入和删除操作中需要移动大量元素，导致算法效率低下。解决这个问题的一个方法是对线性表使用链式存储。在链表存储模式下，逻辑相邻的数据元素在存储空间中不一定相邻，数据元素的逻辑顺序是通过链表中的指针链接来实现的。本节将介绍链式存储结构的特点和各种基本操作的实现。
通过本节，您应掌握以下内容：
线性表的链式存储及实现方法
链表基本操作的实现
利用链表的基本操作实现复杂算法
1. 线性表的链式存储结构
链式存储结构用于存储线性表中元素的存储单元可以是连续的，也可以分散在内存中。因为线性表中的元素之间存在线性关系，为了表示元素之间的线性关系，链式存储结构不仅要存储线性表中的元素，还要存储表示元素之间逻辑关系的信息。因此，当线性表中的一个元素用链式存储结构表示时，至少需要两条信息。除了存储每个数据元素的值之外，还需要存储其后继元素或前趋元素所在的存储器的地址。链式存储结构表示的线性表简称为链表。
1.1 指针相关概念
在继续讲解之前，我们先了解一下指针的相关概念，以便更好的理解链表。假设我们需要处理一个大的数据文件，这个文件已经被读取并保存在内存中。当我们在函数之间传递文件时，我们并不直接传递整个文件。我们需要创建变量来保存文件在内存中的位置。这些变量很小，很容易在不同的函数之间转换。
使用指针的一个好处是，你可以用一个简单的内存地址指向一个更大的内存地址段。硬件中支持指针，称为间接寻址。
与C语言等等不同，在Python中，我们不需要直接操作指针，但这并不意味着Python中不使用指针。比如赋值语句l=list([1，2，3])，我们通常说L是列表类型的变量，或者直接说L是列表，但这是不准确的。变量L是对列表的引用(指针)。list构造函数在内存中创建一个列表，并返回列表开始的内存位置，这就是l中存储的内容，Python隐藏了这种复杂性。
1.2 指针结构
每个指针结构包含一个或多个到结构中其他元素的链接。这些链接的类型取决于我们创建的数据类型。例如，在一个链表中，我们将链接到结构中的下一个或上一个元素。
指针结构具有以下优点：
可以快速添加或删除节点，不需要连续的顺序存储空间，在一个恒定的时间内扩展结构空间。
然而，指针的这种灵活性是有代价的，即需要额外的空间来存储地址。例如，如果有一个整数线性表，我们不仅需要在每个节点中存储一个整数数据，还需要额外的空间来存储指向下一个节点的指针。
1.3 结点
节点是一个数据容器和一个或多个到其他节点的链接，而链接是一个指针。简单节点只有到下一个节点的链接。如果我们有一个包含水果列表的链表，我们知道字符串实际上并没有存储在节点中，但是有一个指向实际字符串的指针，如下图所示，它包含两个节点。第一个节点有一个指向存储在内存中的字符串(apple)的指针和一个指向下一个节点地址的指针。因此，这个简单节点的存储需求是两个内存地址，包括数据字段和指针字段：
我们需要考虑的另一个问题是最后一个节点的指针字段。我们需要确保每个节点的指针字段都指向一个确定的值。如果我们希望显式地让最后一个节点的指针字段不指向任何东西，那么在Python中，我们需要使用特殊值None来表示什么都没有。如下图所示，链表最后一个节点的指针字段指向无：
1.4 结点类
接下来，我们将实现上面的节点结构：
类节点：
def __init__(self，data=None):
self.data=数据
self.next=无
Next指针初始化为None，意味着默认节点是端点，除非改变Next的值，这样可以保证链表的正确终止。我们还可以根据需要在节点类中添加其他内容。例如，我们可以创建一个水果类来存储不同水果的价格信息等数据，并使用数据字段链接到水果类的实例。
为了能够打印节点信息，我们需要重载__str__方法：
def __str__(self):
返回字符串(self.data)
2. 单链表的实现
通常，“链表”指的是单个链表。单个链表由许多节点组成，每个节点只有一个指向直接后继节点的next指针。链表中最后一个节点的链接为None，表示链表结束。数据元素只能从链表头到链表尾依次访问，不能反向访问。这是最简单的链表。其他链表类型(包括双向链表、循环链表等。)将在下面的部分中解释。
单链表分为前导节点和非前导节点两种。因为链表中的第一个节点没有直接的前任，所以它的地址需要放在链表的头指针变量中；而其他节点的地址被放置在直接前趋节点的指针字段中。在链表中插入和删除节点时，第一个节点的处理方式与其他节点不同。因此，为了操作方便，在链表的头部增加了一个“头节点”，第一个数据节点的地址存储在它的指针字段中，头节点的地址存储在头指针变量中。下图(a)是一个没有前导节点的链表，其头指针linked_list指向第一个数据节点，而图(b)是一个没有前导节点的链表的头指针linked_list指向头节点，头节点的指针字段指向第一个数据节点：
注：在下面的单链表基本操作中，除非特别说明，否则采用带头节点的链表。
2.1 单链表的初始化
单链表表的初始化建立一个带有前导节点的空单链表，其长度初始化为0。此时链表中没有元素节点，只有一个前导节点，其指针字段为空：
类SinglyLinkedList:
def __init__(self):
self.length=0
#初始化头节点
头节点=节点()
#头指针指向头节点
self.head=头节点
创建SinglyLinkedList对象的时间复杂度为O(1)。
2.2 获取单链表长度
由于我们使用length来跟踪链表中的项数，所以只需要重载__len__就可以从对象返回length的值，所以时间复杂度为O(1):
def __len__(self):
返回自身长度
2.3 读取指定位置元素
为了读取链表中指定位置的元素，我们将重载__getitem__操作。我们已经知道，单链表中的节点只能顺序访问，即先访问上一个节点，再访问下一个节点。因此，为了访问单个链表中第I个元素的值，必须从开始指针开始遍历链表，依次访问每个节点，直到到达第I个节点。因此，运算的复杂度为O(n)。同时，我们要确保索引在可接受的索引范围内，否则会抛出IndexError异常：
def __getitem__(self，index):
如果index self.length - 1或index 0:
引发IndexError(“SinglyLinkedList赋值索引超出范围”)
否则：
计数=-1
当前=自身. head
计数索引时：
当前=当前。下一个
计数=1
返回当前数据
我们也可以实现在指定位置修改元素的操作，只需要重载__setitem__操作，其复杂度也是O(n):
def __setitem__(self，index，value):
如果index self.length - 1或index 0:
引发IndexError(“SinglyLinkedList赋值索引超出范围”)
否则：
计数=-1
当前=自身. head
计数索引时：
当前=当前。下一个
计数=1
current.data=值
2.4 查找指定元素
当搜索一个指定的元素时，需要设置一个指针current来跟踪链表的节点。最初，current指向链表中的第一个数据节点，然后沿着下一个字段依次指向每个节点。指向每个节点以确定其值是否等于指定值，如果是，则返回节点索引。否则，以后继续搜索。如果链表中没有这样的元素，则会抛出ValueError异常，其时间复杂度为O(n):
定义定位(自身，值):
计数=-1
当前=自身. head
当电流！=None和current.data！=值：
计数=1
当前=当前。下一个
如果当前和当前数据==值：
返回计数
否则：
引发value error({ }不在顺序列表中)。格式(值))
2.5 在指定位置插入新元素
单个链表节点的插入只需要修改节点指针字段的值来指向新的链接位置，而不需要移动任何元素。比如我们要在索引为IIII的链表中插入一个新的节点，首先要找到插入位置的前一个节点I1i-1I1，然后插入。设前一个指针指向待插入位置的前一个节点，当前指针指向插入前链表中索引为IIII的节点，也是待插入位置的后一个节点，new_node指针指向待插入的新节点。插入过程如下：
用Python实现的算法如下：
定义插入(自身，索引，数据):
计数=-1
当前=自身. head
#判断插入位置的合法性
如果索引自身长度或索引为0:
引发IndexError(“SinglyLinkedList赋值索引超出范围”)
否则：
节点=节点(数据)
计数索引时：
#找到插入位置
先前=当前
当前=当前。下一个
计数=1
#插入新节点
node.next=previous.next
previous.next=node
self.length=1
也可以用上面的思路直接在链表中插入节点：
def insert_node(自身，索引，节点):
计数=-1
当前=自身. head
如果索引自身长度或索引为0:
引发IndexError(“SinglyLinkedList赋值索引超出范围”)
否则：
计数索引时：
先前=当前
当前=当前。下一个
计数=1
node.next=previous.next
previous.next=node
self.length=1
2.6 删除指定位置元素
要删除链表中的IIII节点，首先在单链表中找到前一个节点，指针current指向要删除的节点，将previous的指针字段修改为要删除的节点的后继节点的地址，被删除的节点需要动态释放。下图(b)中的粉色虚线表示删除节点电流后的指针指向：
用Python实现的算法如下：
def __delitem__(self，index):
如果index self.length - 1或index 0:
引发IndexError(“SinglyLinkedList赋值索引超出范围”)
否则：
计数=-1
上一个=自己. head
当计数索引- 1时：
previous=previous.next
计数=1
current=previous.next
previous.next=current.next
自身长度-=1
德尔电流
在插入和删除操作中，先确定操作位置，再进行插入和删除操作，所以时间复杂度为O(n)。由于算法不移动元素的位置，只是在插入和删除时修改指针链接，所以使用链表存储进行插入和删除比顺序存储效率更高。
2.7 其它一些有用的操作
2.7.1链表元素的输出操作
将单个链接列表转换为用于打印的字符串，并使用str函数调用对象上的__str__方法来创建适合打印的字符串表示形式：
def __str__(self):
s='['
当前=自身.头部.下一个
计数=0
当电流！=无：
计数=1
s=str(当前)
当前=当前。下一个
如果算上自身长度：
s=' -'
s=']'
返回s
2.7.2删除指定元素。
这与删除指定位置的元素略有不同。删除指定元素需要删除链表中与给定值数据元素相同的第一个节点，其时间复杂度也是O(n):
def del_value(自身，值):
当前=自身. head
上一个=自己. head
当电流！=无：
如果当前数据==值：
previous.next=current.next
自身长度-=1
德尔电流
返回
否则：
先前=当前
当前=当前。下一个
raise ValueError('提供的值不存在！')
2.7.3在链表的末尾添加新元素。
为了方便地在链表的末尾添加新元素，可以实现append函数：
定义附加(自身，值):
节点=节点(值)
当前=自身. head
虽然current.next不是None:
当前=当前。下一个
current.next=节点
self.length=1
该算法的时间复杂度为O(n)。如果需要频繁向链表末尾添加新元素，可以使用尾指针tail跟踪链表的最后一个元素，通过尾指针向链表末尾添加新元素的时间复杂度可以降低到O(1)。
3. 单链表应用
接下来我们先测试上面实现的链表，验证操作的有效性，然后用实现的基本操作实现更复杂的算法。
3.1 单链表应用示例
首先，初始化一个链表sllist，并向它追加几个元素：
sllist=SinglyLinkedList()
#在链接列表的末尾追加元素
sllist.append('苹果')
sllist.append('柠檬')
#在指定位置插入元素
sllist.insert(0，'香蕉')
sllist.insert(2，'橙色')
我们可以直接打印链表中的数据元素，链表的长度等信息：
打印('链接列表是：'，sllist)
Print('链表长度为：'，len(sllist))
Print('链表的第0个元素是：'，sllist[0])
#修改数据元素
sllist[0]='pear '
打印('修改链接列表数据后：'，sllist)
上面的代码输出如下：
链表是：[香蕉-苹果-橘子-柠檬]
链表长度：4
链表的第0个元素是香蕉。
修改链表数据后：【梨-苹果-橘子-柠檬】
接下来，我们将演示如何在指定位置添加/删除元素以及如何找到指定的元素等。
#在指定位置添加/删除节点
sllist.insert(1，'葡萄')
Print('在位置1添加葡萄后的链表数据：'，sllist)
del(sllist[2])
打印('修改链接列表数据后：'，sllist)
#删除指定的元素
sllist.del_value('pear ')
打印('删除pear后的链表数据：'，sllist)
sllist.append('西瓜')
打印('添加西瓜后的链表数据：'，sllist)
上面的代码输出如下：
在位置1添加葡萄以链接列表数据：[梨-葡萄-苹果-橙-柠檬]
修改链表数据后：【梨-葡萄-橙-柠檬】
删除梨后的链表数据：[葡萄-橘子-柠檬]
西瓜后添加链表数据：[葡萄-橙子-柠檬-西瓜]
3.2 利用单链表基本操作实现复杂操作
[1]利用基本运算函数对单个链表进行倒排，如下图(A)倒排链表和图(B)倒排链表，要求算法的空间复杂度为O(1):
为了保证算法的空间复杂度为O(1)，我们只能修改原节点的指针，将指针current设置为指向head-next，并使head.next=None，然后用当前指针依次遍历每个节点，并插入到head之后。该算法只需要扫描一次链表就可以完成求逆，因此时间复杂度为O(n)。该算法实现如下：
def反向链表(sllist):
head_node=sllist.head
if head_node.next:
当前=head_node.next
head_node.next=无
sllist.length=0
当前时间：
先前=当前
当前=当前。下一个
sllist.insert_node(0，上一个)
返回列表
#算法测试
sllist=SinglyLinkedList()
对于范围(5)中的I:
sllist.append(i)
打印('反转前：'，sllist)
Print('反转后：'，reverse_linked_list(sllist))
算法输出如下：
反向位置：[0-1-2-3-4]
后退：[4-3-2-1-0]
算法执行流程如下：
[2]删除单链表中的重复节点，如下图所示：(a)删除前，(b)删除后。
用previous指针指向第一个数据节点，用另一个指针curent指向previous的直接后继开始遍历整个链表，遇到相同数据元素的节点就删除；然后previous指向下一个节点，重复删除过程；直到previous指向最后一个节点，算法才结束：
定义删除相同节点(sllist):
previous=sllist.head.next
如果不是以前的：
返回
虽然以前：
当前=先前
当前。下一个：
如果current . next . data==previous . data:
相同=当前。下一个
current.next=current.next.next
sllist.length -=1
德尔相同
否则：
当前=当前。下一个
previous=previous.next
返回列表
#算法测试
sllist=SinglyLinkedList()
打印('删除重复节点之前：'，sllist)
sllist.append(10)
sllist.append(11)
sllist.append(10)
sllist.append(10)
sllist.append(11)
Print('删除重复节点后'，delete_same_node(sllist))
算法的时间复杂度为O(n2)，程序输出如下：
删除重复节点之前：[10-11-10-10-11]
删除重复节点后：[10-11]
算法执行流程如下：
以上是Python数据结构链表的详细讲解。更多关于Python链表的信息，请关注我们的其他相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。