python单向链表实例详解_python_

# Functions  函数声明 class Node():     """     存放节点类     每次调用该类，实例化一个节点     默认每个节点中有数据区，next区。     数据区为该数据，next区为空     """     def __init__(self, item,next=None):         self.item = item         self.next = next         pass class Linklist():     """     存放数据类     将所有的节点存放起来的容器     首先，默认链表为空，在这里需要有一个头节点，默认头节点为空     """     def __init__(self, head=None):         self.head = head     def is_empty(self):         return self.head == None     def append(self, item):         """         往链表尾部添加数据         1、实例化游标：使用游标指向每一个数据，检索数据和判断数据next是否为空         2、移动游标，从头节点开始，每次使用self.next移动，以为next指向的就是下一个数据         3、添加数据，首先判断链表是否为空，为空的情况下，直接将头节点等于node数据         4、如果不为空，需要从头节点开始，移动游标，判断游标指向的next是否为空         5、使用循环不停的移动节点，当遇到节点中的next为空的情况下停止移动         6、循环条件： 当 条件 != None, 进入循环获取，当cur为空时就不会进入循环，所以在这里要使用 cur != None         """         # 首先要实例化一个节点         node = Node(item)         # 如果链表为空         if self.is_empty():             # 直接将头节点的next添加node             self.head = node         else:             # 实例化一个游标             cur = self.head             while cur.next != None:                 # 移动游标，得到最后一个游标的数据                 cur = cur.next             # 将移动后的数据的下一个next添加上 node             cur.next=node             pass     def travel(self):         """遍历数据"""         # 实例化一个游标         cur = self.head         # 数据链为空的情况         if self.is_empty():             print('')         else:             # 获取每个数据区中的数据             # 移动游标，每移动一次，输出一次数据区内的数据             while cur != None:                 print(cur.item, end=' ')                 cur = cur.next             print()     def length(self):         """返回链表的长度"""         # 实例化游标         cur = self.head         # 计数，这里对空链表进行判断，如果是链表，则不会进入循环，直接输出 0         count = 0         # 移动游标，获取下一个数据，然后让count +=1         while cur != None:             # 计数             count+=1             # 移动游标             cur = cur.next         return count     def add(self, item):         """         头部添加数据         分析： 将数据添加到第一个节点当中         1、 需要先将node的next指向 原第一个节点，这原第一个节点就是self.head         2、 再讲self.head指向node进行连接         """         # 先实例化节点         node = Node(item)         # 将数据添加到头部当中         node.next=self.head         self.head=node     def insert(self, index, item):         """         指定位置添加数据         分析：         1、首先要找到，该位置的数据         2、将要添加的数据next等于 原位置的next数据         3、原数据的 next等于node新数据         """         if index<=0:             # 如果输入的索引小于或者等于O，默认使用头插发             self.add(item)         elif index>self.length():             # 如果输入的索引大于链表的长度,使用尾插法             self.append(item)         else:             # 实例化数据节点             node = Node(item)             # 找到该数据的位置             # 实例化一个游标             cur = self.head             # 计数             conent = 0             while conent<(index-1):                 conent+=1                 cur = cur.next             node.next=cur.next             cur.next=node     def search(self, item):         """         查询指定的数据是否存在         分析： 查询指定的数据，需要对整个链表扫描，判断这个数据是否等的该节点中的数据         """         # 实例化一个游标         cur = self.head         # 进行判断是否相等         while cur != None:             # 判断             if cur.item == item:                 return True             else:                 cur = cur.next             pass         # 否则返回False         return False     def remove(self, item):         """         移除指定的数据         分析：         1、删除数据，需要首先判断数据是否存在         2、找到该数据所在的位置，将该数据的上一个数据的next指向自己的next         3、如何获取该数据的指向，和上一个数据的指向         4、需要定义两个指针         5、先将两个指针相等，再讲一个指针先移动一次，再同时移动         """         # 先找到该数据         cur = self.head         por = None         while cur != None:             if cur.item==item:                 # 要判断是否为第一个节点                 if cur == self.head:                     self.head = cur.next                 else:                     por.next = cur.next                 break             else:                 # 如果在当前节点中没有相等的，将节点进行移动                 # 移动要注意，现将两个游标相等，再讲另一个游标移动一次                 por = cur                 cur = cur.next

# 程序的入口 if __name__ == "__main__":     s = Linklist()     s.append(100)     s.append(200)     s.append(300)     s.add(1)     s.add(12)     s.insert(-1,6)          s.travel()       #  6 12 1 100 200 300      print(s.length())  # 6     print(s.search(11)) # False     s.remove(12)     s.travel()       # 6 1 100 200 300      print(s.length())  # 5     print(s.search(11)) # False     pass