前言先澄清一个前提Python 没有内置的链表类型。内置的list是动态数组底层是一块连续内存collections.deque是分块的双向队列都不是教科书意义上的链表。所以「单向循环链表」不是一个可以import的现成结构而是一道数据结构练习题——用类把节点串起来自己维护指针。另一个容易混的概念「循环」不等于「双向」。单向循环链表只保存一个next指针最后一个节点的next指回第一个节点形成闭环它没有prev。有人一看到「循环」就以为要同时维护前后两个指针那是双向循环链表是另一回事。本文用 Python 3 从零实现一个单向循环链表包括建环、追加、删除、遍历最后用它解一道经典题——约瑟夫环。代码以 Python 3.8 及以上为基准只用标准库。一、结构定义单向循环链表由节点组成。每个节点保存数据和「下一个节点」的引用# 适用于 Python 3 全版本class Node:链表节点。def __init__(self, data):self.data dataself.next Nonedef __repr__(self):return fNode({self.data!r})链表本身只需要记住一个入口——head头节点。为什么只记head就够了因为沿着next一直走总能回到head整个环都能走到。三种状态要分清楚状态head环的样子空链表None没有环只有一个节点指向该节点节点自己指向自己自环多个节点指向首节点首 → 次 → … → 尾 → 首二、追加节点# 适用于 Python 3 全版本class CircularLinkedList:def __init__(self):self.head Noneself.size 0def append(self, data):node Node(data)if self.head is None:self.head nodenode.next node # 单节点自环else:tail self.headwhile tail.next is not self.head: # 走到尾节点tail tail.nexttail.next node # 旧尾指向新节点node.next self.head # 新节点指回首节点闭环self.size 1def __len__(self):return self.size闭环靠两句话旧尾节点的next指向新节点新节点的next指向head。任何一步漏掉环就断了。三、遍历必须有终止条件普通链表靠「走到None」结束循环链表永远走不到None所以终止条件是「又回到head」# 适用于 Python 3 全版本# 下面两个方法接在 CircularLinkedList 类里def __iter__(self):if self.head is None:return # 空链表直接结束迭代cur self.headwhile True:yield cur.datacur cur.nextif cur is self.head: # 回到起点 → 停breakdef __repr__(self):return - .join(str(x) for x in self) - (回到起点)如果没有if cur is self.head: break这一句while True会永远转下去——这是循环链表最经典的死循环 bug。四、删除节点删除要处理三种情况删的是唯一的节点、删的是头节点、删的是中间或尾部节点。关键是要同时拿到前驱节点prev# 适用于 Python 3 全版本# remove 方法同样接在 CircularLinkedList 类里def remove(self, data):if self.head is None:raise ValueError(链表为空无法删除)prev Nonecur self.headwhile True:if cur.data data:breakprev curcur cur.nextif cur is self.head: # 转了一圈没找到raise ValueError(f{data!r} 不在链表中)if cur.next is cur: # 情况一只有一个节点self.head Noneelif prev is None: # 情况二删头节点tail self.headwhile tail.next is not self.head: # 先找尾节点tail tail.nextself.head cur.next # 头指针后移tail.next self.head # 尾节点重新接上新的头else: # 情况三删中间或尾部prev.next cur.nextself.size - 1return cur.data删头节点为什么要先找尾节点因为尾节点的next原本指向旧的头头一换尾节点就必须改指新的头否则环就指向了一个已经被摘掉的节点。实战用循环链表解约瑟夫环n 个人围成一圈从第 1 个开始报数每数到第 k 个就出列然后从下一个人继续报数直到所有人出列。这正是单向循环链表的主场# 适用于 Python 3.8def josephus(n, k):n 个人围成环每数到第 k 个出列返回出列顺序。if n 0 or k 0:raise ValueError(n 和 k 都必须为正整数)head Node(1)prev headfor i in range(2, n 1):node Node(i)prev.next nodeprev nodeprev.next head # 首尾相接成环result []cur headtail prev # tail 始终是 cur 的前驱while cur.next is not cur: # 还剩多个节点for _ in range(k - 1):tail curcur cur.nextresult.append(cur.data)tail.next cur.next # 摘掉 curcur tail.next # 从下一个人重新开始result.append(cur.data) # 最后一个节点return resultdef demo_class():circle CircularLinkedList()for word in [A, B, C, D]:circle.append(word)print(circle) # A - B - C - D - (回到起点)print(长度, len(circle)) # 长度 4circle.remove(C)print(circle) # A - B - D - (回到起点)print(长度, len(circle)) # 长度 3if __name__ __main__:demo_class()print(josephus(5, 2)) # [2, 4, 1, 5, 3]print(josephus(7, 3)) # [3, 6, 2, 7, 5, 1, 4]josephus(5, 2)的输出[2, 4, 1, 5, 3]可以手工验证环为 1-2-3-4-5数到 2 出列依次是 2、4、1、5最后剩下的 3。五、链表与 list 的取舍操作list动态数组单向循环链表按下标访问快一步到位慢要从头沿next走已知位置后插入/删除慢要挪动后续元素快改指针即可是否需要额外内存小每个节点多一个指针字段环形遍历要手动取模天然闭环只有在「频繁在中间增删」且「几乎不需要随机访问」的场景链表才有优势。日常业务里list和dict通常更合适——不要为了「数据结构」而用链表。常见坑点空链表上直接取head.next❌cur self.head; cur cur.next而不先判断head is None✅ 先判空if self.head is None: return遍历没有终止条件导致死循环❌while cur:或while True:里没有「回到 head 就 break」 ✅ 用if cur is self.head: break作为环的终点删头节点后忘记更新尾节点的next❌ 只写self.head cur.next结果尾节点还指向被删的旧头 ✅ 先找到尾节点再tail.next self.head删唯一节点时没断开自环❌ 只把self.head置空却没有意识到该节点仍指向自己 ✅ 用if cur.next is cur:单独处理直接把head置None追加时漏掉指向head的那一步❌tail.next node之后没写node.next self.head✅ 两句都要写环才闭合删除时先移动指针再删丢了节点❌ 先cur cur.next再删cur前置节点已被跳过 ✅ 用prev记住前驱删除时改prev.next cur.next把「循环」当成「双向」❌ 在单向循环链表里访问node.prev✅ 单向循环链表只有next需要前后都能走要用双向循环链表用len(list)的复杂度去套链表❌ 以为在链表中间插入也是 O(1) 而把它当默认选择 ✅ 链表插入是 O(1)前提是已经拿到那个位置的节点按值查找仍是 O(n)总结要点结论Python 是否内置链表否list是动态数组成环条件尾节点next指向head单节点next指向自己遍历终点指针回到head不是None删除关键同时持有前驱prev删头时还要修尾节点典型应用约瑟夫环、轮询调度实现单向循环链表真正容易出错的只有三处建环时的两句指针赋值、遍历时的终止条件、删除头节点时对尾节点的修补。把这三个点守住剩下的就是照抄模板。而要判断该不该用链表先问自己「是随机访问多还是中间增删多」——答案通常是继续用list。