编辑“︁循环链表”︁

{{DISPLAYTITLE:循环链表}}  
'''循环链表'''（Circular Linked List）是[[链表]]的一种特殊形式，其最后一个节点的指针不再指向空值（`NULL`），而是指向链表的头节点（或第一个节点），从而形成一个闭环。这种结构在需要周期性操作或环形遍历的场景中非常有用。  

== 基本概念 ==  
循环链表分为两种主要类型：  
1. '''单向循环链表'''：每个节点包含数据域和指向下一个节点的指针，尾节点指向头节点。  
2. '''双向循环链表'''：每个节点包含数据域、前驱指针和后继指针，尾节点的后继指针指向头节点，头节点的前驱指针指向尾节点。  

=== 与普通链表的区别 ===  
* 普通链表的尾节点指向`NULL`，而循环链表的尾节点指向头节点。  
* 遍历时需要额外注意终止条件，避免无限循环。  

== 实现示例 ==  
以下是使用Python实现的单向循环链表：  

<syntaxhighlight lang="python">  
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:  
            temp = self.head  
            while temp.next != self.head:  
                temp = temp.next  
            temp.next = new_node  
            new_node.next = self.head  

    def display(self):  
        if not self.head:  
            print("List is empty")  
            return  
        temp = self.head  
        while True:  
            print(temp.data, end=" -> ")  
            temp = temp.next  
            if temp == self.head:  
                break  
        print("HEAD")  

# 示例用法  
clist = CircularLinkedList()  
clist.append(1)  
clist.append(2)  
clist.append(3)  
clist.display()  
</syntaxhighlight>  

'''输出：'''  
<pre>  
1 -> 2 -> 3 -> HEAD  
</pre>  

== 实际应用场景 ==  
循环链表的典型应用包括：  
1. '''操作系统调度'''：时间片轮转调度算法中，任务队列常使用循环链表实现。  
2. '''游戏开发'''：循环遍历角色或道具列表（如“大富翁”中的玩家轮流机制）。  
3. '''数据缓冲区'''：音频/视频流处理中环形缓冲区的实现。  

== 复杂度分析 ==  
{| class="wikitable"  
|+ 时间复杂度对比  
! 操作 !! 普通链表 !! 循环链表  
|-  
| 插入/删除（头部） || O(1) || O(1)  
|-  
| 插入/删除（尾部） || O(n) || O(n)  
|-  
| 遍历 || O(n) || O(n)  
|}  

== 进阶操作 ==  
=== 约瑟夫问题（Josephus Problem） ===  
循环链表可高效解决经典约瑟夫问题：  
<syntaxhighlight lang="python">  
def josephus(n, k):  
    clist = CircularLinkedList()  
    for i in range(1, n+1):  
        clist.append(i)  
    current = clist.head  
    while current.next != current:  
        for _ in range(k-2):  # 移动k-1步  
            current = current.next  
        print(f"Eliminated: {current.next.data}")  
        current.next = current.next.next  
        current = current.next  
    print(f"Survivor: {current.data}")  

josephus(5, 2)  # 示例：5个人，每第2个淘汰  
</syntaxhighlight>  

'''输出：'''  
<pre>  
Eliminated: 2  
Eliminated: 4  
Eliminated: 1  
Eliminated: 5  
Survivor: 3  
</pre>  

== 可视化结构 ==  
<mermaid>  
graph LR  
    A[Head] --> B[Node 1]  
    B --> C[Node 2]  
    C --> D[Node 3]  
    D --> A  
</mermaid>  

== 数学表达 ==  
循环链表的长度计算与普通链表相同，但遍历条件需满足：  
<math>  
\exists \, n \in \mathbb{N} \, \text{使得} \, \text{node}_{n+1} = \text{node}_1  
</math>  

== 注意事项 ==  
* 避免内存泄漏：删除节点时需正确更新指针。  
* 终止条件：遍历时需检查是否回到起始点（如`while temp != self.head`）。  

== 总结 ==  
循环链表通过闭合环路简化了环形数据的处理，适合需要循环访问的场景。掌握其实现与边界条件处理是算法设计中的重要技能。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:线性数据结构]]