C 语言实现循环链表深入讲解

循环链表的概念与特性

什么是循环链表

循环链表（Circular Linked List）是一种特殊的链表结构，与普通链表不同的是，其最后一个节点的指针不再指向 NULL，而是指向链表的头节点，从而形成一个环形结构。这种结构使得链表中的每个节点都有后继节点，在遍历链表时不会遇到 NULL 而终止，而是可以无限循环遍历下去。

在 C 语言中，我们通过结构体来定义链表节点，普通链表节点的定义如下：

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

对于循环链表，节点定义形式相同，但在构建和操作上有所区别。

循环链表的特性

循环遍历：由于链表形成闭环，从任意节点出发都可以遍历整个链表。这在一些需要重复执行某些操作，且操作对象为链表中所有元素的场景中非常有用。例如，实现一个循环播放音乐列表的功能，音乐列表可以用循环链表表示，每次播放完一首歌曲后，可以无缝切换到下一首，直到用户停止播放。
无明显的尾节点：普通链表通过尾节点的 next 指针为 NULL 来标识链表的结束，而循环链表没有真正意义上的尾节点。这就需要在遍历和操作链表时采用不同的判断条件。例如，在遍历循环链表时，不能以 node->next == NULL 作为结束条件，而通常以回到起始节点作为结束条件。
节点删除与插入的特殊处理：在循环链表中删除或插入节点时，需要特别注意维护链表的循环特性。例如，当删除链表中唯一的节点时，不仅要将该节点内存释放，还要将链表的头指针设置为 NULL（如果允许空链表的话）；当在链表头部插入新节点时，除了更新新节点和原头节点的指针，还需要确保尾节点的 next 指针指向新的头节点。

C 语言实现循环链表的基本操作

创建循环链表节点

首先，我们需要定义循环链表节点的结构体，并编写一个函数来创建新节点。

#include <stdio.h>
#include <stdlib.h>

// 定义循环链表节点结构体
struct Node {
    int data;
    struct Node* next;
};

// 创建新节点的函数
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = newNode; // 新节点初始时指向自身，形成一个单节点的循环链表
    return newNode;
}

在 createNode 函数中，我们为新节点分配内存，设置节点的数据值，并让新节点的 next 指针指向自身。这样就创建了一个独立的循环链表，虽然此时链表只有一个节点。

插入节点到循环链表

在头部插入节点：在头部插入节点时，我们需要更新新节点的 next 指针指向原头节点，同时更新尾节点（因为循环链表可能只有一个节点，此时该节点既是头节点也是尾节点）的 next 指针指向新的头节点。

// 在头部插入节点的函数
struct Node* insertAtHead(struct Node* head, int value) {
    struct Node* newNode = createNode(value);
    if (head == NULL) {
        return newNode;
    }
    struct Node* tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    newNode->next = head;
    tail->next = newNode;
    return newNode;
}

在 insertAtHead 函数中，首先创建新节点。如果链表为空，则直接返回新节点。否则，找到链表的尾节点，将新节点插入到头部，并更新尾节点的 next 指针。

在尾部插入节点：在尾部插入节点时，需要遍历到链表的尾节点，然后将尾节点的 next 指针指向新节点，新节点的 next 指针指向头节点。

// 在尾部插入节点的函数
struct Node* insertAtTail(struct Node* head, int value) {
    struct Node* newNode = createNode(value);
    if (head == NULL) {
        return newNode;
    }
    struct Node* tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    tail->next = newNode;
    newNode->next = head;
    return head;
}

在 insertAtTail 函数中，同样先创建新节点。若链表为空，返回新节点。否则，找到尾节点，将新节点插入到尾部，并更新新节点的 next 指针指向头节点。

删除循环链表中的节点

删除头部节点：删除头部节点时，需要找到尾节点，将尾节点的 next 指针指向原头节点的下一个节点，然后释放原头节点的内存。

// 删除头部节点的函数
struct Node* deleteAtHead(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }
    if (head->next == head) {
        free(head);
        return NULL;
    }
    struct Node* tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    struct Node* temp = head;
    head = head->next;
    tail->next = head;
    free(temp);
    return head;
}

在 deleteAtHead 函数中，首先判断链表是否为空或只有一个节点。若只有一个节点，释放该节点内存并返回 NULL。否则，找到尾节点，更新尾节点的 next 指针，释放原头节点内存，返回新的头节点。

删除尾部节点：删除尾部节点时，需要遍历到尾节点的前一个节点，将其 next 指针指向头节点，然后释放尾节点的内存。

// 删除尾部节点的函数
struct Node* deleteAtTail(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }
    if (head->next == head) {
        free(head);
        return NULL;
    }
    struct Node* tail = head;
    struct Node* prev = NULL;
    while (tail->next != head) {
        prev = tail;
        tail = tail->next;
    }
    prev->next = head;
    free(tail);
    return head;
}

在 deleteAtTail 函数中，类似地先判断链表是否为空或只有一个节点。若链表有多个节点，遍历找到尾节点及其前一个节点，更新前一个节点的 next 指针，释放尾节点内存，返回头节点。

遍历循环链表

遍历循环链表需要注意结束条件，不能以 node->next == NULL 作为结束条件，而是要判断是否回到起始节点。

// 遍历循环链表的函数
void traverse(struct Node* head) {
    if (head == NULL) {
        return;
    }
    struct Node* current = head;
    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != head);
    printf("\n");
}

在 traverse 函数中，使用 do - while 循环，确保至少输出头节点的数据，然后不断移动到下一个节点，直到再次回到头节点，完成整个链表的遍历。

循环链表的应用场景

操作系统中的进程调度

在操作系统的进程调度中，循环链表可以用来表示进程队列。每个进程可以作为链表中的一个节点，包含进程的相关信息，如进程 ID、优先级、执行状态等。调度程序可以按照一定的算法（如轮转调度算法）从循环链表中依次选取进程执行。当一个进程执行完一个时间片后，将其重新插入到链表尾部，等待下一次调度。这样，循环链表可以方便地实现进程的循环调度，保证每个进程都有机会得到执行。

约瑟夫环问题

约瑟夫环问题是一个经典的数学问题，也可以用循环链表来解决。假设有 n 个人围成一圈，从第 k 个人开始报数，数到 m 的人出圈，然后从出圈的下一个人开始重新报数，如此重复，直到所有人都出圈。我们可以用循环链表来模拟这个过程，链表节点表示每个人，节点的数据域可以存储人的编号。通过不断删除满足条件的节点，直到链表为空，就可以得到出圈的顺序。

下面是用 C 语言解决约瑟夫环问题的代码示例：

#include <stdio.h>
#include <stdlib.h>

// 定义循环链表节点结构体
struct Node {
    int data;
    struct Node* next;
};

// 创建新节点的函数
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = newNode;
    return newNode;
}

// 创建循环链表的函数
struct Node* createCircularList(int n) {
    struct Node* head = createNode(1);
    struct Node* current = head;
    for (int i = 2; i <= n; i++) {
        current->next = createNode(i);
        current = current->next;
    }
    current->next = head;
    return head;
}

// 解决约瑟夫环问题的函数
void josephusProblem(int n, int k, int m) {
    struct Node* head = createCircularList(n);
    struct Node* prev = NULL;
    struct Node* current = head;

    // 移动到第 k 个人
    for (int i = 1; i < k; i++) {
        prev = current;
        current = current->next;
    }

    while (current->next != current) {
        // 数到 m - 1
        for (int i = 1; i < m - 1; i++) {
            current = current->next;
        }
        printf("%d ", current->next->data);
        struct Node* temp = current->next;
        current->next = temp->next;
        free(temp);
    }
    printf("%d\n", current->data);
    free(current);
}

int main() {
    int n = 7, k = 1, m = 3;
    printf("约瑟夫环出圈顺序: ");
    josephusProblem(n, k, m);
    return 0;
}

在上述代码中，createCircularList 函数创建一个包含 n 个节点的循环链表。josephusProblem 函数按照约瑟夫环的规则，从第 k 个人开始，数到 m 的人出圈，直到所有人都出圈，并输出出圈顺序。

循环缓冲区

在数据处理中，循环缓冲区（Circular Buffer）是一种常用的数据结构，用于临时存储数据。它可以用循环链表来实现，链表节点存储数据。循环缓冲区常用于数据的生产者 - 消费者模型中，生产者将数据写入循环缓冲区，消费者从循环缓冲区读取数据。由于链表的循环特性，缓冲区可以循环使用，避免了频繁的内存分配和释放。

例如，在音频处理中，音频数据可以不断地写入循环缓冲区，音频播放模块从循环缓冲区读取数据进行播放。当缓冲区满时，新的数据会覆盖旧的数据，保证音频播放的连续性。

循环链表与其他链表结构的比较

与单链表的比较

遍历方式：单链表通过 node->next == NULL 来判断遍历结束，而循环链表通过回到起始节点来判断遍历结束。循环链表的遍历可以无限循环，适用于需要重复处理链表元素的场景；而单链表遍历到尾节点后就结束，更适合一次性处理链表元素的场景。
插入和删除操作：在单链表头部插入节点相对简单，只需更新新节点和头节点的指针；而在循环链表头部插入节点，除了更新新节点和头节点指针，还需要更新尾节点的指针。在删除操作上，单链表删除尾节点时需要遍历到尾节点的前一个节点；而循环链表删除尾节点时，同样需要找到尾节点的前一个节点，但由于链表的循环特性，处理方式略有不同。
应用场景：单链表常用于实现栈、队列等数据结构，以及一些简单的线性数据存储和处理；而循环链表更适合需要循环遍历、循环操作数据的场景，如前面提到的进程调度、约瑟夫环问题等。

与双向链表的比较

指针结构：双向链表每个节点有两个指针，一个指向前一个节点，一个指向后一个节点；而循环链表每个节点只有一个指针，指向后继节点。双向链表的双向指针结构使得它在遍历和操作节点时更加灵活，可以双向遍历链表；而循环链表只能单向循环遍历。
插入和删除操作：双向链表在插入和删除节点时，可以更方便地找到前驱节点，操作相对简单；而循环链表在插入和删除节点时，需要特别注意维护链表的循环特性。例如，在双向链表中删除一个节点，只需更新前驱节点和后继节点的指针；而在循环链表中删除节点，除了更新相邻节点指针，还需要考虑链表的循环结构。
内存开销：由于双向链表每个节点需要额外存储一个指向前驱节点的指针，因此内存开销比循环链表大。在对内存空间要求较高的场景中，循环链表可能更具优势。

循环链表的性能分析

时间复杂度

插入操作：在循环链表头部插入节点的时间复杂度为 O(n)，因为需要遍历找到尾节点来更新其指针；在尾部插入节点的时间复杂度也为 O(n)，同样需要遍历找到尾节点。
删除操作：删除头部节点的时间复杂度为 O(n)，需要遍历找到尾节点；删除尾部节点的时间复杂度也为 O(n)，需要遍历找到尾节点的前一个节点。
遍历操作：遍历循环链表的时间复杂度为 O(n)，因为需要访问链表中的每个节点。

空间复杂度

循环链表的空间复杂度为 O(n)，其中 n 是链表中节点的数量。每个节点需要存储数据和一个指针，因此总的空间开销与节点数量成正比。

在实际应用中，需要根据具体的需求和场景来选择合适的数据结构。如果需要循环遍历、循环操作数据，并且对内存空间要求不是特别苛刻，循环链表是一个不错的选择；如果需要频繁地插入和删除节点，并且需要双向遍历链表，双向链表可能更合适；如果只是简单的线性数据存储和处理，单链表可能就足够了。

通过深入理解循环链表的概念、特性、基本操作、应用场景、与其他链表结构的比较以及性能分析，我们可以在实际编程中更加灵活地运用循环链表来解决各种问题，提高程序的效率和可维护性。