Python 数据结构：循环链表（Circular Linked List）

# /*
# Python 数据结构：循环链表（Circular Linked List）
# --------------------------------------------------------
# 概念：
# 循环链表是一种链表结构，其中尾节点指向头节点，
# 形成一个环。可以是单向或双向链表。
#
# 特点：
# 1) 可以从任意节点开始遍历，始终回到起点；
# 2) 适合实现轮转队列、约瑟夫问题等场景。
# */

# ========================================================
# 单向循环链表节点定义
# ========================================================
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# ========================================================
# 单向循环链表实现
# ========================================================
class CircularLinkedList:
    def __init__(self):
        self.head = None

    # 插入节点（尾插法）
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

    # 遍历打印链表
    def display(self, count=None):
        if not self.head:
            print("链表为空")
            return
        current = self.head
        i = 0
        while True:
            print(current.data, end=" -> ")
            current = current.next
            i += 1
            if current == self.head or (count is not None and i >= count):
                break
        print("(head)")

    # 删除指定值节点
    def delete(self, key):
        if not self.head:
            return

        current = self.head
        prev = None

        # 单节点情况
        if current.data == key and current.next == self.head:
            self.head = None
            return

        # 查找节点
        while True:
            if current.data == key:
                if prev:
                    prev.next = current.next
                else:  # 删除头节点
                    # 找到尾节点指向新头
                    tail = self.head
                    while tail.next != self.head:
                        tail = tail.next
                    self.head = current.next
                    tail.next = self.head
                return
            prev = current
            current = current.next
            if current == self.head:
                break

# ========================================================
# 示例演示
# ========================================================
cll = CircularLinkedList()
for value in [10, 20, 30, 40]:
    cll.append(value)

print("初始循环链表（完整显示一圈）:")
cll.display()

print("\n删除节点 20:")
cll.delete(20)
cll.display()

print("\n删除节点 10（头节点）:")
cll.delete(10)
cll.display()

print("\n删除节点 40（尾节点）:")
cll.delete(40)
cll.display()

print("\n删除节点 30（最后节点）:")
cll.delete(30)
cll.display()

# ========================================================
# 要点总结：
# --------------------------------------------------------
# 1) 循环链表尾节点指向头节点，形成闭环；
# 2) 插入操作需处理空链表与尾节点指向问题；
# 3) 删除头节点时必须更新尾节点指针；
# 4) 遍历链表时注意避免无限循环，可限制循环次数；
# 5) 适用于轮转任务、约瑟夫问题等场景。
# */

#
# 初始循环链表（完整显示一圈）:
# 10 -> 20 -> 30 -> 40 -> (head)
#
# 删除节点 20:
# 10 -> 30 -> 40 -> (head)
#
# 删除节点 10（头节点）:
# 30 -> 40 -> (head)
#
# 删除节点 40（尾节点）:
# 30 -> (head)
#
# 删除节点 30（最后节点）:
# 链表为空