python数据结构之单向循环链表

1.形式：单向循环链表的尾结点指向头结点。

2.判断是否为空，计算链表长度，遍历链表，在链表头部、尾部、任意位置插入元素，删除元素、查找元素。

class Node(object): #结点类 def __init__(self,item): self.item = item self.next = None #单链表类 class SingleLinkList(object): def __init(self,node=None): self.__head = node def is_empty(self): #判断链表是否为空 return self.__head is None def length(self): #计算单向循环链表的长度 #考虑特殊情况：链表为空 if self.is_empty(): return 0 cur = self.__head count = 1 while cur.next != self.__head: count += 1 cur = cur.next return count def travel(self): #遍历链表 #判断是否为空 if self.is_empty(): print("") return cur = self.__head while cur.next != self.__head: print(cur.item,end=" ") #设置空格为了取消python3自动换行 cur = cur.next print(cur.item,end=" ")#当cur指向尾结点时循环退出，需单独输出元素 def add(self,item): #头插法：添加元素 #构造结点 node = Node(item) #考虑特殊情况：链表为空 if self.is_empty(): self.__head = node node.next = node cur = self.__head while cur.next != self.__head: cur = cur.next node.next = self.__head self.__head = node cur.next = self.__head 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 cur.next = node node.next = self.__head def insert(self,pos,item): #在链表的指定位置添加元素 if pos <= 0: self.add(item) elif pos>=self.length(): 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 remove(self,item): #删除结点 #考虑链表为空 if self.is_empty(): return cur = self.__head pre = None while cur.next != self.__head: if cur.item == item: if cur == self.__head: rear = self.__head while rear.next != self.__head: rear = rear.next #退出循环后，rear指向尾结点 self.__head = cur.next rear.next = self.__head else: pre.next = cur.next return pre = cur cur = cur.next #退出循环后cur指向尾结点，删除尾结点 if cur.item == item: #考虑当前链表只有一个结点 if cur == self.__head: self.__head = None pre.next = self.__head def search(self,item): #查找元素 #考虑链表为空 if self.is_empty(): return False cur = self.__head while cur is not None: if cur.item == item: return True cur = cur.next #退出循环后，cur指向尾结点 if cur.item == item: return True return False

3.验证程序可行性：

注：非常感谢B站中各位大神分享的python数据结构与算法的视频教程，我仅用该博客作为复习笔记以及知识普及。