C语言实现循环单链表：从原理到完整代码与调试指南

2026/8/16 4:43:18

1. 项目概述：为什么我们需要循环单链表？

在数据结构的学习和实际项目开发中，单链表是绕不开的基础。但你是否遇到过这样的场景：需要让一个数据队列“循环”起来，比如实现一个轮询任务调度器、一个循环播放的媒体列表，或者一个固定大小的缓冲区？这时，普通的单链表就显得有些力不从心了，因为它的尾节点指向空（NULL），无法形成一个闭环。循环单链表（Circular Singly Linked List）正是为了解决这类问题而生的。

简单来说，循环单链表就是将普通单链表的最后一个节点的指针，不再指向NULL，而是指向链表的头节点（或头指针指向的节点），从而形成一个环。这个看似微小的改动，却带来了逻辑和操作上的一系列变化与优势。对于初学者，理解循环单链表是深入理解链表家族和复杂数据结构（如循环队列）的关键一步；对于有经验的开发者，它是构建高效、无边界循环逻辑的利器。

接下来，我将结合十多年的编程和教学经验，用C语言手把手带你从零实现一个功能完整的循环单链表。我们不仅会写出每一行代码，更会深入探讨每个设计决策背后的“为什么”，并分享那些在教科书和普通博客里不会写的实操陷阱和调试技巧。无论你是正在备战数据结构考试的学生，还是希望夯实基础的开发者，这篇文章都将为你提供一份可直接“抄作业”的完整指南。

2. 核心思路与结构设计

2.1 循环 vs. 非循环：本质区别与设计考量

在设计之初，我们必须想清楚循环单链表和普通单链表的根本区别，这决定了我们后续所有操作函数的行为。

核心区别在于“终止条件”。在遍历普通单链表时，我们通常使用while(p != NULL)作为循环条件。但在循环链表中，没有任何一个节点的next指针是NULL。如果我们仍然用p != NULL作为条件，程序将陷入死循环。

因此，循环链表的遍历需要一个参照点。常见的做法是，当我们从某个节点（通常是头节点）开始遍历时，以“再次回到这个起点”作为遍历结束的条件。这就引出了第一个关键设计点：我们是否需要一个独立的“头节点”（Dummy Node）？

方案选择与理由：

不带头节点的循环链表：头指针head直接指向第一个有效数据节点。这种结构节省了一个节点的内存，但操作起来需要处理更多边界情况，例如空链表时head为NULL，插入第一个节点和删除最后一个节点的逻辑会比较特殊。
带头节点的循环链表：头指针head指向一个不存储有效数据的“头节点”。这个头节点永远存在，它的next指针指向第一个有效数据节点。当链表为空时，head->next指向头节点自身。这种设计虽然多用了一点内存，但极大简化了操作逻辑，因为空链表和非空链表的许多操作可以统一处理。

对于教学和追求代码的健壮性、清晰度而言，我强烈推荐使用“带头节点”的方案。它用微小的空间代价，换来了逻辑上巨大的简化，尤其是在处理插入、删除和遍历时。下面的完整实现也将基于此方案。

2.2 结构体定义与类型别名

确定了带头节点方案后，我们开始定义链表节点的结构。这一步看似简单，但良好的习惯能让代码更安全、易读。

// 定义链表节点存储的数据类型，方便后续修改 typedef int DataType; // 循环单链表节点结构体 typedef struct CircularNode { DataType data; // 数据域 struct CircularNode *next; // 指针域，指向下一个节点 } CircularNode; // 为整个链表结构定义一个类型别名（可选，但推荐） // 在某些需要封装链表状态（如头指针+长度）的进阶设计中非常有用。 // 此处为简化，我们直接使用 CircularNode* 代表头指针。

为什么使用typedef？

typedef int DataType;：将数据类型抽象出来。如果未来需要将链表存储的数据从int改为float、char*或某个自定义结构体，你只需要修改这一行代码，而不是替换全文几十上百处的int。这是编写可维护性代码的基本素养。
typedef struct CircularNode {...} CircularNode;：这样定义后，我们可以直接使用CircularNode来声明变量，而不必每次都写struct CircularNode，让代码更简洁。

关于头指针：我们将使用CircularNode *head;来声明头指针。初始化后，head指向我们创建的头节点。头节点的data域通常不使用（或可用于存储元信息如链表长度），其next指针在空链表时指向自己。

3. 核心操作实现与代码精讲

从这一节开始，我们将进入具体的代码实现。我会为每个函数提供完整代码，并穿插讲解关键行、易错点和我踩过的坑。

3.1 链表的初始化与销毁

任何资源的使用，都必须有始有终。初始化创建链表，销毁释放所有内存，这是防止内存泄漏的生死线。

3.1.1 初始化链表 (list_init)

初始化函数的目标是创建一个头节点，并让其形成一个自环（自己指向自己），同时返回这个头节点的指针。

/** * @brief 初始化一个空的循环单链表（带头节点） * @return 成功返回头指针，失败返回NULL */ CircularNode* list_init() { // 1. 申请头节点内存 CircularNode *head = (CircularNode*)malloc(sizeof(CircularNode)); if (head == NULL) { perror("malloc failed in list_init"); return NULL; } // 2. 形成自环：这是循环链表初始化的关键一步！ head->next = head; // 注意：是head->next指向head自己，不是NULL // 3. (可选) 可以初始化头节点的数据域，例如存储链表长度 // head->data = 0; return head; }

关键点与避坑指南：

head->next = head;：这是循环链表初始化的灵魂语句。它标志着这个链表是“循环”的。很多初学者在这里会习惯性地写成head->next = NULL，那就退化成普通链表了。
内存申请检查：malloc之后一定要检查返回值是否为NULL。在内存紧张的系统或嵌入式环境中，申请失败是可能发生的。直接使用未检查的指针会导致程序崩溃。
perror的使用：perror(“malloc failed”)会打印出 “malloc failed: 错误原因”，能帮助你在调试时快速定位问题，比单纯printf更专业。

3.1.2 销毁链表 (list_destroy)

销毁链表需要遍历所有节点（包括头节点），逐一释放内存。由于是循环链表，我们需要巧妙地找到遍历的终点。

/** * @brief 彻底销毁循环单链表，释放所有内存 * @param pHead 指向头指针的指针，用于在函数内将外部头指针置NULL */ void list_destroy(CircularNode **pHead) { if (pHead == NULL || *pHead == NULL) { return; // 非法输入或链表已空 } CircularNode *head = *pHead; // 头节点 CircularNode *curr = head->next; // 从第一个有效节点开始 CircularNode *temp = NULL; // 遍历并释放所有有效节点 while (curr != head) { // 终止条件：回到头节点 temp = curr; // 保存当前节点地址 curr = curr->next; // 指针后移 free(temp); // 释放当前节点 } // 最后，释放头节点本身 free(head); // 至关重要：将外部的头指针置为NULL，避免成为野指针 *pHead = NULL; printf("链表已销毁，内存已释放。\n"); }

为什么参数是CircularNode **pHead（二级指针）？这是本函数最容易出错的地方。如果我们传递CircularNode *head（一级指针），在函数内部free(head)后，函数外部的那个head变量本身的值（一个地址）并不会改变，它现在变成了一个野指针（指向已被释放的内存）。后续如果再误用这个指针，会导致未定义行为，通常是段错误（Segmentation Fault）。传递二级指针**pHead，我们就能在函数内部通过*pHead = NULL;修改外部头指针的值，将其安全地置空。这是一个非常重要的C语言编程技巧。

遍历终止条件while (curr != head)：因为我们的链表带头节点且循环，所以当遍历指针curr绕了一圈又指回头节点head时，说明所有有效节点都已处理完毕。这个条件简洁而正确。

3.2 插入操作：头插、尾插与指定位置插入

插入操作是链表的核心，循环链表的插入需要特别注意指针修改的顺序，尤其是在处理头节点和尾节点时。

3.2.1 头插法 (list_insert_head)

在链表的第一个有效节点之前插入新节点。

/** * @brief 在循环单链表头部插入新节点 * @param head 链表头指针 * @param data 要插入的数据 * @return 成功返回1，失败返回0 */ int list_insert_head(CircularNode *head, DataType data) { if (head == NULL) return 0; CircularNode *new_node = (CircularNode*)malloc(sizeof(CircularNode)); if (new_node == NULL) return 0; new_node->data = data; // 关键步骤：顺序很重要！ new_node->next = head->next; // 新节点指向原第一个节点 head->next = new_node; // 头节点指向新节点 return 1; }

指针修改顺序的玄机：一定要先new_node->next = head->next;，再head->next = new_node;。如果顺序反了，你会先丢失原第一个节点的地址，导致链表断裂。这个顺序对于单链表的各种插入操作是通用法则。

3.2.2 尾插法 (list_insert_tail)

在链表末尾插入新节点。循环链表的尾插法比普通链表更高效，因为我们维护了头指针，可以快速找到“尾节点”（即head的前驱节点）。

/** * @brief 在循环单链表尾部插入新节点 * @param head 链表头指针 * @param data 要插入的数据 * @return 成功返回1，失败返回0 */ int list_insert_tail(CircularNode *head, DataType data) { if (head == NULL) return 0; CircularNode *new_node = (CircularNode*)malloc(sizeof(CircularNode)); if (new_node == NULL) return 0; new_node->data = data; // 寻找尾节点：尾节点的next指向头节点head CircularNode *tail = head; while (tail->next != head) { // 注意遍历条件 tail = tail->next; } // 循环结束后，tail即为尾节点 // 插入新节点 new_node->next = head; // 新节点指向头节点，形成环 tail->next = new_node; // 原尾节点指向新节点 return 1; }

寻找尾节点的循环条件：while (tail->next != head)。为什么不是tail->next != NULL？因为这是循环链表。为什么从head开始找？因为头节点是环的一部分，从head开始，它的next指向第一个有效节点。当某个节点的next指向head时，它就是尾节点。

3.2.3 指定位置插入 (list_insert_at)

在链表的第pos个位置（从1开始计数）插入新节点。这需要先找到第pos-1个节点（即前驱节点）。

/** * @brief 在循环单链表指定位置插入新节点 * @param head 链表头指针 * @param pos 要插入的位置（从1开始） * @param data 要插入的数据 * @return 成功返回1，失败返回0 */ int list_insert_at(CircularNode *head, int pos, DataType data) { if (head == NULL || pos < 1) return 0; // 1. 寻找第pos-1个节点 CircularNode *prev = head; // 从头节点开始，因为头节点是第0个“节点” int index = 0; while (prev != NULL && index < pos - 1) { prev = prev->next; index++; // 如果绕了一圈又回到头节点，说明pos超出链表长度+1 if (prev == head) { printf("插入位置%d超出链表范围。\n", pos); return 0; } } // 循环结束后，prev应指向第pos-1个节点 if (prev == NULL) return 0; // 理论上不会发生，防御性编程 // 2. 创建新节点 CircularNode *new_node = (CircularNode*)malloc(sizeof(CircularNode)); if (new_node == NULL) return 0; new_node->data = data; // 3. 执行插入（与头插法逻辑一致） new_node->next = prev->next; prev->next = new_node; return 1; }

位置参数的边界处理：

pos < 1：位置非法。
while循环中的条件if (prev == head)：这是处理pos值过大的关键。在普通链表中，我们检查prev->next != NULL。在循环链表中，如果prev在移动过程中又回到了head，说明我们绕了一圈还没找到第pos-1个位置，意味着pos超出了“链表长度+1”的范围（因为可以在尾部之后插入，即pos = 长度+1）。这个检查防止了无限循环。

3.3 删除操作：按值删与按位置删

删除操作比插入更需要小心，因为涉及到内存释放和指针重连，稍有不慎就会导致内存泄漏或链表断裂。

3.3.1 按值删除 (list_delete_by_value)

删除第一个数据域等于给定值的节点。

/** * @brief 删除循环单链表中第一个值为data的节点 * @param head 链表头指针 * @param data 要删除的数据 * @return 成功删除返回1，未找到返回0 */ int list_delete_by_value(CircularNode *head, DataType data) { if (head == NULL || head->next == head) return 0; // 空链表 CircularNode *prev = head; CircularNode *curr = head->next; // 从第一个有效节点开始 while (curr != head) { // 遍历整个环 if (curr->data == data) { // 找到目标节点 prev->next = curr->next; free(curr); return 1; } prev = curr; curr = curr->next; } // 遍历完整个环都没找到 printf("未找到值为%d的节点。\n", data); return 0; }

双指针技巧：删除节点时，我们需要知道待删除节点（curr）和它的前驱节点（prev）。因为我们需要用prev->next = curr->next;来跳过curr，从而将curr从链表中“摘除”。这是单链表删除的标准模式。

3.3.2 按位置删除 (list_delete_at)

删除第pos个位置的节点。

/** * @brief 删除循环单链表中第pos个位置的节点 * @param head 链表头指针 * @param pos 要删除的位置（从1开始） * @return 成功删除返回1，失败返回0 */ int list_delete_at(CircularNode *head, int pos) { if (head == NULL || pos < 1 || head->next == head) return 0; CircularNode *prev = head; CircularNode *curr = head->next; int index = 1; // curr当前指向第1个节点 while (curr != head && index < pos) { prev = curr; curr = curr->next; index++; } // 循环结束有两种可能： // 1. curr == head: 说明pos超出链表长度 // 2. index == pos: 找到了第pos个节点 if (curr == head) { printf("删除位置%d超出链表范围。\n", pos); return 0; } // 执行删除 prev->next = curr->next; free(curr); return 1; }

遍历的起始点：注意这里curr初始化为head->next（第一个有效节点），index初始化为1。这样设计使得循环逻辑更清晰：while循环的终止条件之一是index < pos，当index增长到等于pos时，curr正好指向要删除的第pos个节点。

3.4 查找、遍历与辅助功能

一个完整的数据结构需要提供信息的查询和展示能力。

3.4.1 查找节点 (list_find)

判断链表中是否存在某个值的节点，并返回其指针（通常返回第一个匹配的）。

/** * @brief 在循环单链表中查找值为data的节点 * @param head 链表头指针 * @param data 要查找的数据 * @return 找到返回节点指针，未找到返回NULL */ CircularNode* list_find(CircularNode *head, DataType data) { if (head == NULL) return NULL; CircularNode *curr = head->next; // 跳过头节点 while (curr != head) { if (curr->data == data) { return curr; } curr = curr->next; } return NULL; // 遍历完未找到 }

3.4.2 获取链表长度 (list_get_length)

计算有效节点的个数。这是一个O(n)的操作，因为需要遍历。

/** * @brief 获取循环单链表的长度（有效节点个数） * @param head 链表头指针 * @return 链表长度，空链表返回0 */ int list_get_length(CircularNode *head) { if (head == NULL) return 0; int length = 0; CircularNode *curr = head->next; while (curr != head) { length++; curr = curr->next; } return length; }

为什么不在头节点里存储长度？这是一个经典的权衡。将长度存储在头节点的data域中，可以使list_get_length变成O(1)的操作。但这意味着每次插入或删除时，都必须同步更新这个长度值，增加了操作的复杂性。对于小型链表或长度查询不频繁的场景，O(n)的遍历是可以接受的。如果性能是关键，可以考虑维护长度信息。

3.4.3 打印链表 (list_print)

以可视化的方式输出链表内容，是调试的利器。

/** * @brief 打印循环单链表的所有元素 * @param head 链表头指针 */ void list_print(CircularNode *head) { if (head == NULL) { printf("链表指针为NULL。\n"); return; } if (head->next == head) { printf("链表为空。\n"); return; } CircularNode *curr = head->next; printf("链表内容 (头节点不显示): "); while (curr != head) { printf("%d -> ", curr->data); curr = curr->next; } printf("(回到头节点)\n"); }

打印的终止条件：同样是curr != head。打印时在最后加上“(回到头节点)”，可以直观地展示链表的循环特性。

4. 完整代码整合与测试用例

将上述所有函数整合到一个.c文件中，并编写一个main函数进行测试，是检验我们代码正确性的最后一步。

4.1 完整源代码 (circular_singly_linked_list.c)

#include <stdio.h> #include <stdlib.h> typedef int DataType; typedef struct CircularNode { DataType data; struct CircularNode *next; } CircularNode; // 函数声明 CircularNode* list_init(); void list_destroy(CircularNode **pHead); int list_insert_head(CircularNode *head, DataType data); int list_insert_tail(CircularNode *head, DataType data); int list_insert_at(CircularNode *head, int pos, DataType data); int list_delete_by_value(CircularNode *head, DataType data); int list_delete_at(CircularNode *head, int pos); CircularNode* list_find(CircularNode *head, DataType data); int list_get_length(CircularNode *head); void list_print(CircularNode *head); // 各函数实现（将前面3.1至3.4节的代码依次粘贴在此处） // ... (为节省篇幅，此处省略具体实现，请参照前文) ... int main() { printf("=== 循环单链表测试程序 ===\n"); // 1. 初始化 CircularNode *head = list_init(); if (head == NULL) { printf("链表初始化失败！\n"); return -1; } printf("初始化成功。\n"); list_print(head); // 2. 测试尾插法 printf("\n--- 测试尾插法插入 1, 2, 3 ---\n"); list_insert_tail(head, 1); list_insert_tail(head, 2); list_insert_tail(head, 3); list_print(head); printf("当前链表长度: %d\n", list_get_length(head)); // 3. 测试头插法 printf("\n--- 测试头插法插入 0 ---\n"); list_insert_head(head, 0); list_print(head); // 4. 测试指定位置插入 printf("\n--- 在位置3插入 99 ---\n"); list_insert_at(head, 3, 99); list_print(head); // 5. 测试查找 printf("\n--- 查找值为2的节点 ---\n"); CircularNode *found = list_find(head, 2); if (found) { printf("找到节点，其值为: %d\n", found->data); } else { printf("未找到节点。\n"); } // 6. 测试按值删除 printf("\n--- 删除值为99的节点 ---\n"); if (list_delete_by_value(head, 99)) { printf("删除成功。\n"); } else { printf("删除失败（未找到）。\n"); } list_print(head); // 7. 测试按位置删除 printf("\n--- 删除第2个位置的节点 ---\n"); if (list_delete_at(head, 2)) { printf("删除成功。\n"); } else { printf("删除失败（位置无效）。\n"); } list_print(head); // 8. 测试边界：删除头元素、尾元素 printf("\n--- 测试边界删除 ---\n"); printf("删除第一个节点（值0）: "); list_delete_by_value(head, 0); list_print(head); printf("删除最后一个节点（值3）: "); // 先获取长度，再删除最后一个位置 int len = list_get_length(head); list_delete_at(head, len); list_print(head); // 9. 最终销毁 printf("\n--- 销毁链表 ---\n"); list_destroy(&head); // 注意传递二级指针 if (head == NULL) { printf("头指针已置空，销毁成功。\n"); } return 0; }

4.2 编译与运行测试

在Linux或Mac的终端，或者Windows的对应开发环境中，使用gcc编译并运行：

gcc -o circular_list circular_singly_linked_list.c ./circular_list

你应该能看到类似以下的输出，清晰地展示了每个操作后链表的状态变化：

=== 循环单链表测试程序 === 初始化成功。 链表为空。 --- 测试尾插法插入 1, 2, 3 --- 链表内容 (头节点不显示): 1 -> 2 -> 3 -> (回到头节点) 当前链表长度: 3 --- 测试头插法插入 0 --- 链表内容 (头节点不显示): 0 -> 1 -> 2 -> 3 -> (回到头节点) --- 在位置3插入 99 --- 链表内容 (头节点不显示): 0 -> 1 -> 99 -> 2 -> 3 -> (回到头节点) --- 查找值为2的节点 --- 找到节点，其值为: 2 --- 删除值为99的节点 --- 删除成功。 链表内容 (头节点不显示): 0 -> 1 -> 2 -> 3 -> (回到头节点) --- 删除第2个位置的节点 --- 删除成功。 链表内容 (头节点不显示): 0 -> 2 -> 3 -> (回到头节点) --- 测试边界删除 --- 删除第一个节点（值0）: 链表内容 (头节点不显示): 2 -> 3 -> (回到头节点) 删除最后一个节点（值3）: 链表内容 (头节点不显示): 2 -> (回到头节点) --- 销毁链表 --- 链表已销毁，内存已释放。 头指针已置空，销毁成功。

5. 常见问题、调试技巧与进阶思考

即使代码写完了，真正的挑战往往在调试和后续使用中。这里分享一些我踩过的坑和解决问题的思路。

5.1 经典错误与排查技巧

死循环：这是循环链表最容易出现的问题。症状是程序卡住，CPU占用率100%。
- 原因：遍历的终止条件写错了，例如在list_print或list_destroy中写成了while(curr != NULL)。
- 调试：在遍历循环内加入打印语句，输出当前节点的地址和数据，观察它是否在绕圈。确保你的终止条件是curr != head（对于带头节点的遍历）或基于计数器。
- 预防：在编写任何遍历循环链表的函数时，第一件事就是反复确认终止条件。
内存泄漏：程序运行后，内存使用量持续增长。
- 原因：malloc了节点但没有free，尤其是在删除节点或销毁链表时漏掉了。
- 工具：在Linux下可以使用valgrind工具检测。编译时加上-g选项，然后运行valgrind --leak-check=full ./circular_list。它会详细报告内存泄漏的位置。
- 预防：确保每个malloc都有对应的free。list_destroy函数必须被调用，且要验证外部头指针是否被正确置空。
段错误 (Segmentation Fault)：程序崩溃。
- 原因：访问了非法内存。常见情况：对NULL指针解引用（如head->next而head为NULL）；使用了已被free的指针（野指针）。
- 调试：使用gdb调试器。编译时加-g，用gdb ./circular_list启动，run运行，崩溃后用bt查看调用栈，定位出错行。
- 预防：在所有函数入口检查指针参数是否为NULL（防御性编程）。在free(p)之后，立即将p置为NULL（虽然函数内的局部变量作用域结束，但这是个好习惯）。
逻辑错误：插入/删除位置不对。
- 原因：位置pos的处理有误，特别是pos为1（第一个有效节点）或等于链表长度（最后一个节点）的边界情况。
- 调试：在list_insert_at和list_delete_at函数中，在关键步骤前后打印prev和curr指针的值或它们指向的数据，观察指针移动过程。
- 预防：用第4节的测试用例充分测试边界情况：空链表插入、只有一个节点时删除、在头部插入、在尾部插入、删除头节点、删除尾节点。

5.2 循环单链表的应用场景与变体

理解了基础实现，我们可以看看它能用在哪里，以及如何扩展：

轮询调度：操作系统或网络框架中的轮询任务队列。遍历链表执行任务，执行完一个就移到末尾（curr = curr->next即可自然到达下一个），实现公平调度。
循环缓冲区：固定大小的缓冲区。可以用循环链表模拟，当缓冲区满时，新的数据覆盖最旧的数据（头节点后的第一个节点）。
约瑟夫环问题：经典的算法问题，N个人围成一圈，从第K个开始报数，报到M的人出列，直到所有人出列。用循环链表模拟是再自然不过的选择。
变体：仅设尾指针：有时我们只维护一个尾指针rear。此时，rear->next就是头节点，插入到链表头部和尾部都非常快（O(1)）。但查找、指定位置插入等操作会稍微复杂一些。你可以尝试实现这个变体，作为练习。

5.3 给初学者的最后建议

数据结构的学习，动手实现一遍比看十遍都强。不要满足于看懂这篇文章的代码。请你：