python双向链表实例详解
作者:python-行者 发布时间:2023-10-28 08:25:09
标签:python,双向链表
使用python实现双向链表,供大家参考,具体内容如下
双向链表: 指的是讲数据链接在一起,每个数据是一个节点,每一个节点都有一个数据区,两个链接区,分别链接上一个节点和下一个节点
数据区: 存放数据的地方
prev: 链接上一个节点
next: 链接下一个节点
双向链表操作
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
# 技术器
# 如果链表为空,不会进入循环,直接输出 0
count = 0
# 遍历所有的数据
while cur != None:
count +=1
cur = cur.next
return count
# 3. 遍历链表
def treval(self):
"""
遍历链表,获取所有的数据
使用游标,遍历整个链表,每次输出cur.item 的值
注意链表为空的情况,
"""
# 实例化一个游标
cur = self.head
# 遍历链表
while cur != None:
print(cur.item, end=' ')
cur = cur.next
print()
# 4. 链表头部添加元素
def add(self, item):
"""
头部添加数据
分析:
1、头部添加数据,链表为空时: self.head 指向node
2、链表不为空时: 先将node.next = self.head.next, 再讲 self.head = node
"""
# 实例化节点
node = Node(item)
# 添加数据
# 判断链表是否为空
if self.is_empty():
# 为空,直接将self.head 指向node
self.head=node
else:
# 不为空,先将noede
node.next = self.head
self.head.prev=node
self.head=node
# 5. 链表尾部添加元素
def append(self,item):
"""
尾部添加数据
分析:
要先将指针指向尾部的节点
最后的节点的 cur.next = node, node.prev = cur
"""
# 实例化节点
node = Node(item)
# 实例化游标
cur = self.head
# 移动游标到最后一个节点
# 如果链表为空
# 直接使用头插法
if self.is_empty():
self.add(item)
else:
while cur.next != None:
# cur.next 不为空,则进入循环, 上次循环,是进入上上个节点,但 将cur = cur.next,就指向了最后一个节点
cur = cur.next
node.prev = cur
cur.next = node
# 6. 链表指定位置添加元素
def insert(self, index, item):
"""
指定位置添加数据
分析
单链表中需要实例化两个有游标
双向链表,直接向指针指向索引的位置
将这个位置节点的 cur.
"""
# 实例化节点
node = Node(item)
# 实例化游标
cur = self.head
# 起始位置
count = 0
if index<=0:
# 使用头插法
self.add(item)
elif index > (self.length()-1):
self.append(item)
else:
# 移动游标
while count < index:
# 增加一
count += 1
# 移动游标到索引位置
cur = cur.next
node.next = cur
node.prev = cur.prev
cur.prev.next = node
cur.prev = node
# 7. 链表删除节点
def remove(self,item):
"""
删除指定的节点
首先实例化节点,遍历链表,找到该节点,删除该节点
"""
# 实例化游标
cur = self.head
# 遍历链表,找到该节点
while cur != None:
if cur.item == item:
if self.head == cur:
self.head = cur.next
if cur.next:
cur.next.prev = None
else:
cur.prev.next = cur.next
# 如果有下个节点,防止最后一个节点
if cur.next:
cur.next.prev = cur.prev
pass
break
else:
cur = cur.next
# # 8. 查找节点是否存在
def search(self, item):
"""
查看节点是否存在
分析
遍历链表,查看每一个节点的数据区
空链表
只有头节点
只有尾节点
"""
# 实例化一个游标
cur = self.head
# 遍历链表
while cur != None:
if cur.item == item:
return True
else:
cur = cur.next
return False
测试运行
# 程序的入口
if __name__ == "__main__":
s = Linklist()
print(s.is_empty()) # True
s.append(100)
s.append(200)
s.append(300)
s.add(6)
s.insert(1, 10)
s.search(6)
s.treval() # 6 10 100 200 300
s.remove(100)
s.treval() # 6 10 200 300
pass
来源:https://blog.csdn.net/Dhaihaihai/article/details/111304360
0
投稿
猜你喜欢
- 误区 #16:多个关于数据的损坏和修复误区 坊间流传的很多版本都不正确 我已经听过很多关于数据修复可以做什么、不可以做什么、什么会导致数据损
- 前言在大多数介绍 Buffer 的文章中,主要是围绕数据拼接和内存分配这两方面的。比如我们使用fs模块来读取文件内容的时候,返回的就是一个
- 本文最主要参考的是这一篇,后端也是用django来完成。大文件上传(秒传/断点续传)_使用Vue-Simple-Uploader插件 --V
- 本文实例讲述了PHP实现将浏览历史页面网址保存到cookie的方法。分享给大家供大家参考。具体如下:将浏览历史页面网址保存到cookie,大
- 滑动拼图验证码可以算是滑块验证码的进阶版本,其验证机制相对复杂。本节将介绍两种滑动拼图验证码:初级版和高级版本。初级版滑块拼图验证码初级版滑
- 防止用户通过后退按钮重复提交表单 <% response.Buffer=true response.Expires=0 respons
- Python中包含了许多内建的语言特性,它们使得代码简洁且易于理解。这些特性包括列表/集合/字典推导式,属性(property)、以及装饰器
- 前几篇都是手动录入或随机函数产生的数据。实际有许多类型的文件,以及许多方法,用它们从文件中提取数据来图形化。比如之前python基础(12)
- 前话最近跟着廖雪峰的教程学到 模块 这一节。关于如何自定义一个模块,如果大家不懂的话先来看看基本的介绍:模块在计算机程序的开发过程中,随着程
- 前言本文主要给大家介绍了关于Mysql元数据生成Hive建表语句注释脚本的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的
- 搜了全网都是各种坑,没能解决我的问题。最后自己琢磨出来了。安装好以后,会弹出临时密码 ,copy住。如果手点快了,在通知栏还有一次机会,通知
- SOCKET编程socket(套接字):是一个网络通信的端点,能实现不同主机的进程通信, -通过IP+端口定位对方并发送消息的通信机制分为U
- python代码换行就是每行后面加个 \举个栗子:time = "2017"print "one"
- 创建列表sample_list = ['a',1,('a','b')]Python 列表操作
- 索引和切片一维数组一维数组很简单,基本和列表一致。它们的区别在于数组切片是原始数组视图(这就意味着,如果做任何修改,原始都会跟着更改)。这也
- 1:数据源Hollywood Movie Dataset: 好莱坞2006-2011数据集实验目的: 实现 统计2006-2011的数据综合
- 对设计“以人为本”和“绿色设计”两个观点的反思——兼与设计界同仁商榷Reflection of Two Views: “People-ori
- 我就废话不多说了,大家还是直接看代码吧~</pre><pre code_snippet_id="1947416&
- 导言Bootstrap 轮播(Carousel)插件是一种灵活的响应式的向站点添加滑块的方式。除此之外,内容也是足够灵活的,可以是图像、内嵌
- Python 中提供了对时间日期的多种多样的处理方式,主要是在 time 和 datetime 这两个模块里。一、time 模块time 模