C语言实现循环单链表：从原理到实践，掌握环形数据结构

1. 项目概述：循环单链表，一个被低估的“环形”数据结构

在初学数据结构时，我们接触的第一个动态结构往往是单链表。它解决了数组需要预先分配连续空间、插入删除效率低的问题。但你是否想过，单链表有一个“天生”的缺陷？当你遍历到链表末尾，想快速回到链表头部时，只能从头再来，或者依赖一个额外的头指针。这在某些需要“循环”或“轮转”处理的场景下，就显得不那么优雅和高效了。今天要聊的循环单链表，就是为解决这个问题而生的。它把单链表的“线性”首尾相连，形成一个环，让遍历操作可以无缝地循环往复。

简单来说，循环单链表就是最后一个节点的指针域不再指向NULL，而是指向了头节点（或第一个数据节点），从而形成一个闭环。这个看似微小的改动，却带来了应用逻辑上的巨大便利。比如，在操作系统的进程时间片轮转调度、多人游戏的玩家回合制循环、数据缓冲区的循环利用（环形缓冲区）等场景中，循环单链表都是非常自然且高效的数据模型。对于C语言学习者而言，亲手实现一个循环单链表，不仅能巩固指针和动态内存管理的核心知识，更能深刻理解“结构决定用途”的设计思想。接下来，我将以一个从业者的视角，带你从零开始，用C语言构建一个功能完整、鲁棒性强的循环单链表，并分享那些教科书上不会写的“踩坑”心得。

2. 核心设计：如何为“循环”而生

实现一个数据结构，首先要明确它的“形态”和“规则”。循环单链表的核心设计决策，主要集中在如何表示这个“环”，以及如何处理边界情况，这直接决定了后续所有操作的复杂度和正确性。

2.1 节点结构定义：万变不离其宗

链表的基石是节点。循环单链表的节点结构与普通单链表完全一致，这体现了数据结构设计的继承性。每个节点需要包含两部分：数据域和指针域。

typedef int ElemType; // 为方便起见，假设数据元素为整型，实际可替换为任意复杂类型 typedef struct LNode { ElemType data; // 数据域，存放节点数据 struct LNode *next; // 指针域，指向下一个节点 } LNode, *LinkList;

这里用了typedef定义了两种类型：LNode强调这是一个节点结构体，LinkList强调这是一个指向节点的指针，通常用作链表的头指针（或尾指针）。这种定义在后续的函数参数传递时，能让代码意图更清晰：LinkList L表示“一个链表”，LNode *p表示“一个指向节点的指针”。

注意：数据域ElemType应根据实际需求定义。如果是学生信息，可能是一个包含学号、姓名、成绩的结构体。这里用int是为了简化示例，聚焦于链表结构本身的操作。

2.2 循环的基石：尾指针 vs 头指针

这是实现循环单链表的第一个关键抉择。普通单链表通常用一个头指针指向第一个节点。在循环单链表中，我们有两种主流方案：

1. 带头节点的循环单链表（使用头指针）：引入一个不存储实际数据的“头节点”，其next指向第一个数据节点，最后一个数据节点的next指向这个头节点。头指针L始终指向这个头节点。

   • 优点：统一了空表和非空表的操作。无论链表是否为空，头节点的next域都指向某个节点（空表时指向自己），这使得插入、删除第一个数据节点的操作与操作中间节点在代码逻辑上完全一致，简化了判断。
   • 缺点：多占用了一个节点的内存。要找到链表尾部，需要遍历。

2. 不带头节点的循环单链表（使用尾指针）：这是更符合“循环”直觉、也往往更高效的方案。我们维护一个尾指针rear，它直接指向链表中的最后一个节点。那么，最后一个节点的next就指向第一个节点，而rear->next就是第一个节点。

   • 优点：
     • 插入到链表尾部的操作是O(1)时间复杂度，因为直接修改rear及其next即可。
     • 合并两个循环链表异常高效，只需交换几个指针，也是O(1)时间。
     • 逻辑直观，rear->next就是头，形成了一个完美的环。
   • 缺点：空表的表示和操作需要特殊处理（rear为NULL），且删除第一个节点时，需要更新rear->next，稍微麻烦一点。

我的选择与理由：在大多数需要循环特性的实际场景中（如缓冲区、轮询队列），频繁的尾部插入和链表合并操作更为常见。因此，我将采用“不带头节点、使用尾指针”的方案来实现。这不仅性能更优，也能让我们更纯粹地体会“循环”的精髓。空表状态用一个NULL指针表示，我们在初始化、插入和删除时仔细处理这个边界条件即可。

2.3 核心操作的设计思路

基于尾指针的设计，我们来规划核心操作：

• 初始化：创建一个空链表，即*rear = NULL。
• 创建（尾插法）：依次在尾部插入新节点，并始终更新rear指向新的尾节点。注意处理第一个节点插入时的成环操作。
• 遍历：从rear->next（即第一个节点）开始，依次访问，直到再次回到这个节点为止。需要小心处理空表情况。
• 插入：
  • 头部插入：新节点插入在rear->next之前，并可能需要更新rear->next（如果链表原为空，则还需更新rear）。
  • 尾部插入：新节点插入在rear之后，并更新rear为新节点。这是最方便的操作。
  • 中间插入：先找到前驱节点，然后修改指针。
• 删除：需要找到待删除节点的前驱节点。特别注意删除第一个或最后一个节点时，对rear指针的影响。
• 查找：遍历环，比对数据。
• 销毁：依次释放所有节点内存，最后将rear置为NULL。遍历时需注意避免无限循环。

3. 核心细节与避坑指南

纸上得来终觉浅，绝知此事要躬行。理论设计清晰后，真正的挑战在于代码实现中的各种细节和边界条件。下面这些“坑”，是我在无数次调试中总结出来的。

3.1 空链表的判断与操作统一

这是使用尾指针方案最需要小心的地方。一个空链表意味着rear == NULL。此时：

• rear->next是非法访问，会导致程序崩溃。
• 插入第一个节点时，这个节点既是头也是尾，其next要指向自己，同时rear要指向它。

解决方案：在所有涉及rear->next的操作前，必须先判断rear是否为NULL。例如，在遍历函数中：

void TraverseList(LinkList rear) { if (rear == NULL) { printf("The list is empty.\n"); return; } LNode *p = rear->next; // 从第一个节点开始 do { printf("%d ", p->data); p = p->next; } while (p != rear->next); // 回到起点则结束 printf("\n"); }

这里使用了do...while循环，确保即使链表只有一个节点（此时p == rear），也能正确打印一次。如果用while循环，就需要更复杂的初始条件判断。

3.2 指针修改的顺序：不可逆转的法则

在链表操作中，修改指针的顺序至关重要，一旦顺序错误，就会丢失节点引用，导致内存泄漏或链表断裂。有一个基本原则：先搭新桥，再拆旧桥。

以在节点p之后插入新节点s为例：

1. s->next = p->next;// 新节点s指向p原来的后继
2. p->next = s;// 节点p指向新节点s绝对不能颠倒！如果先执行p->next = s，那么p原来的后继节点就丢失了，再也找不回来。

在循环链表中，如果p是尾节点rear，插入后还需要更新rear = s。这个更新操作放在两步指针修改之后即可。

3.3 尾指针的维护：谁是真正的“尾”

在删除操作中，维护尾指针rear的正确性是难点。考虑两种情况：

1. 删除尾节点：如果删除的节点恰好是rear指向的节点，那么在删除它之后，必须将rear更新为它的前驱节点。这就要求我们在删除前必须找到前驱节点。
2. 链表只剩一个节点：这是上面情况的特例。删除这个唯一的节点后，链表变为空，rear必须被设为NULL。

因此，一个健壮的删除函数，通常需要先遍历找到待删除节点的前驱节点pre。即使你知道要删除的节点指针p，你也需要pre来修改链表结构，并判断p是否是尾节点。

// 假设已知要删除节点p，我们需要找到它的前驱pre LNode *pre = rear; while (pre->next != p) { // 在循环链表中寻找p的前驱 pre = pre->next; if (pre == rear && pre->next != p) { // 绕了一圈没找到，说明p不在链表中 // 错误处理 return; } } // 执行删除 pre->next = p->next; // 维护rear if (p == rear) { if (pre == rear) { // 链表只有一个节点 rear = NULL; } else { rear = pre; // 更新rear为新的尾节点 } } free(p);

3.4 遍历的终止条件：防止无限循环

在普通单链表中，遍历以p != NULL为条件。在循环单链表中，遍历以p != 起始点为条件。这带来了一个微妙的问题：如何确定起始点？对于带头指针的链表，起始点是头节点或第一个数据节点。对于我们的尾指针链表，起始点是rear->next。

关键技巧：在遍历开始前，用一个变量start保存起始点的地址，然后移动指针p，当p再次回到start时停止。一定要使用do...while或确保初始p被正确设置，否则可能一次都不执行（对于while循环）或无法处理单节点情况。

4. 完整代码实现与逐行解析

下面，我将给出一个采用尾指针rear、不带头节点的循环单链表的完整C语言实现。每一部分都配有详细注释和逻辑解释。

#include <stdio.h> #include <stdlib.h> // 定义节点类型和链表类型 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; // LinkList 是指向LNode的指针，此处我们用它表示尾指针 // 1. 初始化链表（传入尾指针的地址） void InitList(LinkList *rear) { *rear = NULL; // 空链表，尾指针为NULL } // 2. 采用尾插法创建循环单链表 void CreateList_R(LinkList *rear, int n) { printf("Please enter %d elements: ", n); for (int i = 0; i < n; i++) { LNode *s = (LNode *)malloc(sizeof(LNode)); if (!s) { perror("Memory allocation failed"); exit(EXIT_FAILURE); } scanf("%d", &(s->data)); if (*rear == NULL) { // 链表为空，插入第一个节点 s->next = s; // 自己指向自己，形成环 *rear = s; // 尾指针指向这唯一的节点 } else { // 链表非空，插入到尾部 s->next = (*rear)->next; // 新节点指向原头节点 (*rear)->next = s; // 原尾节点指向新节点 *rear = s; // 更新尾指针为新节点 } } } // 3. 遍历打印链表 void TraverseList(LinkList rear) { if (rear == NULL) { printf("The list is empty.\n"); return; } LNode *p = rear->next; // p指向第一个节点 printf("List elements: "); do { printf("%d ", p->data); p = p->next; } while (p != rear->next); // 再次回到起点时结束 printf("\n"); } // 4. 在链表头部插入元素 void InsertAtHead(LinkList *rear, ElemType e) { LNode *s = (LNode *)malloc(sizeof(LNode)); if (!s) exit(EXIT_FAILURE); s->data = e; if (*rear == NULL) { // 空表插入 s->next = s; *rear = s; } else { // 非空表，插入到rear->next之前 s->next = (*rear)->next; (*rear)->next = s; // rear指针不变，因为插入在头部，尾部没变 } } // 5. 在链表尾部插入元素（效率最高） void InsertAtTail(LinkList *rear, ElemType e) { LNode *s = (LNode *)malloc(sizeof(LNode)); if (!s) exit(EXIT_FAILURE); s->data = e; if (*rear == NULL) { // 空表插入 s->next = s; *rear = s; } else { s->next = (*rear)->next; // 新节点指向头 (*rear)->next = s; // 原尾节点指向新节点 *rear = s; // 更新尾指针 } } // 6. 在指定位置（第i个元素，从1开始计数）之后插入元素 int InsertAfter(LinkList *rear, int i, ElemType e) { if (i < 0 || *rear == NULL) return 0; // 位置非法或空表 LNode *p = (*rear)->next; // 从第一个节点开始找 int count = 1; // 寻找第i个节点 while (p != *rear && count < i) { p = p->next; count++; } if (count != i) { // 没找到第i个节点 return 0; } LNode *s = (LNode *)malloc(sizeof(LNode)); if (!s) exit(EXIT_FAILURE); s->data = e; s->next = p->next; p->next = s; if (p == *rear) { // 如果在尾节点后插入，需要更新尾指针 *rear = s; } return 1; } // 7. 按值查找节点 LNode* LocateElem(LinkList rear, ElemType e) { if (rear == NULL) return NULL; LNode *p = rear->next; do { if (p->data == e) return p; p = p->next; } while (p != rear->next); return NULL; // 未找到 } // 8. 删除第i个节点（从1开始计数） int DeleteNode(LinkList *rear, int i, ElemType *e) { if (i < 1 || *rear == NULL) return 0; // 位置非法或空表 LNode *p = (*rear)->next; // p初始指向第一个节点，最终指向待删除节点 LNode *pre = *rear; // pre初始指向尾节点，最终指向p的前驱 // 处理删除第一个节点的特殊情况，因为pre初始就是它的前驱（尾节点） if (i == 1) { // 要删除的节点是p } else { // 寻找第i个节点及其前驱 int count = 1; while (p != *rear && count < i) { pre = p; p = p->next; count++; } if (count != i) { // 没找到第i个节点 return 0; } } // 执行删除 pre->next = p->next; if (p == *rear) { // 如果删除的是尾节点 if (pre == p) { // 链表只有一个节点 *rear = NULL; } else { *rear = pre; // 更新尾指针为前驱 } } else if (p == (*rear)->next) { // 如果删除的是第一个节点（且链表节点数>1） // rear指针不需要改变，因为尾部没变，但头变了，这个变化已由pre->next = p->next体现 } if (e != NULL) *e = p->data; free(p); return 1; } // 9. 获取链表长度 int GetLength(LinkList rear) { if (rear == NULL) return 0; int len = 0; LNode *p = rear->next; do { len++; p = p->next; } while (p != rear->next); return len; } // 10. 销毁链表，释放所有内存 void DestroyList(LinkList *rear) { if (*rear == NULL) return; LNode *p = (*rear)->next; // 从第一个节点开始 LNode *q; (*rear)->next = NULL; // 打破环，变成普通单链表以便遍历释放 while (p != NULL) { q = p->next; // 保存下一个节点 free(p); // 释放当前节点 p = q; // 移动到下一个节点 } *rear = NULL; // 最后将尾指针置空 } // 主函数，测试所有功能 int main() { LinkList rear; // 尾指针 InitList(&rear); printf("1. Create a list with 5 elements.\n"); CreateList_R(&rear, 5); TraverseList(rear); printf("Length: %d\n", GetLength(rear)); printf("\n2. Insert 100 at head.\n"); InsertAtHead(&rear, 100); TraverseList(rear); printf("\n3. Insert 200 at tail.\n"); InsertAtTail(&rear, 200); TraverseList(rear); printf("\n4. Insert 300 after the 3rd element.\n"); if (InsertAfter(&rear, 3, 300)) { TraverseList(rear); } else { printf("Insert failed.\n"); } printf("\n5. Search for element 200.\n"); LNode *found = LocateElem(rear, 200); if (found) { printf("Found node with data: %d\n", found->data); } else { printf("Not found.\n"); } printf("\n6. Delete the 2nd element.\n"); ElemType deletedValue; if (DeleteNode(&rear, 2, &deletedValue)) { printf("Deleted element: %d\n", deletedValue); TraverseList(rear); } else { printf("Delete failed.\n"); } printf("\n7. Destroy the list.\n"); DestroyList(&rear); printf("After destruction, list is: "); TraverseList(rear); return 0; }

代码解析与关键点：

• 函数参数LinkList *rear：因为我们需要修改调用者手中的尾指针（例如初始化置空、插入后更新），所以必须传递尾指针的地址（二级指针）。这是C语言修改外部指针的标准做法。
• CreateList_R：尾插法的核心。每次插入新节点s后，都将其设为新的尾节点，并保证s->next指向头，维持循环。
• TraverseList：使用do...while是处理循环链表遍历的经典模式，能正确处理单节点情况。
• DeleteNode：这是最复杂的函数。它巧妙地用pre初始指向尾节点来处理删除第一个节点的情况。删除后，需要仔细判断并更新rear指针。
• DestroyList：在释放内存前，先将尾节点的next置为NULL，打破循环，从而可以将一个循环链表的释放转化为一个普通单链表的释放，简化了操作。

5. 常见问题与调试技巧实录

即使有了完整的代码，在实际编写和调试时，你依然可能会遇到下面这些问题。我把它们和解决方法记录下来，希望能帮你节省时间。

5.1 程序崩溃：访问空指针或野指针

• 症状：程序运行中突然崩溃，调试器提示Segmentation fault或访问了0x0地址。
• 常见原因：
  1. 对NULL指针进行了解引用操作，例如rear->next当rear为NULL时。
  2. 释放内存后，再次使用该指针（use after free）。
  3. 指针未初始化就使用。
• 排查技巧：
  • 防御性编程：在任何使用rear或p->next之前，先判断其是否为NULL。尤其是在TraverseList,Insert,Delete等函数的开头。
  • 画图辅助：在纸上画出链表操作前后的指针指向变化。对于复杂的插入删除，画图能极大降低出错概率。
  • 使用调试器：在关键函数处设置断点，单步执行，观察指针变量的值是否与预期一致。

5.2 内存泄漏：分配的内存未释放

• 症状：程序长时间运行后，内存占用不断增长（对于小程序可能不明显，但习惯很重要）。
• 原因：使用malloc分配了节点内存，但在删除节点或销毁链表时，没有调用free释放。
• 解决：
  • 确保DeleteNode和DestroyList函数中，每一个malloc都有对应的free。
  • 在DestroyList中，使用临时指针q保存下一个节点的地址，再释放当前节点，这是一个安全的内存释放模式。
  • 可以使用如Valgrind（Linux）或Dr. Memory（Windows）等工具来检测内存泄漏。

5.3 逻辑错误：遍历陷入死循环或提前结束

• 症状：遍历函数停不下来，或者该打印的元素没打全。
• 原因：循环终止条件错误。
  • 死循环：在while(p != NULL)这样的条件下遍历循环链表，因为永远没有NULL，所以死循环。
  • 提前结束：在while(p != rear)的条件下遍历，如果链表只有一个节点（p == rear），则一次都不会执行。
• 解决：牢记循环链表的遍历范式：do { ... } while (p != start_point);。务必在循环开始前正确记录起始点start_point = rear->next。

5.4 合并两个循环链表的“魔术”

这是一个展示循环单链表（尾指针表示法）优势的经典操作。合并两个链表La和Lb，要求时间复杂度为O(1)。

// 假设La和Lb都是非空的循环单链表的尾指针 LinkList Connect(LinkList La, LinkList Lb) { if (La == NULL) return Lb; if (Lb == NULL) return La; LNode *head_a = La->next; // La的头节点 LNode *head_b = Lb->next; // Lb的头节点 La->next = head_b; // La的尾节点指向Lb的头 Lb->next = head_a; // Lb的尾节点指向La的头（此时Lb->next已不是原来的头，但Lb指针本身仍指向原Lb的尾） // 新的尾指针是Lb（原第二个链表的尾） // 因为La现在是中间节点了，而Lb指向合并后链表的最后一个节点 // 实际上，也可以返回La，取决于你想把哪个链表的尾作为新链表的尾 return Lb; }

这段代码像变魔术一样，只通过几次指针赋值，就完成了合并。其核心思想是交换两个链表的“头尾连接”。理解它的最好方式，就是在纸上画出合并前后的指针变化图。

5.5 关于“头节点”的再思考

虽然我们这次实现选择了不带头节点，但带头节点的设计在“简化边界操作”上确有优势。例如，在带头节点的循环链表中，空链表是一个头节点自己指向自己的环。插入和删除第一个数据节点，不需要特殊判断rear是否为空或是否更新rear（如果使用头指针）。这使代码更统一。选择哪种方式，取决于你的具体需求和个人偏好。在面试或考试中，务必先明确题目要求或与面试官确认。