单向循环链表 + 尾指针：让插入删除更高效的秘密武器

你还在用头指针遍历整个链表来尾部插入吗加上一个尾指针时间复杂度从 O(n) 直接降到 O(1)今天我们来聊一个链表中的“小优化大智慧”——单向循环链表配合尾指针。别看只是多存了一个指针它能让尾部插入、头部删除、链表拼接等操作变得异常高效。一、什么是单向循环链表单向循环链表在普通单向链表的基础上将最后一个节点的next指针指向头节点而不是None形成一个闭环。尾指针除了传统的head指针外再维护一个tail指针始终指向链表的最后一个节点。为什么加尾指针没有尾指针时要在尾部插入新节点需要从头遍历到尾部O(n)。有了尾指针直接tail.next new_node然后更新tailO(1)。二、结构图示普通单向链表带头指针head → [A] → [B] → [C] → None尾部插入需要遍历到C才能操作。单向循环链表带尾指针head → [A] → [B] → [C] ──┐ ↑ │ └────────────┘ tail ────────────────────┘tail.next指向head形成环。插入、删除时同时维护head和tail。三、插入操作详解带尾指针1. 头部插入在第一个节点之前步骤创建新节点new_node。new_node.next head新节点指向原头节点。tail.next new_node尾节点的 next 指向新头。head new_node更新头指针。时间复杂度O(1)图示原链表head → [A] → [B] → [C] ─┐ tail ────────────────────┘ 插入 new 到头部后 head → [new] → [A] → [B] → [C] ─┐ tail ────────────────────┘2. 尾部插入在最后一个节点之后步骤创建新节点new_node。new_node.next head新节点指向头保持循环。tail.next new_node原尾节点指向新节点。tail new_node更新尾指针。时间复杂度O(1) —— 因为直接通过tail定位。图示原链表head → [A] → [B] → [C] ─┐ tail ────────────────────┘ 插入 new 到尾部 head → [A] → [B] → [C] → [new] ─┐ tail ────────────────────┘3. 中间插入已知某节点之后与普通单向链表一样需要先找到插入位置的前驱节点O(n)然后修改指针并注意如果插入位置是尾部需要更新tail。四、删除操作详解带尾指针1. 删除头节点步骤如果链表只有一个节点head tail则删除后链表为空设置head tail None。否则head head.next移动头指针。tail.next head保持循环。时间复杂度O(1)图示删除前head → [A] → [B] → [C] ─┐ tail ────────────────────┘ 删除后head → [B] → [C] ─┐ tail ─────────────┘2. 删除尾节点关键删除尾节点需要找到它的前驱节点倒数第二个节点因为单链表无法直接获取前驱。所以即使有tail指针删除尾节点仍需要遍历到倒数第二个节点时间复杂度 O(n)。步骤从head开始遍历找到节点prev使得prev.next tail。prev.next head跳过尾节点指向头。tail prev更新尾指针。如果链表只有一个节点则删除后置空。时间复杂度O(n)特殊优化如果经常需要删除尾节点可以考虑使用双向循环链表那样可以 O(1) 删除尾部。3. 删除中间节点需要先找到前驱节点O(n)然后prev.next curr.next。注意如果删除的是最后一个节点即curr tail需要更新tail为prev。五、时间复杂度总结表操作单向循环链表带尾指针普通单向链表仅头指针头部插入O(1)O(1)尾部插入O(1)O(n)中间插入已知前驱O(1)O(1)头部删除O(1)O(1)尾部删除O(n)O(n)需遍历到倒数第二中间删除已知前驱O(1)O(1)查找元素O(n)O(n)结论尾指针主要优化了尾部插入操作从 O(n) 降为 O(1)。六、Python 实现带详细注释classNode:def__init__(self,val):self.valval self.nextNoneclassCircularLinkedList:def__init__(self):self.headNone# 头指针self.tailNone# 尾指针defis_empty(self):returnself.headisNone# 头部插入definsert_at_head(self,val):new_nodeNode(val)ifself.is_empty():self.headnew_node self.tailnew_node new_node.nextnew_node# 指向自己形成循环else:new_node.nextself.head self.tail.nextnew_node self.headnew_node# 尾部插入O(1)definsert_at_tail(self,val):new_nodeNode(val)ifself.is_empty():self.headnew_node self.tailnew_node new_node.nextnew_nodeelse:new_node.nextself.head self.tail.nextnew_node self.tailnew_node# 删除头节点defdelete_head(self):ifself.is_empty():returnNoneremoved_valself.head.valifself.headself.tail:# 只有一个节点self.headNoneself.tailNoneelse:self.headself.head.nextself.tail.nextself.headreturnremoved_val# 删除尾节点需要遍历O(n)defdelete_tail(self):ifself.is_empty():returnNoneremoved_valself.tail.valifself.headself.tail:# 只有一个节点self.headNoneself.tailNonereturnremoved_val# 找到倒数第二个节点currself.headwhilecurr.next!self.tail:currcurr.next# curr 现在是倒数第二个节点curr.nextself.head self.tailcurrreturnremoved_val# 删除第一个值为 val 的节点defdelete_by_value(self,val):ifself.is_empty():returnFalse# 如果头节点就是要删除的ifself.head.valval:self.delete_head()returnTrue# 遍历查找prevself.head currself.head.nextwhilecurr!self.head:ifcurr.valval:prev.nextcurr.nextifcurrself.tail:# 删除的是尾节点self.tailprevreturnTrueprevcurr currcurr.nextreturnFalse# 遍历打印从 head 开始绕一圈defdisplay(self):ifself.is_empty():print(空链表)returnresult[]currself.headwhileTrue:result.append(str(curr.val))currcurr.nextifcurrself.head:breakprint( - .join(result) - (回到头))# 测试if__name____main__:cllCircularLinkedList()cll.insert_at_tail(10)cll.insert_at_tail(20)cll.insert_at_head(5)cll.display()# 5 - 10 - 20 - (回到头)cll.delete_head()cll.display()# 10 - 20 - (回到头)cll.insert_at_tail(30)cll.display()# 10 - 20 - 30 - (回到头)cll.delete_tail()cll.display()# 10 - 20 - (回到头)cll.delete_by_value(20)cll.display()# 10 - (回到头)七、图解辅助理解ASCII 艺术插入尾部带尾指针初始状态只有一个节点 5 head ──→ [5] ←── tail ↑ │ └─┘ 插入 10 到尾部 head ──→ [5] → [10] ←── tail ↑ │ └───────────┘尾指针直接让5.next 1010.next headtail 10一步到位。删除尾部删除前 head ──→ [5] → [10] → [20] ←── tail ↑ │ └─────────────────┘ 删除尾节点 20 需要找到前驱节点 10 head ──→ [5] → [10] ←── tail ↑ │ └────────┘10.next headtail 10。八、实际应用场景约瑟夫环问题循环链表天然适合模拟围成一圈的人。操作系统进程调度时间片轮转调度算法中就绪队列常用循环链表。缓冲池/对象池需要循环利用固定数量资源时。游戏开发中的回合制战斗角色按顺序行动循环链表可轻松实现。九、总结单向循环链表 尾指针的核心优势是尾部插入 O(1)。头部插入/删除、尾部插入都是 O(1)但尾部删除仍然是 O(n)。空间上只多了一个指针换来了尾部操作的高效。适合需要频繁在尾部添加元素的场景如消息队列、日志收集。思考题如果既要尾部插入 O(1)又要尾部删除 O(1)应该使用什么数据结构提示双向循环链表或者用 Python 的collections.deque如果觉得有用欢迎点赞、收藏、转发下期我们讲“双向循环链表的实现与应用”敬请期待