循环单链表（Circular Singly Linked List）

循环单链表是单链表的一种变体，其特点是链表的尾节点指向头节点，形成一个闭环。这种结构允许在链表中进行无缝的遍历，并且可以从任何节点开始遍历整个链表。循环单链表通常用于需要循环访问元素的场景，如轮询调度、环形缓冲区等。

1. 节点结构

在循环单链表中，每个节点包含两个部分：

• 数据：存储实际的数据元素。

• 后继指针：指向当前节点的下一个节点。

class Node:def __init__(self, data):self.data = dataself.next = None

2. 循环单链表的特点

• 循环结构：链表的尾节点指向头节点，形成一个闭环。

• 单向遍历：由于每个节点只有一个指针，只能向前遍历链表。

• 插入和删除操作高效：在插入或删除节点时，只需要修改相关节点的指针，不需要遍历整个链表，时间复杂度为O(1)，假设你已经定位到操作的位置。

• 内存消耗较低：每个节点只需要存储一个指针，内存消耗比双向链表低。

• 实现复杂度较低：相对于双向链表，实现起来较为简单，但需要注意循环结构的特殊处理。

3. 循环单链表的操作

3.1 插入节点

在循环单链表中插入一个新节点，需要更新相关节点的指针：

• 在头部插入：

  1. 创建新节点。

  2. 如果链表为空，将新节点的next指向自己，并设置头节点为新节点。

  3. 如果链表不为空，设置新节点的next指向原头节点，并更新尾节点的next指向新节点。

  4. 更新头节点为新节点。

• 在尾部插入：

  1. 创建新节点。

  2. 如果链表为空，将新节点的next指向自己，并设置头节点为新节点。

  3. 如果链表不为空，设置新节点的next指向头节点，并更新原尾节点的next指向新节点。

  4. 更新尾节点为新节点。

3.2 删除节点

删除一个节点，需要更新其前驱节点的指针：

• 删除头节点：

  1. 如果链表为空，返回。

  2. 如果链表只有一个节点，释放该节点并设置头节点为空。

  3. 如果链表有多个节点，设置尾节点的next指向头节点的next。

  4. 释放头节点，并更新头节点为原头节点的next。

• 删除尾节点：

  1. 如果链表为空，返回。

  2. 如果链表只有一个节点，释放该节点并设置头节点为空。

  3. 如果链表有多个节点，找到尾节点的前驱节点，设置其next指向头节点。

  4. 释放尾节点，并更新尾节点为原尾节点的前驱节点。

3.3 查找节点

与单链表类似，可以从头节点开始遍历链表，逐个检查节点的数据是否匹配。由于链表是循环的，遍历会在回到头节点时停止。

4. 循环单链表的应用

• 循环缓冲区：用于实现环形缓冲区，数据结构的两端相连，可以实现高效的循环读写。

• 任务调度：在操作系统中，用于实现循环调度算法（如轮询调度）。

• 多人游戏：在多人游戏中，玩家列表可以表示为一个循环单链表，允许玩家在列表中循环移动。

• 循环队列：用于实现循环队列，避免数据搬移，提高效率。

5. 代码示例

以下是一个完整的循环单链表实现，包括插入、删除和遍历操作。

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构
typedef struct Node {int data;            // 数据域struct Node* next;   // 指向下一个节点的指针
} Node;// 定义循环单链表结构
typedef struct CircularLinkedList {Node* head;          // 指向链表的头节点
} CircularLinkedList;// 创建一个新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;return newNode;
}// 初始化循环单链表
void initCircularLinkedList(CircularLinkedList* cll) {cll->head = NULL;
}// 在循环单链表的末尾插入节点
void append(CircularLinkedList* cll, int data) {Node* newNode = createNode(data);if (cll->head == NULL) {// 如果链表为空，新节点成为头节点，并指向自身cll->head = newNode;newNode->next = cll->head;} else {// 遍历到链表的最后一个节点Node* current = cll->head;while (current->next != cll->head) {current = current->next;}// 将新节点插入到末尾，并指向头节点current->next = newNode;newNode->next = cll->head;}
}// 在循环单链表的开头插入节点
void prepend(CircularLinkedList* cll, int data) {Node* newNode = createNode(data);if (cll->head == NULL) {// 如果链表为空，新节点成为头节点，并指向自身cll->head = newNode;newNode->next = cll->head;} else {// 遍历到链表的最后一个节点Node* current = cll->head;while (current->next != cll->head) {current = current->next;}// 将新节点插入到开头，并指向原头节点newNode->next = cll->head;cll->head = newNode;current->next = cll->head;  // 更新最后一个节点的next指针}
}// 删除链表中第一个值为key的节点
void delete(CircularLinkedList* cll, int key) {if (cll->head == NULL) {return;  // 链表为空，直接返回}// 如果要删除的节点是头节点if (cll->head->data == key) {if (cll->head->next == cll->head) {// 链表只有一个节点free(cll->head);cll->head = NULL;} else {// 找到最后一个节点Node* last = cll->head;while (last->next != cll->head) {last = last->next;}// 将最后一个节点的next指向新的头节点Node* temp = cll->head;cll->head = cll->head->next;last->next = cll->head;free(temp);  // 释放原头节点}return;}// 如果要删除的节点不是头节点Node* current = cll->head;Node* prev = NULL;while (current->next != cll->head) {prev = current;current = current->next;if (current->data == key) {// 找到要删除的节点prev->next = current->next;free(current);return;}}
}// 打印循环单链表中的所有节点
void display(CircularLinkedList* cll) {if (cll->head == NULL) {printf("List is empty\n");return;}Node* current = cll->head;do {printf("%d -> ", current->data);current = current->next;} while (current != cll->head);printf(" (回到起点)\n");
}// 主函数
int main() {CircularLinkedList cll;initCircularLinkedList(&cll);// 在链表末尾插入元素append(&cll, 1);append(&cll, 2);append(&cll, 3);display(&cll);  // 输出: 1 -> 2 -> 3 ->  (回到起点)// 在链表开头插入元素prepend(&cll, 0);display(&cll);  // 输出: 0 -> 1 -> 2 -> 3 ->  (回到起点)// 删除元素delete(&cll, 2);display(&cll);  // 输出: 0 -> 1 -> 3 ->  (回到起点)return 0;
}

代码说明：

1. Node 结构体:

    定义了链表中的节点，包含数据（data）和指向下一个节点的指针（next）。

2. CircularLinkedList 结构体:

    定义了循环单链表，包含一个指向头节点的指针（head）。

3. initCircularLinkedList 函数:

    初始化循环单链表，将 head 设为 NULL。

4. append 函数:

    在链表末尾插入一个新节点。如果链表为空，新节点成为头节点并指向自身；否则，遍历到链表的最后一个节点，将其 next 指向新节点，新节点的 next 指向头节点。

5. prepend 函数:

    在链表开头插入一个新节点。如果链表为空，操作同 append；否则，找到最后一个节点，将其 next 指向新节点，新节点的 next 指向原头节点，然后更新头节点为新节点。

6. delete 函数:

    删除链表中第一个值为 key 的节点。如果链表为空，直接返回；如果要删除的是头节点，需要特殊处理；否则，遍历链表找到要删除的节点，修改前一个节点的 next 指针。

7. display 函数:

    打印链表中的所有节点数据。从头节点开始，遍历直到回到头节点，形成一个循环。

输出示例：

1 -> 2 -> 3 ->  (回到起点)
0 -> 1 -> 2 -> 3 ->  (回到起点)
0 -> 1 -> 3 ->  (回到起点)

6. 总结

循环单链表通过维护尾节点指向头节点的指针，形成一个闭环结构，提供了无缝遍历和高效插入删除操作的能力。虽然在内存消耗和实现复杂度上较低，但在需要频繁插入和删除操作，并需要无缝遍历的场景中，循环单链表具有很大的优势。