python双向循环链表实例详解

使用python实现双向循环链表，供大家参考，具体内容如下

双向循环链表： 将所有的数据存放到节点中，每一个节点相连接，首尾链接，
每一个节点中有一个数据存储区，和两个链接区，一个链接前一个节点，一个链接下一个节点

双向链表操作

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
? ? ? ? # 判断是否为空
? ? ? ? if self.is_empty():
? ? ? ? ? ? return 0
? ? ? ? else:
? ? ? ? ? ? # 不为空
? ? ? ? ? ? # 定义计数
? ? ? ? ? ? count = 1
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? count+=1
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? return count
? ? ? ? ? ? pass

? ? # 3. 遍历链表
? ? def travel(self):
? ? ? ? """
? ? ? ? 遍历链表
? ? ? ? 实例化游标，遍历链表，每次输出节点的数据
? ? ? ? 空链表
? ? ? ? 只有头节点
? ? ? ? """
? ? ? ? # 实例化游标
? ? ? ? cur = self.head
? ? ? ? # 判断是否为空
? ? ? ? if self.is_empty():
? ? ? ? ? ? return None
? ? ? ? else:
? ? ? ? ? ? # 不为空的情况
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? print(cur.item, end=' ')
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? print(cur.item)
? ? ? ? ? ? pass

? ? # 4. 链表头部添加元素
? ? def add(self, item):
? ? ? ? """
? ? ? ? 头节点添加
? ? ? ? 实例化节点，
? ? ? ? """
? ? ? ? # 实例化节点
? ? ? ? node = Node(item)
? ? ? ? # 实例化游标
? ? ? ? cur = self.head
? ? ? ? # 判断是否为空
? ? ? ? if self.is_empty():
? ? ? ? ? ? node.next = node
? ? ? ? ? ? node.prev = node
? ? ? ? ? ? self.head = node
? ? ? ? else:
? ? ? ? ? ? # 链表不为空的情况
? ? ? ? ? ? # 只有一个节点的情况
? ? ? ? ? ? # node.next = self.head
? ? ? ? ? ? node.next = cur
? ? ? ? ? ? node.prev = cur
? ? ? ? ? ? if cur.next == self.head:
? ? ? ? ? ? ? ? # print(cur.item)
? ? ? ? ? ? ? ? cur.prev = node
? ? ? ? ? ? ? ? cur.next = node
? ? ? ? ? ? ? ? self.head = node
? ? ? ? ? ? elif cur.next != self.head:
? ? ? ? ? ? ? ? pro = self.head
? ? ? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? pro.prev = node
? ? ? ? ? ? ? ? cur.next = node
? ? ? ? ? ? ? ? self.head = node
? ? ? ? ? ? ? ? pass

? ? # 5. 链表尾部添加元素
? ? def append(self, item):
? ? ? ? """
? ? ? ? 链表尾部添加数据
? ? ? ? 实例化节点，实例化游标，指向尾部节点，修改指向
? ? ? ? 链表为空
? ? ? ? """
? ? ? ? # 实例化节点
? ? ? ? node = Node(item)
? ? ? ? # 实例化游标
? ? ? ? cur = self.head
? ? ? ? if self.is_empty():
? ? ? ? ? ? self.add(item)
? ? ? ? else:
? ? ? ? ? ? # 不为空的情况
? ? ? ? ? ? # 指针指向最后一个节点
? ? ? ? ? ? self.head.prev = node
? ? ? ? ? ? node.next = self.head
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? node.prev = cur
? ? ? ? ? ? cur.next = node
? ? ? ? ? ? pass

? ? # 6. 链表指定位置添加元素
? ? def insert(self, index, item):
? ? ? ? """
? ? ? ? 指定位置添加数据
? ? ? ? 实例化节点， 实例化游标
? ? ? ? 移动游标到索引位置，更改指向
? ? ? ? 输入索引大小判断
? ? ? ? 链表是否为空
? ? ? ? """
? ? ? ? # 实例化节点
? ? ? ? node = Node(item)
? ? ? ? # 实例化游标
? ? ? ? cur = self.head
? ? ? ? if index <= 0:
? ? ? ? ? ? self.add(item)
? ? ? ? elif index > (self.length()-1):
? ? ? ? ? ? self.append(item)
? ? ? ? else:
? ? ? ? ? ? # 中间添加数据
? ? ? ? ? ? # 声明计数
? ? ? ? ? ? count = 0
? ? ? ? ? ? print(index)
? ? ? ? ? ? while count < index-1:
? ? ? ? ? ? ? ? count+=1
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? # print(cur.item)
? ? ? ? ? ? node.next = cur.next
? ? ? ? ? ? node.prev = cur
? ? ? ? ? ? cur.next.prev = node
? ? ? ? ? ? cur.next = node
? ? ? ? ? ? pass

? ? # 7. 链表删除节点
? ? def remove(self, item):
? ? ? ? """
? ? ? ? 删除数据
? ? ? ? 实例化游标，遍历链表，查找有没有改数据
? ? ? ? 有，对改数据两侧的节点进行指向修改
? ? ? ? """
? ? ? ? # 实例化游标
? ? ? ? cur = self.head
? ? ? ? # 判断是否为空
? ? ? ? if self.is_empty():
? ? ? ? ? ? return None
? ? ? ? else:
? ? ? ? ? ? # 不为空的情况下
? ? ? ? ? ? # 如果删除的是头节点
? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? # 如果只有一个头节点
? ? ? ? ? ? ? ? if cur.next == self.head:
? ? ? ? ? ? ? ? ? ?self.head = None
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? # self.head = cur.next
? ? ? ? ? ? ? ? ? ? pro = cur.next
? ? ? ? ? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? ? ? cur.next = pro
? ? ? ? ? ? ? ? ? ? pro.prev = cur
? ? ? ? ? ? ? ? ? ? self.head = pro
? ? ? ? ? ? ? ? ? ? pass
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? ? ? ? ? # print(cur.item)
? ? ? ? ? ? ? ? ? ? ? ? pro = cur.prev
? ? ? ? ? ? ? ? ? ? ? ? nex = cur.next
? ? ? ? ? ? ? ? ? ? ? ? pro.next = cur.next
? ? ? ? ? ? ? ? ? ? ? ? nex.prev = pro
? ? ? ? ? ? ? ? ? ? ? ? return True
? ? ? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? # 如果是最后一个节点
? ? ? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? ? ? cur.prev.next = self.head
? ? ? ? ? ? ? ? ? ? self.head.prev = cur.prev

? ? # 8. 查找节点是否存在
? ? def search(self, item):
? ? ? ? """
? ? ? ? 查询指定的数据是否存在
? ? ? ? 实例化游标
? ? ? ? 遍历所有的节点。每个节点中判断数据是否相等，相等，返回True
? ? ? ? """
? ? ? ? # 实例化游标
? ? ? ? cur = self.head
? ? ? ? # 判断是否为空
? ? ? ? if self.is_empty():
? ? ? ? ? ? return None
? ? ? ? else:
? ? ? ? ? ? # 不为空的情况
? ? ? ? ? ? # 遍历所有的节点
? ? ? ? ? ? while cur.next != self.head:
? ? ? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? ? ? return True
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? return True
? ? ? ? ? ? pass

测试运行

# 程序的入口
if __name__ == "__main__":
? ? a = Linklist()
? ? a .add(400)
? ? a .add(300)
? ? a .add(200)
? ? a .add(100)
? ? a.append(10)
? ? a.append(11)
? ? a.add(1)
? ? a.insert(30, 12) # 1 100 200 300 400 10 11 12
? ? a.remove(1) ? ?# 100 200 300 400 10 11 12
? ? a.remove(12) ? # 100 200 300 400 10 11
? ? a.remove(400) ?# # 100 200 300 ?10 11
? ? a.remove(4000)
? ? print(a.search(100)) ?# True
? ? print(a.search(11)) ? # True
? ? print(a.search(111)) ?# None
? ? print(a.is_empty()) ? # False
? ? a.travel() ? ? ? ? ? ?# 100 200 300 10 11
? ? print(a.length()) ? ? # 5
? ? pass

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

查看更多关于python双向循环链表实例详解的详细内容...