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

# Functions  函数声明 class Node():     """实例化节点类"""     def __init__(self, item):         self.item = item         self.next = None class Linklist():     """     存放节点类     """     def __init__(self):         self.head = None     # 1. 链表是否为空     def is_empty(self):         return self.head == None     # 2. 链表的长度     def length(self):         """         返回链表的长度         遍历所有的节点，使用计数器计数         1、链表为空情况         """         # 实例化节点         cur = self.head         if self.is_empty():             return 0         else:             # 计数             count = 1             # 遍历链表             while cur.next != self.head:                 count+=1                 cur = cur.next             return count     # 3. 遍历链表     def travel(self):         """         遍历链表，获取所有的数据         实例游标，遍历数据，输出数据         1、 空链表情况         2、 只有头部节点情况         3、 只有尾部节点情况         """         # 实例化游标         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)     # 4. 链表头部添加元素     def add(self, item):         """         往链表头部添加数据         分析         链表为空             self.head 直接指向node， 再讲node指向自己         链表不为空             node.next = self.head         """         # 实例化游标         cur = self.head         # 实例化节点         node = Node(item)         # 判断是否为空         if self.is_empty():             self.head = node             node.next = node         else:             # 不为空的情况             # 要将最后一个节点指向node             while cur.next != self.head:                 cur = cur.next             node.next = self.head             self.head = node             cur.next = node     # 5. 链表尾部添加元素     def append(self, item):         """         往尾部添加数据         分析         实例化节点，再实例化游标先指向最后一个节点         调换指向         1、空链表情况         2、只有一个链表情况         """         # 实例化节点         node = Node(item)         # 实例化游标         cur = self.head         # 判断是否为空         if self.is_empty():             self.add(item)         else:             # 不为空的情况,移动游标指向最后一个节点             while cur.next != self.head:                 cur = cur.next             node.next = self.head             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:             # 判断链表是否为空             if self.is_empty():                 self.add(item)             else:                 # 移动游标，指向指定的索引位置                 count = 0                 while count < index-1:                     count+=1                     cur = cur.next                 node.next = cur.next                 cur.next = node             pass     # 7. 链表删除节点     def remove(self, item):         """         删除指定的节点         实例化游标，遍历链表插件这个节点是否存在，存在则更改指向         不存在，则不修改         空链表情况         头节点情况         尾结点情况         """         # 实例化游标         cur = self.head         if self.is_empty():             return None         else:             # 不为空，遍历链表，对比数据是否相等             # 如果头节点是要删除的数据             if cur.item == item:                 self.head=cur.next                 # 找出最后的节点，将最后的节点指向，删除后面的那个节点                 while cur.next != self.head:                     cur = cur.next                 cur.next = cur.next             else:                 pro = None                 while cur.next != self.head:                     if cur.item == item:                         if cur.item == item:                             pro.next = cur.next                             return True                     else:                         pro = cur                         cur = cur.next                 if cur.item == item:                     pro.next = self.head             pass     # 8. 查找节点是否存在     def search(self, item):         """         查找该节点是否存在         实例化游标，遍历所有的节点         查看当前节点的数据是否和item 相等         空链表         头节点         尾结点         """         # 实例化游标         cur = self.head         # 判断空链表         if self.is_empty():             return None         else:             # 不为空遍历整个链表             if cur.item == item:                 return True             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.insert(4,6)     # a.remove(6)     print(a.length())  # 5     a.travel()         # 100 200 300 400 6     print(a.search(100)) # True     pass