Python代码实现双链表
作者:伟伟哦 发布时间:2021-12-26 15:55:04
标签:python,双链表
本文实例为大家分享了Python代码实现双链表的具体代码,供大家参考,具体内容如下
双链表的每个节点有两个指针: 一个指向后一个节点,另一个指向前一个节点
class Node(object):
def __init__(self, item=None):
#放数据
self.item= item
#指向后一个节点
self.next = None
#指向前一个节点
self.prior =None
此时当前链表第一个节点就是头节点指向的节点 20就是第一个节点 下图
node.next = self.head 当前节点指向原第一个节点
头插法
如何插入呢
插入
p.next = curNode.next #指向后一个节点
curNode.next.prior = p #指向前一个节点
删除
双链表删除
考虑特殊情况删除的
正常删除
双链表删除 30
#双链表头插法
#停在前一个位置了
count < (pos -1 )
#双向链表 从左往右读
class Node(object):
"""双向链表节点"""
def __init__(self,item):
#放数据的节点
self.elem = item
#指向后一个节点
self.next = None
#指向前一个节点
self.prev = None
#双向链表
class LinkList(object):
def __init__(self,node=None):
#代表头节点
self.__head = node
#判断链表是否为空
def is_empty(self):
return self.__head == None
def length(self):
"""返回链表的长度"""
#cur游标移动,从而实现遍历元素的功能
cur = self.__head
#count用来计数
count = 0
while cur != None:
count += 1
#让cur游标可以向下移动
cur = cur.next
return count
#遍历整个链表
def travel(self):
if self.is_empty():
return
#建立游标等于起始节点
else:
cur = self.__head
while cur != None:
print(cur.elem,end=" ")
cur = cur.next
print("")
#头插法
def add(self,item):
#新节点
node = Node(item)
if self.is_empty():
#头节点指向了新的节点
self.__head = node
else:
#新节点指向原第一个节点
node.next = self.__head
self.__head = node
node.next.prev = node
def append(self,item):
"""链表尾部添加元素"""
node = Node(item) #定义新节点
#链表是否为空链表
if self.is_empty():
#如果为空,新的节点加了进去
self.__head = node
else:
#头节点 创建游标
cur = self.__head #设置指向头结点的游标 此时的当前链表第一个节点,就是头节点指向的节点
#cur到最后一个节点停下
while cur.next != None:
cur = cur.next
#添加节点到尾部 cur道了最后一个结点 cur.next指向了新的节点node 从左往右读
cur.next = node
#当前的节点指向它前一个
node.prev = cur
#插入法 #pos从零开始
def insert(self,pos,item):
"""在指定位置添加元素"""
#指向不是头部元素,self.__head的地址
# 为下一个元素,所以pre为下一个元素
if pos <= 0:
#认为是头插法
self.add(item)
#假如长度是3 pos大于2要特殊处理
elif pos > (self.length()-1):
#尾插法
self.append(item)
else:
#创建节点 新节点
node = Node(item)
cur = self.__head
count = 0
#动起来
while count < pos:
count+=1
cur = cur.next
#把节点链接到中间任意位置 插入前一个节点 此时,cur停在后一个节点
node.next = cur
node.prev = cur.prev
cur.prev.next = node
cur.prev = node
def remove(self,item):
"""删除元素"""
if self.is_empty():
return
cur = self.__head
#查找所有的位置有没有要删除的,若有则删除
while cur != None:
#判断cur指向的数据,是否为要删除的数据 item要删除的元素
if cur.elem == item:
#判断此节点是否为头节点
#考虑特殊情况,恰好要删除是第一个元素 当前的元素就是我要删除的元素
if cur == self.__head:
#如果删除中间, 头节点指向后一个节点
self.__head = cur.next
#考虑链表只有一个节点 直接指向None
if cur.next != None:
#是否只有一个节点
cur.next.prev = None
else:
#中间节点
cur.prev.next = cur.next
if cur.next != None:
cur.next.prev = cur.prev
break
else:
#没有找到,cur游标向继续往下移动
cur = cur.next
def search(self,item):
"""查找结点是否存在"""
#如果是一个空链表
if self.is_empty():
return False
cur = self.__head
while cur.next != self.__head:
#cur数据是否为查找的数据 item是要查的数据
if cur.elem == item:
return True
else:
cur = cur.next
#遍历完成 cur指向None
return False
if __name__ == '__main__':
ll = LinkList()
#第一次的
print(ll.is_empty())
print(ll.length())
ll.append(1)
print(ll.is_empty())
print(ll.length())
ll.append(2)
ll.append(3)
ll.append(4)
ll.append(5)
ll.travel()
ll.insert(-1,50)
ll.travel()
ll.insert(2,60)
ll.travel()
ll.insert(10,300)
ll.travel()
ll.remove(50)
ll.travel()
ll.remove(300)
ll.travel()
来源:https://blog.csdn.net/u012164509/article/details/102878519
0
投稿
猜你喜欢
- 前言Python代码缩进和测试模块是大家学习python必不可少的一部分,本文主要介绍了关于Python代码缩进和测试模块的相关内容,分享出
- 1.安装wkhtmltopdf下载地址:https://wkhtmltopdf.org/downloads.html我测试用的是window
- 本文实例讲述了Python可变和不可变、类的私有属性。分享给大家供大家参考,具体如下:可变和不可变items = []print(id(li
- js格式化金额,可选是否带千分位,可选保留精度,也是网上搜到的,但是使用没问题 /* 将数值四舍五入后格式化. @param num 数值(
- 前言pandas对大数据有很多便捷的清洗用法,尤其针对缺失值和重复值。缺失值就不用说了,会影响计算,重复值有时候可能并未带来新的信息反而增加
- 前言:列表元素能增加就可以删除,这篇文章介绍几种增加元素的方法,虽然都是增加但是也有所不同,这里介绍的删除列表元素的方法也是一样,下面就来演
- Union 与 Union ALL 的作用都是合并 SELECT 的查询结果集,那么它们有什么不同呢? Union 将查询到的结果集合并后进
- 上个月,我写了一篇关于微软如何在向jQuery贡献代码的文章,也谈到了在第一批贡献的代码中的一些功能:jQuery模板和数据链接支持.今天,
- 前言当今,随着计算机技术的发展,摄像头已经成为了人们生活中不可或缺的一部分。而Python作为一种流行的编程语言,也可以轻松地控制和操作摄像
- 日一二三四五六'.split('') ['日','一','二
- 主要利用了XMLHTTP的一些方法和属性来获取服务器的信息。 以下是全部源代码: &
- 我们知道在超级链接的title属性中,是不支持html代码的,我们只能使用文本来处理提示信息。当然借助js可以做出很好的效果。这里讲一下如何
- Go微服务网关从核心原理理解网关的本质网关具备的基本功能:支持多种协议代理:tcp/http/ websocket/grpc支持多种负载均衡
- 复制代码 代码如下: public partial class CMS_DBDataContext { partial void OnCre
- 功能1: 爬取西拉ip代理官网上的代理ip环境:python3.8+pycharm库:requests,lxml浏览器:谷歌IP地址:htt
- 1. 滤波器1.1 什么是滤波器滤波器是对图像做平滑处理 的一种常用工具。平滑处理即在尽可能地保留原图像信息的情况下,对像素值进行微调,使邻
- 你的SQL Server最近是否运行不正常?不,我指的不是我们肯定会遇到的通常的数据库和操作系统问题。我的意思是,你是否经历过服务器的反应迟
- 如题:我写入关键字到数据库,多的时候用|隔开了,我提取再做相关文章搜索的时候,我怎么提取用|隔开的文字啊,这样我就好用关键字做搜索啊 回复:
- Python encode()方法encode() 方法为字符串类型(str)提供的方法,用于将 str 类型转换成 bytes 类型,这个
- type 所有类是type生成的a = 1b = "abc"print("type a:{}&qu