Python代码实现双链表
作者:伟伟哦 时间:2021-12-26 15:55:04
本文实例为大家分享了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
标签:python,双链表
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
10个不为人知的Google失败作品
2008-05-24 16:56:00
![](https://img.aspxhome.com/file/UploadPic/20085/24/200852417924655s.jpg)
PHP实现判断二叉树是否对称的方法
2023-06-28 13:24:10
python新手练习实例之万年历
2021-01-29 02:20:35
Python configparser模块常用方法解析
2021-07-08 17:31:11
python3发送邮件需要经过代理服务器的示例代码
2023-07-27 01:00:44
另类解读SQL Server中的DateTime数据类型
2009-01-06 11:22:00
Python集中化管理平台Ansible介绍与YAML简介
2023-09-23 12:52:34
![](https://img.aspxhome.com/file/2023/6/88026_0s.png)
表单验证中时间起止判断的递归处理
2009-12-16 19:27:00
在tensorflow中实现屏蔽输出的log信息
2023-02-27 17:41:21
Python logging日志模块 配置文件方式
2021-03-07 04:31:01
pycharm中如何使用快捷键按出代码提示框
2023-03-11 22:18:52
![](https://img.aspxhome.com/file/2023/8/84928_0s.jpg)
社会化音乐:在夹缝中生出花来
2009-08-24 12:37:00
![](https://img.aspxhome.com/file/UploadPic/20098/24/0908-music-flower-01-18s.jpg)
Z-Blog实现摘要图文混排效果的方法
2009-02-23 13:54:00
python使用WMI检测windows系统信息、硬盘信息、网卡信息的方法
2023-06-22 01:57:01
详解Python 中的容器 collections
2021-09-12 07:11:38
PyQT5之使用QT Designer创建基本窗口方式
2023-10-06 05:59:41
![](https://img.aspxhome.com/file/2023/7/91967_0s.png)
Python中的list与tuple集合区别解析
2023-01-13 11:05:23
Python读取YAML文件过程详解
2021-04-21 07:12:25
关于Python字符编码与二进制不得不说的一些事
2022-01-07 14:56:46
Python爬虫基础之requestes模块
2022-04-24 20:20:15
![](https://img.aspxhome.com/file/2023/3/83943_0s.png)