数据结构：循环单链表

循环单链表（Circular Singly Linked List）

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

1. 节点结构

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

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

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

class Node:
    def __init__(self, data):
        self.data = data
        self.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. 总结

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