循环链表（Circular Linked List）是一种特殊的链表形式，它的最后一个节点的指针不是指向 NULL，而是指向链表的头节点，这样链表形成一个环，可以从任意节点开始进行遍历。在循环链表中，链表的头节点和尾节点通过指针连接，因此可以循环地访问链表中的所有节点。
循环链表既可以是 单向循环链表，也可以是 双向循环链表，但单向循环链表更常见。
循环链表的概念
- 节点 (Node)：链表的基本单元，包含数据和指针。
- 头节点 (Head)：链表的第一个节点。
- 尾节点 (Tail)：链表的最后一个节点，它的指针指向头节点，而不是
NULL。 - 循环特性：尾节点的指针指向头节点，使链表形成一个循环。
- 单向循环链表：节点只包含一个指向下一个节点的指针。
- 双向循环链表：节点包含指向前一个和下一个节点的两个指针。
循环链表的基本操作
- 创建链表：初始化一个空的循环链表。
- 插入节点：在链表头部、尾部或指定位置插入节点。
- 删除节点：删除指定的节点。
- 遍历链表：由于链表是循环的，遍历过程中需要注意避免无限循环。
- 释放链表：释放链表中动态分配的所有节点内存。
单向循环链表的结构定义
#include <stdio.h>
#include <stdlib.h>
// 定义单向循环链表的节点结构
struct Node {
int data; // 数据域
struct Node* next; // 指针域，指向下一个节点
};基本操作实现
- 创建新节点
// 创建新节点
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // 分配内存
if (!newNode) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = data; // 设置节点数据
newNode->next = newNode; // 初始化时，节点指向自身形成循环
return newNode;
}- 插入节点到链表头部
// 插入节点到链表头部
void insertAtHead(struct Node** head, int data) {
struct Node* newNode = createNode(data); // 创建新节点
if (*head == NULL) { // 如果链表为空
*head = newNode; // 新节点就是头节点
newNode->next = newNode; // 新节点指向自身，形成循环
return;
}
struct Node* temp = *head;
// 找到链表的最后一个节点
while (temp->next != *head) {
temp = temp->next;
}
// 插入新节点到头部
temp->next = newNode; // 尾节点指向新节点
newNode->next = *head; // 新节点指向原头节点
*head = newNode; // 更新头节点
}- 在链表尾部插入节点
// 插入节点到链表尾部
void insertAtTail(struct Node** head, int data) {
struct Node* newNode = createNode(data); // 创建新节点
if (*head == NULL) { // 如果链表为空
*head = newNode; // 新节点就是头节点
newNode->next = newNode; // 新节点指向自身，形成循环
} else {
struct Node* temp = *head;
// 找到链表的最后一个节点
while (temp->next != *head) {
temp = temp->next;
}
// 插入新节点到尾部
temp->next = newNode; // 尾节点指向新节点
newNode->next = *head; // 新节点指向头节点，形成循环
}
}- 删除节点
// 删除值为 data 的节点
void deleteNode(struct Node** head, int data) {
if (*head == NULL) return; // 空链表
struct Node* temp = *head;
struct Node* prev = NULL;
// 如果头节点就是要删除的节点
if ((*head)->data == data) {
if ((*head)->next == *head) { // 链表只有一个节点
free(*head);
*head = NULL;
return;
}
// 找到链表的最后一个节点
while (temp->next != *head) {
temp = temp->next;
}
temp->next = (*head)->next; // 最后一个节点指向头节点的下一个节点
free(*head); // 释放原头节点
*head = temp->next; // 更新头节点
return;
}
// 找到要删除的节点
prev = *head;
temp = (*head)->next;
while (temp != *head && temp->data != data) {
prev = temp;
temp = temp->next;
}
// 如果找到要删除的节点
if (temp->data == data) {
prev->next = temp->next;
free(temp);
}
}- 遍历链表
// 遍历链表并打印每个节点的数据
void printList(struct Node* head) {
if (head == NULL) {
printf("链表为空\n");
return;
}
struct Node* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head); // 循环直到再次回到头节点
printf("(回到头节点)\n");
}- 释放链表
// 释放链表的所有节点
void freeList(struct Node** head) {
if (*head == NULL) return;
struct Node* current = *head;
struct Node* nextNode;
do {
nextNode = current->next; // 保存下一个节点
free(current); // 释放当前节点
current = nextNode; // 移动到下一个节点
} while (current != *head); // 循环直到再次回到头节点
*head = NULL; // 头指针置为 NULL，表示链表已空
}使用示例
int main() {
struct Node* head = NULL; // 初始化空链表
// 插入数据
insertAtHead(&head, 3);
insertAtHead(&head, 2);
insertAtHead(&head, 1);
insertAtTail(&head, 4);
insertAtTail(&head, 5);
// 打印链表
printf("循环链表内容: ");
printList(head);
// 删除节点
deleteNode(&head, 3);
printf("删除节点3后的链表: ");
printList(head);
// 释放链表
freeList(&head);
return 0;
}运行结果
循环链表内容: 1 -> 2 -> 3 -> 4 -> 5 -> (回到头节点)
删除节点3后的链表: 1 -> 2 -> 4 -> 5 -> (回到头节点)总结
- 循环链表 与普通链表的主要区别在于其循环特性：尾节点指向头节点，形成一个循环结构。
- 这种结构允许从任意节点开始遍历，并且能够简化某些需要循环操作的算法。
- 与单向链表相比，循环链表在处理链尾时更加方便（不需要额外处理尾节点的
next指针为NULL的情况）。