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* 代表头指针。为什么使用typedeftypedef 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-checkfull ./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 给初学者的最后建议数据结构的学习动手实现一遍比看十遍都强。不要满足于看懂这篇文章的代码。请你在电脑上亲自敲一遍所有代码。故意制造一些错误比如把while(curr ! head)改成while(curr ! NULL)然后观察现象并尝试用调试工具定位问题。尝试实现“仅设尾指针”的循环链表变体。用这个循环链表去解决“约瑟夫环”问题。当你能够不参考任何资料在白板上清晰地画出节点和指针的变化并写出正确的代码时你对链表的理解就真正过关了。循环单链表是更复杂的双向链表、循环队列等结构的基础打好这个基础后续的学习会顺畅很多。编程的路上每一个扎实的脚印都算数。