Python实现双向链表
作者:HBLQ_GK 发布时间:2022-06-12 17:41:34
标签:python,双向链表
之前写的单向链表和环形链表都只是单向的,只能单向遍历,不能根据后面的节点获取前面的节点,除非进行反转操作。
双向链表每个节点都有两个指针,这两个指针分别指向前后两个节点,这样就可以从任意一个节点从两个方向获取其他的所有节点,非常方便。但是由于每个节点有两个指针,所以双向链表比较消耗空间。
在设计双向链表时,通常会加上一个链表头指针,该链表头指针的数据字段不存放任何数据。
双向链表的可以是环形的,也可以不是环形的,如果是环形的话,那么最后一个节点的一个指针将指向链表头,链表头的一个指针将指向最后一个节点;如果不是环形的话,那么最后一个节点的一个指针和链表头的一个指针都将指向None。
我在这里实现的是一个环形的双向链表,这样我就可以从链表头开始,从两个方向中任意选择一个方向来进行操作。
我在这里主要实现了环形双向链表的:双向新增,双向遍历,双向插入,双向删除。
如图为双向环形链表示意图,每一个节点都被两个指针所指向,同时每个节点也指向了两个节点。
实现代码如下:
class Player:
"""节点类"""
def __init__(self):
"""初始化姓名,分数,指针"""
self.name = ''
self.score = 0
self.rlink = None
self.llink = None
def ergodic(head, num=None, is_print=False, left=False):
"""遍历函数,num是遍历到哪一个位置序号,is_print是否触发打印方法,left表示是否由head开始往左遍历"""
ptr = head
count = 0
while True:
if num == count:
break
if not left:
if ptr.rlink != head:
ptr = ptr.rlink
else:
break
else:
if ptr.llink != head:
ptr = ptr.llink
else:
break
count += 1
if is_print:
print('No.'+str(count), ptr.llink.name if ptr.llink != head else 'head', '<---',
ptr.name, ptr.score, '--->', ptr.rlink.name if ptr.rlink != head else 'head')
return ptr # 返回遍历完成后的最后一个节点
head = Player() # 初始化一个链表头指针,不用来存放任何数据
head.rlink = head # 初始化右指针
head.llink = head # 初始化左指针
while True:
select = input("(1).新增 (2).查看 (3).插入 (4).删除 (5).离开\n输入:")
if select == "1": # 新增节点,分为右新增和左新增
direction = input("(1).右新增 (2).左新增\n输入:")
if direction not in ("1", "2"):
print("输入错误")
continue
new_data = Player()
new_data.name = input("姓名:")
new_data.score = input("分数:")
if direction == "1": # 右新增
ptr = ergodic(head) # 从head开始向右遍历获取最后一个节点
ptr.rlink = new_data
new_data.llink = ptr
new_data.rlink = head
head.llink = new_data
else: # 左新增
ptr = ergodic(head, left=True) # 从head开始向左遍历获取最后一个节点
ptr.llink = new_data
new_data.rlink = ptr
new_data.llink = head
head.rlink = new_data
elif select == "2": # 遍历查看所有节点,分为右遍历和左遍历
direction = input("(1).右遍历 (2).左遍历\n输入:")
if direction == "1": # 右遍历
ergodic(head, is_print=True)
elif direction == "2": # 左遍历
ergodic(head, is_print=True, left=True)
else:
print("输入错误")
elif select == '3': # 插入节点,分为右插入和左插入
direction = input("(1).右插入 (2).左插入\n输入:")
if direction not in ("1", "2"):
print("输入错误")
continue
try:
num = int(input("请输入需要插入的节点位置序号:")) # 输入序号必须是大于0的正整数,如果输入大于最后一个节点的序号则插入到最后一个节点之后
if num < 1:
print("输入必须为大于0的正整数")
continue
except ValueError:
print("输入有误")
continue
insert_data = Player()
insert_data.name = input("姓名:")
insert_data.score = input("分数:")
if direction == "1": # 右插入
ptr = ergodic(head, num - 1) # 获取需要插入位置的前一个节点,新插入的节点就在这个节点的后面
insert_data.llink = ptr
insert_data.rlink = ptr.rlink
ptr.rlink = insert_data
insert_data.rlink.llink = insert_data
else: # 左插入
ptr = ergodic(head, num - 1, left=True)
insert_data.rlink = ptr
insert_data.llink = ptr.llink
ptr.llink = insert_data
insert_data.llink.rlink = insert_data
elif select == '4': # 删除节点,分为右删除和左删除
direction = input("(1).右删除 (2).左删除\n输入:")
if direction not in ("1", "2"):
print("输入错误")
continue
try:
num = int(input("请输入需要删除的节点位置序号:")) # 输入序号必须是大于0的正整数,如果输入大于最后一个节点的序号则删除最后一个节点
if num < 1:
print("输入必须为大于0的正整数")
continue
except ValueError:
print("输入有误")
continue
if direction == "1": # 右删除
ptr = ergodic(head, num) # 获取需要删除的节点
else: # 左删除
ptr = ergodic(head, num, left=True)
ptr.llink.rlink = ptr.rlink
ptr.rlink.llink = ptr.llink
elif select == '5':
print("成功离开")
break
else:
print("输入错误,请重试")
部分运行效果如下:
来源:https://blog.csdn.net/heibuliuqiu_gk/article/details/102687261
0
投稿
猜你喜欢
- 目录1. 警告不是异常2. 警告能捕获吗3. 捕获警告方法一4. 捕获警告方法二5. 捕获警告方法三1. 警告不是异常你是不是经常在使用一些
- 在Python中将字符串转换为集合使用 set() 类将字符串转换为集合,例如 my_set = set(my_str)。 set() 类将
- 一、简介 transitions库pip install transitions状态机 state:状态节点transition:
- 有很多时候,我们会在python的运行过程中得到一些重要的变量,比如一个数据量很庞大的dict。而且,后面的某些程序也会用到这个dict,那
- 1、IIS为一个死循的执行过程设定执行时间(缺省为90秒)超时事件:<%response.buffer=true%><BO
- 爬取xxx天气爬取网址:https://tianqi.2345.com/today-60038.htm安装pip install scrap
- 笔者在今天的工作中,遇到了一个需求,那就是如何将Python字符串生成PDF。比如,需要把Python字符串‘这是测试文件'生成为P
- 飞机大战(Python)代码分为两个python文件,工具类和主类,需要安装pygame模块,能完美运行(网上好多不完整的,调试得心累。实现
- 前言本文主要给大家介绍了关于Django自定义过滤器的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍:过滤器与函数d
- Python爬虫:一些常用的爬虫技巧总结爬虫在开发过程中也有很多复用的过程,这里总结一下,以后也能省些事情。1、基本抓取网页get方法imp
- 这里有一些很棒的自动化脚本,你可以在你的 Python 项目中使用它们。在做项目的时候,我们需要一些现成的代码来帮助我们解决日常生活中的问题
- javascript模仿alert提示效果,如果你听厌倦了系统自带的那个,可以使用这个alert提示效果,听不错的。相关文章推荐《类似于新浪
- 在这篇入门教程中,我们假定你已经有了PHP语言程序、MySQL数据库、计算机网络通讯及XML语言基础。如果你还没有,那么请先学习相关知识。我
- 在了解装饰器的之前一定要先了解函数作为参数传递, 什么是函数内嵌,请参考我之前写的博客函数简介因为在python里面,函数也是对象,也可以作
- 本文实例讲述了Python实现按照指定要求逆序输出一个数字的方法。分享给大家供大家参考,具体如下:问题是:输入一个数字,按照指定要求逆序输出
- 目标:创建一个字典,记录几对python词语,使用OrderedDict类来写,并按顺序输出。写完报错:[root@centos7 tmp]
- 前一阵看到一篇文章《使用css3仿造window7的开始菜单》,文中仅使用CSS3 实现了Windows 7 开始菜单的动态效果,很久以来一
- ASP具备动态输出任一Office应用程序文件格式的功能。在开始编写代码之前,我们首先需要做的就是设置正确的文件类型,因为浏览器需要知道如何
- 想做个和IBM公司一样的网站LOGO,试了半天也没有做出来,郁闷之下,只好求高手帮助!先在这里谢谢了!方法一1、写上IBM,调节字号颜色2、
- 本文实例讲述了PHP函数按引用传递参数及函数可选参数用法。分享给大家供大家参考,具体如下:一、函数按引用传递参数1. 代码<!DOCT