python双向循环链表实例详解_python_

# 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