循环链表（Circular Linked List）原理与应用

1. 循环链表的基本概念

循环链表是一种特殊的链表，其最后一个节点的指针不是指向 null，而是指向头节点（或第一个节点），形成一个环状结构。根据方向可分为：

• 单向循环链表：尾节点指向头节点。
• 双向循环链表：尾节点指向头节点，头节点的前驱指向尾节点。

核心特点：

• 从任意节点出发均可遍历整个链表；
• 适合需要循环访问的场景（如轮询调度、缓冲区管理）。

2. 循环链表的表示与初始化

以单向循环链表为例，节点结构如下：

struct Node {  
    int data;  
    Node* next;  
};  

初始化空链表：

• 创建一个头节点（可存储哨兵值或为空），其 next 指针指向自身。

Node* initCircularList() {  
    Node* head = new Node{0, nullptr};  
    head->next = head; // 指向自身形成环  
    return head;  
}  

3. 插入操作详解

（1）在头部插入

步骤：

1. 创建新节点 newNode；
2. 将 newNode->next 指向原头节点的下一个节点；
3. 将头节点的 next 指向 newNode。

void insertFront(Node* head, int value) {  
    Node* newNode = new Node{value, head->next};  
    head->next = newNode;  
}  

注意：若链表为空（仅头节点），插入后仍满足循环性质。

（2）在尾部插入

步骤：

1. 遍历找到尾节点（tail->next == head）；
2. 将新节点插入尾节点之后，并使其指向头节点。

void insertEnd(Node* head, int value) {  
    Node* tail = head;  
    while (tail->next != head) {  
        tail = tail->next;  
    }  
    tail->next = new Node{value, head};  
}  

4. 删除操作详解

（1）删除头节点后的第一个节点

步骤：

1. 检查链表是否为空（head->next == head）；
2. 记录待删除节点 temp = head->next；
3. 将 head->next 指向 temp->next；
4. 释放 temp。

void deleteFront(Node* head) {  
    if (head->next == head) return; // 空链表  
    Node* temp = head->next;  
    head->next = temp->next;  
    delete temp;  
}  

（2）删除特定值的节点

步骤：

1. 遍历链表，同时记录前驱节点 prev 和当前节点 curr；
2. 若 curr->data == target，将 prev->next 指向 curr->next；
3. 注意处理尾节点指向头节点的循环关系。

void deleteValue(Node* head, int target) {  
    Node* prev = head, *curr = head->next;  
    while (curr != head) {  
        if (curr->data == target) {  
            prev->next = curr->next;  
            delete curr;  
            return;  
        }  
        prev = curr;  
        curr = curr->next;  
    }  
}  

5. 遍历与检测环的正确性

遍历操作：

• 从头节点的下一个节点开始，直到回到头节点结束。

void traverse(Node* head) {  
    Node* curr = head->next;  
    while (curr != head) {  
        cout << curr->data << " ";  
        curr = curr->next;  
    }  
}  

检测循环完整性：

• 若遍历回到起点且无空指针，则循环结构正确。

6. 应用场景举例

1. 轮询调度：操作系统中的进程调度器可用循环链表实现时间片轮转。
2. 缓冲区管理：数据流处理中循环链表作为环形缓冲区（如生产者-消费者模型）。
3. 约瑟夫问题：经典数学问题中，参与者围成圆圈，循环链表可模拟淘汰过程。

7. 双向循环链表的特性

• 每个节点包含 prev 和 next 指针；
• 插入和删除需同时维护前驱和后继指针，但时间复杂度仍为 O(1)；
• 示例：在节点 P 后插入新节点 N：

  N->next = P->next;  
  N->prev = P;  
  P->next->prev = N;  
  P->next = N;  
  

8. 总结

• 优势：无需额外遍历即可从尾部快速回到头部，适合循环访问场景。
• 劣势：相比普通链表，代码需谨慎处理指针的循环指向，避免死循环或内存泄漏。
• 关键点：始终维护尾节点指向头节点的闭环关系。