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         # 技术器         # 如果链表为空，不会进入循环，直接输出 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