Python双链表原理与实现方法详解
作者:授我以驴 时间:2023-10-10 20:55:40
本文实例讲述了Python双链表原理与实现方法。分享给大家供大家参考,具体如下:
Python实现双链表
文章目录
Python实现双链表
定义链表节点
初始化双链表
判断链表是否为空
双链表尾部添加元素
双链表头部添加节点:
双链表表头删除
双链表按位置插入
双链表删除指定节点
完整代码
单链表与双链表比较
双链表的实现
单链表与双链表比较
双链表比单链表多一个前驱指针位置,空间效率不占优势
由于双链表中的节点既可以向前也可以向后,相比单链表在查找方面效率更高(可使用二分法)
双链表的实现
定义链表节点
class Node(object): def __init__(self, value=None, prev=None, next=None): self.value = value# 节点数据域 self.prev = prev# 节点前驱指针 self.next = next# 节点后继指针
初始化双链表
在双链表类的构造方法中定义头指针以及链表长度属性
class doubleLinked(object): def __init__(self): self.head = Node()# 头指针节点,用于确定链表第一个节点,不计入链表实际长度 self.length = 0
判断链表是否为空
通过实例属性self.length是否为0判断链表是否为空
# 判断链表是否为空 def is_Empty(self): return self.length == 0
双链表尾部添加元素
根据传入的value值创建node节点对象
判断是否为空,若为空则插入节点的前驱节点为head头指针节点,head头指针指向node
如果链表非空:
通过while循环判断当前节点的后继节点是否为None,找到尾节点
找到尾节点后,将尾节点指向待添加节点,待添加节点前驱节点域指向原伪节点
长度+1
# 尾部添加 def append(self, value): node = Node(value) if self.length == 0: node.prev = self.head self.head.next = node else: curnode = self.head.next while curnode.next != None: curnode = curnode.next curnode.next = node node.prev = curnode self.length += 1
双链表头部添加节点:
调用类方法is_Empty()判断是否为空,若为空则直接调用append()方法
当链表非空时
首先创建待添加节点对象node
设置中间变量存放原头指针指向的节点
将头指针重新指向待添加节点
新添加节点后驱指针域指向中间变量(即原第一个节点)
中间变量前驱指针域指向新添加节点
链表长度+1
# 头部添加 def add(self, value): if self.is_Empty(): self.append(value) node = Node(value) curnode = self.head.next self.head.next = node node.next = curnode curnode.prev = node self.length += 1
双链表表头删除
老样子,依旧要先判断原链表是否为空,为空的时候返回False
链表不为空时:
将头指针指向的节点存放到中间变量curnode
将头指针指向的节点指向头指针(也就是第一个节点现在变成了头指针)
新头指针指向中间变量的后驱节点
链表长度-1
# 删除表头节点 def remove(self): if self.is_Empty(): return False curnode = self.head.next self.head = self.head.next self.head.next = curnode.next self.length -= 1
双链表按位置插入
接收两个位置参数,postion和value
创建待插入节点对象
变量curnode存放当前节点,变量i初始值为2(位置参数<2时,默认插入到第二个位置,>2时,通过while循环找到指定位置节点再进行插入)
找到指定位置后,待插入节点的后驱指针指向当前节点curnode的后继节点,待插入节点的前驱节点为当前节点。
当前节点的原后驱节点的前驱指针域指向待插入节点,当前节点curnode的后驱节点变更为插入节点
链表长度+1
# 插入到指定位置 def insert(self, postion, value): node = Node(value) curnode = self.head.next i = 2 while i < postion: i += 1 curnode = curnode.next node.next = curnode.next node.prev = curnode curnode.next.prev = node curnode.next = node self.length += 1
双链表删除指定节点
依旧需要判断是否为空,为空时返回False
链表不为空时:
设置中间变量curnode存放当前节点
while循环找到相匹配的值的节点
找到相应节点后,应删除节点的前驱节点的后继节点更改为应删除节点的后继节点;应删除节点的后继节点的前驱更改为应删除节点的前驱;
应删除节点后继指针指向自己
链表长度-1
# 删除指定节点 def delete(self, value): if self.is_Empty(): return False curnode = self.head.next while curnode.value != value: curnode = curnode.next curnode.prev.next = curnode.next curnode.next.prev = curnode.prev curnode.next = curnode self.length -= 1
完整代码
class Node(object):
def __init__(self, value=None, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next
class doubleLinked(object):
def __init__(self):
self.head = Node()
self.length = 0
def __iter__(self):
for node in self.iter_node():
yield node.value
# 对链表进行可迭代操作
def iter_node(self):
curnode = self.head.next
while curnode.next != None:
yield curnode
curnode = curnode.next
if curnode.next == None:
yield curnode
# 判断链表是否为空
def is_Empty(self):
return self.length == 0
# 尾部添加
def append(self, value):
node = Node(value)
if self.length == 0:
node.prev = self.head
self.head.next = node
else:
curnode = self.head.next
while curnode.next != None:
curnode = curnode.next
curnode.next = node
node.prev = curnode
self.length += 1
# 头部添加
def add(self, value):
if self.is_Empty():
self.append(value)
node = Node(value)
curnode = self.head.next
self.head.next = node
node.next = curnode
curnode.prev = node
self.length += 1
# 插入到指定位置
def insert(self, postion, value):
node = Node(value)
curnode = self.head.next
i = 2
while i < postion:
i += 1
curnode = curnode.next
node.next = curnode.next
node.prev = curnode
curnode.next.prev = node
curnode.next = node
self.length += 1
# 删除表头节点
def remove(self):
if self.is_Empty():
return False
curnode = self.head.next
self.head = self.head.next
self.head.next = curnode.next
self.length -= 1
# 删除指定节点
def delete(self, value):
if self.is_Empty():
return False
curnode = self.head.next
while curnode.value != value:
curnode = curnode.next
curnode.prev.next = curnode.next
curnode.next.prev = curnode.prev
curnode.next = curnode
self.length -= 1
# 测试
linkedlist = doubleLinked()
print(linkedlist.is_Empty())
linkedlist.append(1)
linkedlist.append(3)
linkedlist.append(5)
linkedlist.add(4)
linkedlist.add(2)
linkedlist.insert(3,10)
linkedlist.remove()
linkedlist.delete(3)
# 遍历打印
i = 1
for node in linkedlist:
print("第%d个链表节点的值: %d"%(i, node))
i += 1
运行结果:
True
第1个链表节点的值: 4
第2个链表节点的值: 10
第3个链表节点的值: 1
第4个链表节点的值: 5
希望本文所述对大家Python程序设计有所帮助。
来源:https://blog.csdn.net/one_Salted_FishGG/article/details/99876268
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
SQL Server中使用判断语句(IF ELSE/CASE WHEN )案例
ubuntu定时执行python脚本实例代码
Python matplotlib实现折线图的绘制
![](https://img.aspxhome.com/file/2023/1/93621_0s.png)
python实现视频读取和转化图片
关于Dreamweaver乱码问题的解决方案
Python实现有趣的亲戚关系计算器
![](https://img.aspxhome.com/file/2023/9/130559_0s.png)
python如何正确的操作字符串
Mootools 1.2教程(9)——输入过滤第二部分(字符串)
vue+elementUI实现动态面包屑
MySQL-MMM安装指南(Multi-Master Replication Manager for MySQL)
![](https://img.aspxhome.com/file/2023/3/97433_0s.jpg)
php过滤器使用详解
js实现向右横向滑出的二级菜单效果
![](https://img.aspxhome.com/file/2023/9/136229_0s.jpg)
PyInstaller如何打包依赖文件至目标程序目录
![](https://img.aspxhome.com/file/2023/7/130817_0s.jpg)
技巧/诀窍:在ASP.NET中重写URL
![](https://img.aspxhome.com/file/UploadPic/20079/23/2007923122811285s.jpg)
Pycharm快捷键配置详细整理
![](https://img.aspxhome.com/file/2023/5/110375_0s.png)
详解JS如何判断对象上是否存在某个属性
electron-vue 项目添加启动loading动画的实现思路
![](https://img.aspxhome.com/file/2023/0/139810_0s.jpg)
python实现一次创建多级目录的方法
GO 反射对性能的影响分析
详解LyScript 内存扫描与查壳实现
![](https://img.aspxhome.com/file/2023/4/103324_0s.png)