写给自己看的笔记, 很多坑
标准版
class Node(object): def __init__(self, item): self.elem = item self.next = None class xunhuanLinkList(object): def __init__(self, node=None): self.__head = node if node: node.next = node def is_empty(self): return self.__head is None def length(self): if self.is_empty(): return 0 else: cur = self.__head count = 1 while cur.next != self.__head: count += 1 cur = cur.next return count def tarvel(self): if self.is_empty(): return "空链表" else: cur = self.__head while cur.next != self.__head: print(cur.elem, end=(" ")) cur = cur.next print(cur.elem, end=" ") print("") def add(self, item): node = Node(item) if self.is_empty(): node.next = node self.__head = node else: cur = self.__head while cur.next != self.__head: cur = cur.next node.next = self.__head self.__head = node cur.next = node def append(self, item): node = Node(item) if self.is_empty(): self.__head = node node.next = node else: cur = self.__head while cur.next != self.__head: cur = cur.next node.next = self.__head cur.next = node def insert(self, pos, item): if self.is_empty and pos <= 0: self.add(item) elif pos >= (self.length() - 1): self.append(item) else: cur = self.__head count = 0 while count != (pos - 1): count += 1 cur = cur.next node = Node(item) node.next = cur.next cur.next = node def search(self, item): if self.is_empty(): return False else: cur = self.__head while cur.next != self.__head: if cur.elem == item: return True else: cur = cur.next if cur.elem == item: return True return False def remove(self, item): if self.is_empty(): return False else: cur = self.__head pro = None while cur.next != self.__head: if cur.elem == item: if cur == self.__head: weiba = self.__head while weiba.next != self.__head: weiba = weiba.next self.__head = cur.next weiba.next = self.__head else: pro.next = cur.next return else: pro = cur cur = cur.next if cur.elem == item: if cur == self.__head: self.__head = None else: pro.next = cur.next
注释版
class Node(object): def __init__(self, item): # 这是一个节点类，内部的初始化函数, 此类的每一个实例对象都会拥有此函数内部的属性 # 创建一个节点, 此节点包含元素域,next域 self.elem = item self.next = None class xunhuanLinkList(object): def __init__(self, node=None): # 这是一个链表类, 内部的初始化函数, 此类的每一个实例独享都会拥有此函数内部的属性 self.__head = node # 创建头节点, node = None, 链表默认的node指向None, 以传递进来的node为准 if node: # 如果node不为空, node的next域指向node(自身) node.next = node # 如果node为空, node的next域指向None """self.is_empty() 等价于 self.__head == None""" """cur.next != self.__head, 该条件是判断此节点是否为链表的未节点""" def is_empty(self): # 判断是否为空 return self.__head is None # 如果self.__head头节点指向None,代表该链表为空, 返回True # 反之, 返回False def length(self): # 判断链表的偿付 if self.is_empty(): # 如果链表为空 return 0 else: # 链表不为空 cur = self.__head # 创建游标cur, 指向头节点 count = 1 # 以计数的方式来计算长度 while cur.next != self.__head: # cur.next != self.__head, 该条件是如果不是最后一个节点, 则一直循环 count += 1 # 计数加一 cur = cur.next # 游标向后移动一位 return count # 注意: 当循环结束后, 游标指向最后一个节点, # 注意: 当链表只有一个节点的时候,怎么办 def tarvel(self): # 遍历列表 if self.is_empty(): # 如果链表为空直接返回 return "空链表" else: # 如果链表不为空 cur = self.__head # 创建游标 while cur.next != self.__head: # 如果不是尾节点, 则一直循环 print(cur.elem, end=(" ")) # 循环一次打印一下, 当前节点的值 cur = cur.next # 游标后移一位 print(cur.elem, end=" ") # 当循环结束的时候, 游标指向最后一个节点, 但并没有进入循环体, 没有打印最后一个节点的值, # 所以在循环结束后, 打印一下尾节点的值 print("") # 该函数指向完毕, 换行操作 def add(self, item): # 链表头部添加节点 node = Node(item) # 创建一个新节点(node), 该节点的elem元素值为item if self.is_empty(): # 如果链表为空 node.next = node # 该节点的next域指向自身 self.__head = node # 将链表的头节点指向node节点 else: # 链表不为空 cur = self.__head # 创建游标, 寻找尾节点 while cur.next != self.__head: # 如果该游标指向的不是尾节点, 则后移一位 cur = cur.next # 当循环结束后, 游标指向尾节点 node.next = self.__head # 新节点(node)的next域指向原链表的头节点 self.__head = node # 链表的头节点指向新节点node cur.next = node # 等价于cur.next = self.__head # 尾节点的next域, 指向链表的头节点 def append(self, item): # 链表尾部追加节点 node = Node(item) # 创建一个新节点node if self.is_empty(): # 链表为空 self.__head = node # 将链表的头部指向新节点node node.next = node # node的next域指向node(自身) else: cur = self.__head # 创建游标 while cur.next != self.__head: # 如果不是最后一个节点, 则一直循环 cur = cur.next # 游标后移一位 node.next = self.__head # 将node的next域, 指向链表的头部 cur.next = node # 等价于 cur.next = self.__head(上步代码标识node为链表的头节点) # 尾节点的next域,指向链表的头节点 def insert(self, pos, item): # 指定位置，插入元素 if self.is_empty and pos <= 0: # 如果链表为空或者pos指定位置小于0, 则执行在链表头部添加节点 self.add(item) elif pos >= (self.length() - 1): # 如果指定位置, 大于尾节点的下标, 则执行尾部追加 self.append(item) else: cur = self.__head # 创建游标 count = 0 # 以计数的方式找到指定下标处 while count != (pos - 1): # 找到指定下标节点的前驱节点处 count += 1 # 计数加一 cur = cur.next # 游标后移 node = Node(item) # 创建一个新节点node node.next = cur.next # 循环结束后, 游标指向, 指定下标的前驱节点位置处 # 让node的next域指向, 游标cur节点的后继节点处 cur.next = node # 让游标cur节点的next域, 指向新节点node def search(self, item): # 查找元素 if self.is_empty(): # 如果链表为空, 返回False return False else: # 反之 cur = self.__head # 创建游标 while cur.next != self.__head: # 遍历所有元素 if cur.elem == item: # 如果游标指向的当前节点的elem元素等于要查找的元素, 返回True return True else: # 如果没有找到, 游标后移一位 cur = cur.next # 循环结束后, 游标指向最后一个节点, 该节点并没有进入循环体内, 所以要判断最后一个元素是否为要查找的item if cur.elem == item: return True return False # 注意点: 1. 链表为空, 2. 链表只有一个节点 3. item为最后一个节点 def remove(self, item): # 链表为空 # 链表只有一个节点 # 要查找的元素是首节点 # 要查找的元素是尾节点 if self.is_empty(): # 如果链表为空, 返回False return False else: # 链表不为空 cur = self.__head pro = None # 创建两个游标, cur当前元素, pro前驱元素 while cur.next != self.__head: # 遍历元素到尾节点 if cur.elem == item: # 找到item的节点 if cur == self.__head: # 首节点 weiba = self.__head while weiba.next != self.__head: weiba = weiba.next # 循环结束游标weiba指向尾节点 self.__head = cur.next weiba.next = self.__head else: # 中间节点 pro.next = cur.next # 当找到item节点之后, 执行完代码直接退出 return else: pro = cur cur = cur.next # 循环结束后cur指向尾节点 if cur.elem == item: if cur == self.__head: # 链表只有一个节点 self.__head = None else: pro.next = cur.next
测试代码
if __name__ == "__main__": tll = xunhuanLinkList() print(tll.is_empty()) print(tll.length()) tll.append(1) tll.tarvel() print(tll.is_empty()) print(tll.length()) tll.add(2) tll.tarvel() tll.append(1) tll.tarvel() tll.add(100) tll.tarvel() tll.append(2) tll.append(4) tll.append(5) tll.append(6) tll.tarvel() tll.insert(1, 3) tll.tarvel() print(tll.search(2)) print(tll.search(900)) tll.remove(3) tll.tarvel() tll.remove(2) tll.tarvel() tll.remove(1) tll.tarvel() print(tll.search(1)) print(tll.search(10))