Circular Linked List - 首尾相连的环形数据结构
循环链表（Circular Linked List）是一种特殊的链式数据结构，其最后一个节点的指针不是指向NULL，而是指回链表的第一个节点，从而形成一个闭环。这种"首尾相连"的特性使得从任意节点出发都能遍历整个链表。
普通单链表的最后一个节点指向NULL，遍历到末尾即停止；而循环链表没有明确的终点，遍历时需要通过判断是否回到起始节点来确定是否完成一轮遍历。
每个节点只有一个指向下一个节点的指针，最后一个节点指向头节点。结构简单，内存占用小。
每个节点有两个指针，分别指向前驱和后继节点。头节点的prev指向尾节点，尾节点的next指向头节点，形成双向闭环。
// 单向循环链表节点结构
struct Node {
int data; // 数据域：存储节点数据
Node* next; // 指针域：指向下一个节点
};
// 特点：最后一个节点的next指向头节点
// tail->next == head
// 双向循环链表节点结构
struct DNode {
int data; // 数据域
DNode* prev; // 前驱指针：指向前一个节点
DNode* next; // 后继指针：指向下一个节点
};
// 特点：形成双向闭环
// head->prev == tail
// tail->next == head
通过下方的交互工具，直观体验循环链表的基本操作：
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class CircularLinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// 在尾部插入节点
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
newNode.next = this.head; // 指向自己形成环
} else {
let current = this.head;
while (current.next !== this.head) {
current = current.next;
}
current.next = newNode;
newNode.next = this.head;
}
this.size++;
}
// 删除指定值的节点
remove(data) {
if (!this.head) return false;
let current = this.head;
let prev = null;
// 找到尾节点
while (current.next !== this.head) {
prev = current;
current = current.next;
}
prev = current; // prev现在是尾节点
current = this.head;
do {
if (current.data === data) {
if (this.size === 1) {
this.head = null;
} else if (current === this.head) {
prev.next = current.next;
this.head = current.next;
} else {
prev.next = current.next;
}
this.size--;
return true;
}
prev = current;
current = current.next;
} while (current !== this.head);
return false;
}
// 查找节点
search(data) {
if (!this.head) return -1;
let current = this.head;
let index = 0;
do {
if (current.data === data) return index;
current = current.next;
index++;
} while (current !== this.head);
return -1;
}
// 遍历打印
traverse() {
if (!this.head) return "Empty List";
let result = [];
let current = this.head;
do {
result.push(current.data);
current = current.next;
} while (current !== this.head);
return result.join(" → ") + " → (回到头节点)";
}
}
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 在尾部插入
void append(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
newNode->next = *head;
return;
}
Node* temp = *head;
while (temp->next != *head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = *head;
}
// 遍历链表
void traverse(Node* head) {
if (head == NULL) {
printf("Empty List\n");
return;
}
Node* temp = head;
do {
printf("%d → ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(back to head)\n");
}
优化提示：如果维护一个尾指针（tail），可以将尾部插入和头部插入的时间复杂度优化到 O(1)。
| 特性 | 单链表 | 循环链表 | 双向链表 | 双向循环链表 |
|---|---|---|---|---|
| 尾节点指向 | NULL | 头节点 | NULL | 头节点 |
| 头节点prev | 无 | 无 | NULL | 尾节点 |
| 反向遍历 | 不支持 | 不支持 | 支持 | 支持 |
| 循环访问 | 需重置 | 天然支持 | 需重置 | 天然支持 |
| 空间开销 | 最小 | 最小 | 中等 | 中等 |
| 实现复杂度 | 简单 | 中等 | 中等 | 较复杂 |
CPU时间片轮转调度算法（Round Robin），多个进程循环获得执行时间，公平分配CPU资源。
播放列表循环播放功能，当播放到最后一首歌时自动回到第一首继续播放。
多人游戏中玩家轮流行动，回合结束后自动循环到下一个玩家。
环形缓冲区（Ring Buffer）用于数据流的高效读写，常用于音视频流处理。
经典的数学问题，n个人围成一圈，从第一个人开始报数，数到m的人出局，循环直到剩余一人。
网页轮播图自动循环展示，最后一张图片无缝切换到第一张。