成品网站 子目录打不开,php网站安装图解,网站上传的流程图,微信小程序万能开挂器一、链表 链表是一种线性数据结构#xff0c;由一系列按特定顺序排列的节点组成#xff0c;这些节点通过指针相互连接。每个节点包含两部分#xff1a;元素和指向下一个节点的指针。其中#xff0c;最简单的形式是单向链表#xff0c;每个节点含有一个信息域和一个指针域由一系列按特定顺序排列的节点组成这些节点通过指针相互连接。每个节点包含两部分元素和指向下一个节点的指针。其中最简单的形式是单向链表每个节点含有一个信息域和一个指针域该指针指向链表中的下一个节点最后一个节点则指向一个空值。
1.1、Python中的链表
• 大部分都是用C语言实现链表因为C有指针可以很方便的控制内存很轻易就可以实现链 表在C/C中通常采用“指针结构体”来实现链表。
• Python是一门动态语言可以直接把对象赋值给新的变量我们采用“引用类”来实现 链表。
• 结构data为自定义的数据next为下一个节点的地址。
• 链表的种类单向链表、双向链表、单向循环链表、双向循环链表。
1.2、基本元素
节点每个节点有两个部分左边称为值域存放用户数据右边部分称为指针域用来存 放指向下一个元素的指针。
Headhead节点永远指向第一个节点。
Tailtail节点永远指向最后一个节点。
None链表中最后一个节点的指针域为None。
二、基本操作 2.1、节点的创建
class Node:def __init__(self, data):# 初始化节点包含数据和指向下一个节点的指针self.data dataself.next None 2.2、初始化单向链表
class LinkList:def __init__(self, nodeNone):# 初始化链表头指针指向第一个节点默认为Noneself.__head node
2.3、判断是否为空 def is_empty(self):# 检查链表是否为空return self.__head None
2.4、链表长度 def length(self):# 计算链表的长度current self.__headcount 0while current ! None:count 1current current.nextreturn count
2.5、遍历链表 def travel(self):# 遍历链表并打印每个节点的数据current self.__headwhile current ! None:print(current.data)current current.next
2.4、插入节点
2.4.1、头节点 def add(self, data):# 在链表头部添加新节点new_node Node(data)new_node.next self.__headself.__head new_node 2.4.2、中间节点 def insert(self, pos, data):# 在指定位置插入新节点if pos self.length() - 1:self.append(data) # 如果位置超出范围添加到尾部elif pos 0:self.add(data) # 如果位置小于等于0添加到头部else:new_node Node(data)pre self.__headcount 0while count pos - 1:count 1pre pre.nextnew_node.next pre.next # 将新节点的next指向当前节点的nextpre.next new_node # 将前一个节点的next指向新节点 2.4.3、尾节点 def append(self, data):# 在链表尾部添加新节点new_node Node(data)if self.is_empty():self.__head new_nodeelse:current self.__headwhile current.next ! None:current current.nextcurrent.next new_node 2.5、删除节点 def remove(self, data):# 移除链表中指定数据的节点current self.__headpre Nonewhile current ! None:if current.data data:if current self.__head:self.__head current.next # 如果是头节点更新头指针else:pre.next current.next # 将前一个节点的next指向当前节点的nextbreakelse:pre currentcurrent current.next 2.6、查找节点 def serch(self, data):# 查找链表中是否存在指定数据current self.__headwhile current ! None:if current.data data:return True # 找到数据返回Trueelse:current current.nextreturn False # 遍历完成未找到数据返回False
三、链表的特点
1、动态数据集合链表允许动态的添加和删除元素这使得它们在处理未知数量或频繁变 化的数据集时非常有用。
2、元素顺序链表可以按照插入顺序来保持元素的顺序这对于需要维护元素插入顺序的 应用程序非常有用。
3、 内存效率与数组相比链表在内存使用上更为高效因为它们不需要连续的内存空间。 链表通过节点之间的指针来连接元素这样可以更有效地利用内存空间。
4、避免数组扩容数组在初始化时需要指定大小如果超出大小则需要扩容这是一个 昂贵的操作。链表则可以避免这个问题因为它们可以动态地增长。
四、单向链表的缺点
1、只能从头遍历到尾或者从尾遍历到头(一般从头到尾)。
2、链表相连的过程是单向的。实现的原理是上一个链表中有一个指向下一个的引用。
3、 我们可以轻松的到达下一个节点, 但是回到前一个节点是很难的。但是, 在实际开发中, 经 常会遇到需要回到上一个节点的情况。 举个例子: 假设一个文本编辑用链表来存储文本。每一行用一个String对象存储在链表的 一个节点中。当编辑器用户向下移动光标时, 链表直接操作到下一个节点即可。但是当用 于将光标向上移动呢? 这个时候为了回到上一个节点, 我们可能需要从头开始, 依次走到 想要的节点上。 五、完整代码
class Node:def __init__(self, data):# 初始化节点包含数据和指向下一个节点的指针self.data dataself.next Noneclass LinkList:def __init__(self, nodeNone):# 初始化链表头指针指向第一个节点默认为Noneself.__head nodedef is_empty(self):# 检查链表是否为空return self.__head Nonedef length(self):# 计算链表的长度current self.__headcount 0while current ! None:count 1current current.nextreturn countdef travel(self):# 遍历链表并打印每个节点的数据current self.__headwhile current ! None:print(current.data)current current.nextdef add(self, data):# 在链表头部添加新节点new_node Node(data)new_node.next self.__headself.__head new_nodedef append(self, data):# 在链表尾部添加新节点new_node Node(data)if self.is_empty():self.__head new_nodeelse:current self.__headwhile current.next ! None:current current.nextcurrent.next new_nodedef insert(self, pos, data):# 在指定位置插入新节点if pos self.length() - 1:self.append(data) # 如果位置超出范围添加到尾部elif pos 0:self.add(data) # 如果位置小于等于0添加到头部else:new_node Node(data)pre self.__headcount 0while count pos - 1:count 1pre pre.nextnew_node.next pre.next # 将新节点的next指向当前节点的nextpre.next new_node # 将前一个节点的next指向新节点def remove(self, data):# 移除链表中指定数据的节点current self.__headpre Nonewhile current ! None:if current.data data:if current self.__head:self.__head current.next # 如果是头节点更新头指针else:pre.next current.next # 将前一个节点的next指向当前节点的nextbreakelse:pre currentcurrent current.nextdef serch(self, data):# 查找链表中是否存在指定数据current self.__headwhile current ! None:if current.data data:return True # 找到数据返回Trueelse:current current.nextreturn False # 遍历完成未找到数据返回Falseif __name__ __main__:linklist LinkList()linklist.add(10) # 添加节点10linklist.add(20) # 添加节点20linklist.append(100) # 在尾部添加节点100linklist.add(30) # 添加节点30linklist.add(40) # 添加节点40print(linklist.is_empty()) # 检查链表是否为空print(linklist.length()) # 输出链表长度print(*****************)linklist.remove(30) # 移除节点30# linklist.travel() # 遍历链表并打印节点数据print(linklist.serch(40)) # 查找节点40是否存在# linklist.travel() # 遍历链表并打印节点数据
六、思维导图
