python实现双链表
作者:我的加奈 发布时间:2022-06-20 01:47:48
标签:python,双链表
本文实例为大家分享了python实现双链表的具体代码,供大家参考,具体内容如下
实现双链表需要注意的地方
1、如何插入元素,考虑特殊情况:头节点位置,尾节点位置;一般情况:中间位置
2、如何删除元素,考虑特殊情况:头结点位置,尾节点位置;一般情况:中间位置
代码实现
1.构造节点的类和链表类
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.previous = None
class DoubleLinkList:
'''双链表'''
def __init__(self, node=None):
self._head = node
以下方法均在链表类中实现
2. 判断链表是否为空
def is_empty(self):
return self._head is None
3. 输出链表的长度
def length(self):
count = 0
if self.is_empty():
return count
else:
current = self._head
while current is not None:
count += 1
current = current.next
return count
4. 遍历链表
def travel(self):
current = self._head
while current is not None:
print("{0}".format(current.data), end=" ")
current = current.next
print("")
5.头插法增加新元素
def add(self, item):
node = Node(item)
# 如果链表为空,让头指针指向当前节点
if self.is_empty():
self._head = node
# 注意插入的顺序,
else:
node.next = self._head
self._head.previous = node
self._head = node
6. 尾插法增加新元素
def append(self, item):
node = Node(item)
# 如果链表为空,则直接让头指针指向该节点
if self.is_empty():
self._head = node
# 需要找到尾节点,然后让尾节点的与新的节点进行连接
else:
current = self._head
while current.next is not None:
current = current.next
current.next = node
node.previous = current
7. 查找元素是否存在链表中
def search(self, item):
current = self._head
found = False
while current is not None and not found:
if current.data == item:
found = True
else:
current = current.next
return found
8. 在某个位置中插入元素
def insert(self, item, pos):
# 特殊位置,在第一个位置的时候,头插法
if pos <= 0:
self.add(item)
# 在尾部的时候,使用尾插法
elif pos > self.length() - 1:
self.append(item)
# 中间位置
else:
node = Node(item)
current = self._head
count = 0
while count < pos - 1:
current = current.next
count += 1
# 找到了要插入位置的前驱之后,进行如下操作
node.previous = current
node.next = current.next
current.next.previous = node
current.next = node
# 换一个顺序也可以进行
def insert2(self, item, pos):
if pos <= 0:
self.add(item)
elif pos > self.length() - 1:
self.append(item)
else:
node = Node(item)
current = self._head
count = 0
while count < pos:
current = current.next
count += 1
node.next = current
node.previous = current.previous
current.previous.next = node
current.previous = node
9. 删除元素
def remove(self, item):
current = self._head
if self.is_empty():
return
elif current.data == item:
# 第一个节点就是目标节点,那么需要将下一个节点的前驱改为None 然后再将head指向下一个节点
current.next.previous = None
self._head = current.next
else:
# 找到要删除的元素节点
while current is not None and current.data != item:
current = current.next
if current is None:
print("not found {0}".format(item))
# 如果尾节点是目标节点,让前驱节点指向None
elif current.next is None:
current.previous.next = None
# 中间位置,因为是双链表,可以用前驱指针操作
else:
current.previous.next = current.next
current.next.previous = current.previous
# 第二种写法
def remove2(self, item):
"""删除元素"""
if self.is_empty():
return
else:
cur = self._head
if cur.data == item:
# 如果首节点的元素即是要删除的元素
if cur.next is None:
# 如果链表只有这一个节点
self._head = None
else:
# 将第二个节点的prev设置为None
cur.next.prev = None
# 将_head指向第二个节点
self._head = cur.next
return
while cur is not None:
if cur.data == item:
# 将cur的前一个节点的next指向cur的后一个节点
cur.prev.next = cur.next
# 将cur的后一个节点的prev指向cur的前一个节点
cur.next.prev = cur.prev
break
cur = cur.next
10. 演示
my_list = DoubleLinkList()
print("add操作")
my_list.add(98)
my_list.add(99)
my_list.add(100)
my_list.travel()
print("{:#^50}".format(""))
print("append操作")
my_list.append(86)
my_list.append(85)
my_list.append(88)
my_list.travel()
print("{:#^50}".format(""))
print("insert2操作")
my_list.insert2(66, 3)
my_list.insert2(77, 0)
my_list.insert2(55, 10)
my_list.travel()
print("{:#^50}".format(""))
print("insert操作")
my_list.insert(90, 4)
my_list.insert(123, 5)
my_list.travel()
print("{:#^50}".format(""))
print("search操作")
print(my_list.search(100))
print(my_list.search(1998))
print("{:#^50}".format(""))
print("remove操作")
my_list.remove(56)
my_list.remove(123)
my_list.remove(77)
my_list.remove(55)
my_list.travel()
print("{:#^50}".format(""))
print("remove2操作")
my_list.travel()
my_list.remove2(100)
my_list.remove2(99)
my_list.remove2(98)
my_list.travel()
来源:https://blog.csdn.net/CSDNwg/article/details/122492275
0
投稿
猜你喜欢
- 分页功能在每个网站都是必要的,对于分页来说,其实就是根据用户的输入计算出应该显示在页面上的数据在数据库表中的起始位置。确定分页需求:1. 每
- 不知道用ASP写代码的朋友是不是和我有一样的感受,ASP中最头疼的就是调试程序的时候不方便,我想可能很多朋友都会用这样的方法&ldq
- 写程序的人在编写由asp页面生成静态页面html的时候,如果同时生成大量页面,一定遇到过浏览器下方的进度条上显示着3%,6%,10%等缓慢增
- 使用Python语句,读取Linux远端服务器上的文件打印到控制台的代码实现:下载包:paramikoimport paramiko#服务器
- 前言:工作中遇到以下小问题,解决方法如下,可能比较暴力,暂时留档,再进行优化。要求:将列表中json的 ‘id&
- Web 标准要求一览表Russ WeakleyJjgod Jiang14-Aug-2004目录1 Web 标准,不仅仅是“不用表格的站点”2
- <% dim result,result1 str="ad_asp之家_nzlkjlkfjoj
- RegMail是用来存放注册邮件的表,现以创建时间(CreateTime)字段来给表进行分区,具体步骤如下:--为分区创建存储文件 
- 1.函数对象前面我们学习了关于Python中的变量类型,例如int、str、bool、list等等…&hell
- 本文实例为大家分享了python将两张图片生成全景图片的具体代码,供大家参考,具体内容如下1、全景图片的介绍全景图通过广角的表现手段以及绘画
- 目录实验环境依赖项安装编程实现浏览器有一个可以用于展示网页的窗口代码总结实验环境操作系统:Linux Mint编辑器:vim编程语言:pyt
- 问题描述字符串本身作为 bytess = '\xe4\xbd\xa0\xe5\xa5\xbd'解决方案s.encode(
- ORA-00600:internal error code,arguments:[num],[?],[?],[?],[?]产生原因:这种错误
- 直方图,又称质量分布图,是一种统计报告图,由一系列高度不等的纵条或线段表示数据分布情况。用横轴表示数据类型,纵轴表示分布情况。直方图是数值数
- 一个简单的JS显示日期代码,可以显示星期几<script type="text/javascript">fu
- python中有的df列比较长head的时候会出现省略号,现在数据分析常用的就是基于anaconda的notebook和sypder,在sp
- 信息图表设计(Inforgraphic Design),是信息设计(Information Design)学科的一个分支,它兴起于20世纪末
- 阅读上一篇:FrontPage2002简明教程六:图片库 虽然FrontPage已经给我们提供了很多面很强大的所见即所得的工具,但是随着HT
- 如何显示最后十名来访者?代码和说明见下:<%Application.LockIF NOT isArray(&nbs
- 程序开始:<% Server.ScriptTimeout = &HE10 '&