怎么用Python代码实现双链表
本文小编为大家详细介绍“怎么用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()
读到这里，这篇“怎么用Python代码实现双链表”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注蜗牛博客行业资讯频道。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：niceseo99@gmail.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
版权声明：如无特殊标注，文章均为本站原创，转载时请以链接形式注明文章出处。
评论