python双向循环链表实例详解
作者:python-行者 时间:2023-08-04 04:53:06
使用python实现双向循环链表,供大家参考,具体内容如下
双向循环链表: 将所有的数据存放到节点中,每一个节点相连接,首尾链接,
每一个节点中有一个数据存储区,和两个链接区,一个链接前一个节点,一个链接下一个节点
双向链表操作
1、链表是否为空
2、链表的长度
3、遍历链表
4、链表头部添加元素
5、链表尾部添加元素
6、链表指定位置添加元素
7、链表删除节点
8、查找节点是否存在
代码实现
# Functions 函数声明
class Node():
"""实例化节点类"""
def __init__(self, item):
self.item = item
self.prev = None
self.next = None
class Linklist():
"""
存放节点类
"""
def __init__(self):
self.head = None
# 1. 链表是否为空
def is_empty(self):
return self.head == None
# 2. 链表的长度
def length(self):
"""
返回链表中所有数据的个数
实例化游标,遍历链表,使用计数器自增一
空链表
"""
# 实例化游标
cur = self.head
# 判断是否为空
if self.is_empty():
return 0
else:
# 不为空
# 定义计数
count = 1
while cur.next != self.head:
count+=1
cur = cur.next
return count
pass
# 3. 遍历链表
def travel(self):
"""
遍历链表
实例化游标,遍历链表,每次输出节点的数据
空链表
只有头节点
"""
# 实例化游标
cur = self.head
# 判断是否为空
if self.is_empty():
return None
else:
# 不为空的情况
while cur.next != self.head:
print(cur.item, end=' ')
cur = cur.next
print(cur.item)
pass
# 4. 链表头部添加元素
def add(self, item):
"""
头节点添加
实例化节点,
"""
# 实例化节点
node = Node(item)
# 实例化游标
cur = self.head
# 判断是否为空
if self.is_empty():
node.next = node
node.prev = node
self.head = node
else:
# 链表不为空的情况
# 只有一个节点的情况
# node.next = self.head
node.next = cur
node.prev = cur
if cur.next == self.head:
# print(cur.item)
cur.prev = node
cur.next = node
self.head = node
elif cur.next != self.head:
pro = self.head
while cur.next != self.head:
cur = cur.next
pro.prev = node
cur.next = node
self.head = node
pass
# 5. 链表尾部添加元素
def append(self, item):
"""
链表尾部添加数据
实例化节点,实例化游标,指向尾部节点,修改指向
链表为空
"""
# 实例化节点
node = Node(item)
# 实例化游标
cur = self.head
if self.is_empty():
self.add(item)
else:
# 不为空的情况
# 指针指向最后一个节点
self.head.prev = node
node.next = self.head
while cur.next != self.head:
cur = cur.next
node.prev = cur
cur.next = node
pass
# 6. 链表指定位置添加元素
def insert(self, index, item):
"""
指定位置添加数据
实例化节点, 实例化游标
移动游标到索引位置,更改指向
输入索引大小判断
链表是否为空
"""
# 实例化节点
node = Node(item)
# 实例化游标
cur = self.head
if index <= 0:
self.add(item)
elif index > (self.length()-1):
self.append(item)
else:
# 中间添加数据
# 声明计数
count = 0
print(index)
while count < index-1:
count+=1
cur = cur.next
# print(cur.item)
node.next = cur.next
node.prev = cur
cur.next.prev = node
cur.next = node
pass
# 7. 链表删除节点
def remove(self, item):
"""
删除数据
实例化游标,遍历链表,查找有没有改数据
有,对改数据两侧的节点进行指向修改
"""
# 实例化游标
cur = self.head
# 判断是否为空
if self.is_empty():
return None
else:
# 不为空的情况下
# 如果删除的是头节点
if cur.item == item:
# 如果只有一个头节点
if cur.next == self.head:
self.head = None
else:
# self.head = cur.next
pro = cur.next
while cur.next != self.head:
cur = cur.next
cur.next = pro
pro.prev = cur
self.head = pro
pass
else:
while cur.next != self.head:
if cur.item == item:
# print(cur.item)
pro = cur.prev
nex = cur.next
pro.next = cur.next
nex.prev = pro
return True
else:
cur = cur.next
# 如果是最后一个节点
if cur.item == item:
cur.prev.next = self.head
self.head.prev = cur.prev
# 8. 查找节点是否存在
def search(self, item):
"""
查询指定的数据是否存在
实例化游标
遍历所有的节点。每个节点中判断数据是否相等,相等,返回True
"""
# 实例化游标
cur = self.head
# 判断是否为空
if self.is_empty():
return None
else:
# 不为空的情况
# 遍历所有的节点
while cur.next != self.head:
if cur.item == item:
return True
else:
cur = cur.next
if cur.item == item:
return True
pass
测试运行
# 程序的入口
if __name__ == "__main__":
a = Linklist()
a .add(400)
a .add(300)
a .add(200)
a .add(100)
a.append(10)
a.append(11)
a.add(1)
a.insert(30, 12) # 1 100 200 300 400 10 11 12
a.remove(1) # 100 200 300 400 10 11 12
a.remove(12) # 100 200 300 400 10 11
a.remove(400) # # 100 200 300 10 11
a.remove(4000)
print(a.search(100)) # True
print(a.search(11)) # True
print(a.search(111)) # None
print(a.is_empty()) # False
a.travel() # 100 200 300 10 11
print(a.length()) # 5
pass
来源:https://blog.csdn.net/Dhaihaihai/article/details/111304544
标签:python,链表
0
投稿
猜你喜欢
python OpenCV 图像通道数判断
2023-10-15 18:21:22
Python3读写Excel文件(使用xlrd,xlsxwriter,openpyxl3种方式读写实例与优劣)
2022-10-10 18:17:38
Oracle中字符串截取常用方法总结【推荐】
2024-01-26 16:55:02
mysql 8.0.12 解压版安装教程 个人亲测!
2024-01-28 10:22:05
Python中的MongoDB基本操作:连接、查询实例
2021-12-21 07:38:06
asp当中判断函数一览
2010-05-27 12:15:00
Pytorch 保存模型生成图片方式
2023-04-20 17:42:17
Python之维度dim的定义及其理解使用方式
2021-06-10 12:33:04
python 虚拟环境的创建与使用方法
2022-11-09 18:21:50
python实现弹窗祝福效果
2021-09-08 04:22:15
Keras多线程机制与flask多线程冲突的解决方案
2023-09-12 02:10:51
如何用CSS实现图像替换链接文本显示并保证链接可点击
2011-03-03 12:37:00
python机器学习基础K近邻算法详解KNN
2024-01-01 05:44:57
pyecharts如何实现显示数据为百分比的柱状图
2021-06-27 17:11:52
在keras里面实现计算f1-score的代码
2021-12-13 08:39:43
使用Filter实现信息的二次检索
2007-10-08 19:19:00
Python实现按照指定要求逆序输出一个数字的方法
2023-12-21 23:37:46
“生活”设计
2009-03-03 12:14:00
关于JS中变量的显式声明和隐式声明
2008-10-06 13:22:00
配置Git并从GitHub上克隆项目
2023-03-13 12:38:16