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

# /*
# Python 数据结构：双向循环链表（Doubly Circular Linked List）
# --------------------------------------------------------
# 概念：
# 双向循环链表是双向链表的变种，尾节点的 next 指向头节点，
# 头节点的 prev 指向尾节点，形成闭环。
#
# 特点：
# 1) 支持正向和反向循环遍历；
# 2) 插入和删除操作高效；
# 3) 可用于实现轮转队列、约瑟夫问题等场景。
# */

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

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

    # 尾插法添加节点
    def append(self, data):
        new_node = DCNode(data)
        if not self.head:
            self.head = new_node
            new_node.next = new_node
            new_node.prev = new_node
        else:
            tail = self.head.prev
            tail.next = new_node
            new_node.prev = tail
            new_node.next = self.head
            self.head.prev = new_node

    # 正向遍历（可指定循环次数避免无限循环）
    def display_forward(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 display_backward(self, count=None):
        if not self.head:
            print("链表为空")
            return
        current = self.head.prev  # 尾节点
        i = 0
        while True:
            print(current.data, end=" <-> ")
            current = current.prev
            i += 1
            if current.next == self.head.prev or (count is not None and i >= count):
                break
        print("(tail)")

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

        current = self.head
        while True:
            if current.data == key:
                # 仅有一个节点
                if current.next == current:
                    self.head = None
                    return
                # 更新前后节点指针
                current.prev.next = current.next
                current.next.prev = current.prev
                # 删除头节点时更新 head
                if current == self.head:
                    self.head = current.next
                return
            current = current.next
            if current == self.head:
                break

# ========================================================
# 示例演示
# ========================================================
dcll = DoublyCircularLinkedList()
for val in [10, 20, 30, 40]:
    dcll.append(val)

print("正向遍历（显示一圈）:")
dcll.display_forward()

print("\n反向遍历（显示一圈）:")
dcll.display_backward()

print("\n删除节点 20:")
dcll.delete(20)
dcll.display_forward()

print("\n删除头节点 10:")
dcll.delete(10)
dcll.display_forward()

print("\n删除尾节点 40:")
dcll.delete(40)
dcll.display_forward()

print("\n删除最后节点 30:")
dcll.delete(30)
dcll.display_forward()

# ========================================================
# 要点总结：
# --------------------------------------------------------
# 1) 双向循环链表形成闭环，尾节点指向头节点，头节点指向尾节点；
# 2) 插入和删除节点操作需同时更新前驱和后继指针；
# 3) 正向和反向遍历都可无限循环，需要限制循环次数避免死循环；
# 4) 删除唯一节点后需将 head 置为 None；
# 5) 适用于轮转任务、约瑟夫问题、双向队列等场景。
# */

#
# 正向遍历（显示一圈）:
# 10 <-> 20 <-> 30 <-> 40 <-> (head)
#
# 反向遍历（显示一圈）:
# 40 <-> (tail)
#
# 删除节点 20:
# 10 <-> 30 <-> 40 <-> (head)
#
# 删除头节点 10:
# 30 <-> 40 <-> (head)
#
# 删除尾节点 40:
# 30 <-> (head)
#
# 删除最后节点 30:
# 链表为空