时间：2022-10-06 12:00:46 | 栏目：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