单循环链表这个名字光听起来就比普通单向链表多了一层循环的戏。很多人学完单向链表之后觉得链表不过如此结果一碰到单循环链表写出来的遍历代码直接死循环卡得怀疑人生。原因很简单普通链表判断链表结尾看的是p-next NULL而单循环链表里根本没有 NULL最后一个节点的 next 指针重新指回了头节点——整个链表变成了一个环。这一个改动看起来小实际上牵扯到初始化、遍历、插入、删除、销毁的每一个环节全都要跟着改思路。这篇文章我会用 C 语言把单循环链表从头到尾实现一遍不仅给代码还会把每一步为什么这么写讲清楚。内容适合正在学数据结构的本科生、准备计算机二级或考研复试的同学也适合工作中突然要用 C 手写链表、但很久没碰过的朋友。我把带头节点的实现、核心操作的易错点、约瑟夫环实战、调试经验以及单片机场景下的替代思路都整理在下面每一块都是可以在编译器里直接跑的建议你边看边敲。1. 从 NULL 到回环单循环链表到底改了什么1.1 普通单向链表的一个不够优雅的地方先回顾一下普通的单向链表。每个节点有一个数据域和一个 next 指针next 指向下一个节点最后一个节点的 next 指向 NULL表示到尾巴了。这个结构本身没有任何问题但它有一个不算毛病的毛病如果你想从任意一个节点出发把整条链表走一遍你是做不到的。因为走到尾节点之后next 是 NULL路就断了你没办法回到头节点继续走。单循环链表就是为了解决这个回头难的问题。它的做法非常直接把尾节点的 next 从 NULL 改成指向头节点让整个链表首尾相接形成一个环。这样带来的最直观好处是从任何一个节点出发沿着 next 一直走一定能遍历完整条链表。这在某些场景下非常有用比如轮转调度、约瑟夫环问题、循环缓冲区管理数据是转着圈访问的天然需要一个环形的结构。不过这个改动也带来一个直接代价没有了 NULL 这个天然的终点标志。你遍历链表的时候不能再写while (p ! NULL)了得改成while (p ! head)。只要写错这一个条件程序就会在环里无限绕圈CPU 直接占满程序卡死。很多人第一次写单循环链表都是栽在这个地方。1.2 带头节点和不带头节点的两个变体单循环链表有两种常见形态带头节点和不带头节点。不带头节点的方式更纯粹头指针直接指向第一个数据节点尾节点的 next 指向头指针指向的节点整个链表就是一个闭合的环。这种形态写起来很简洁但空链表不好表示——链表为空时头指针只能指向 NULL那么问题来了NULL 和指向自身的节点就产生了矛盾判断空表和非空表的逻辑会变得复杂插入删除时还得分情况讨论是不是第一个节点。带头节点的方式是在第一个数据节点之前额外加一个哑节点这个头节点不存实际数据只作为链表的入口和标志。尾节点的 next 指向头节点空链表时头节点的 next 指向自身。这样一来无论链表是否为空都有一个统一的终点标志——头节点本身。判断空表只需看L-next L插入删除第一个节点和插入删除其他节点逻辑完全一致不需要特殊处理代码可以写得很统一。我的建议非常明确初学阶段一律用带头节点的方式。它多占一个节点空间但换来的是一整套简化的逻辑省下来的是排查边界条件的时间。等你把带头节点的版本吃透了再去看不带头节点的写法那就是降维打击一眼就能看懂。1.3 什么时候我们真的需要单循环链表单循环链表的应用没有普通链表那么广但一旦用上往往是不可替代的那种。最常见的场景是约瑟夫环问题。一群人围成一圈从某个人开始报数数到 k 的人出列然后从下一个人继续报数直到剩下最后一个人。这个围成一圈、循环报数、出列后再从下一个继续的过程本质上就是一个单循环链表在不停地遍历和删除节点。用数组也可以模拟但每删除一个人都要移动后续元素复杂度高用单循环链表删除一个节点只需要改两个指针O(1) 搞定。另一个典型场景是分时操作系统的进程调度。多个进程轮流使用 CPU时间片用完就让出 CPU轮到下一个进程执行。这个轮转的队列天然就是环形的队尾的进程用完之后下一个目标不是出队而是回到队首的进程。用单循环链表来实现这种调度队列结构上非常贴合。还有一类通用思维判断一条链表是否有环时用的快慢指针方法本质上就是在检测链表中是否存在循环结构。你理解了单循环链表再去看快慢指针判断环的问题理解会深很多。2. 存储结构与初始化先让链表转起来2.1 结构体定义一个结构体加一个 typedef 就够单循环链表的存储结构跟普通单向链表完全一样就是一个节点包含数据域和指针域指针域存的是下一个节点的地址。C 语言里用结构体定义即可。#include stdio.h #include stdlib.h typedef int ElemType; // 把元素类型抽象出来改这一处就能换成其他类型 typedef struct Node { ElemType data; // 数据域 struct Node *next; // 指针域指向下一个节点 } Node, *LinkList;这里有个值得解释的点struct Node的 next 指针为什么必须写struct Node *而不是Node *因为在结构体定义内部Node这个类型名还没定义完编译器还认不得它但struct Node这个结构体标识符在开始定义时就已经存在了所以必须用完整的struct Node *来声明。等typedef执行完之后外部才能直接用Node和LinkList。另外LinkList本质上就是Node *的别名为什么还要单独起一个名字这是很多教材沿用下来的一种语义约定声明一个变量时如果你写LinkList L说明你心里清楚这是一个链表头指针是用来代表一整条链表的如果你写Node *p说明这是一个普通的工作指针用来遍历节点。这种约定不是语法必须的但对读代码的人非常友好一看变量名就大致知道它的职责。工程上的代码规范很多时候就体现在这种细节里。2.2 初始化空表的标志是指向自己带头节点的单循环链表初始化要做的事情非常简单申请一个头节点然后让头节点的 next 指向它自己。这个自己指向自己的状态就是空链表的标志。void InitList(LinkList *L) { *L (Node *)malloc(sizeof(Node)); if (*L NULL) { printf(内存分配失败\n); exit(1); } (*L)-next *L; // 空表头节点指向自己 }注意这里函数参数是LinkList *L也就是Node **L二级指针。为什么要传二级指针因为初始化时要修改传入的头指针本身让L指向新分配的头节点。C 语言函数的参数是值传递如果你传的是LinkList L在函数内部给L赋值函数结束后这个修改不会带回到调用方出来之后L还是原来的野指针。只有传指针的地址才能通过*L ...这种写法真正修改调用方的变量。很多初学者第一次写链表时都卡在这个二级指针上我的建议是不要死记链表函数必须传二级指针而是看这个函数是否需要修改头指针本身。需要改就传二级指针不需要改只是遍历、查找、插入、删除中间节点传一级指针就够了。判断标准本身很简单想清楚参数传递的机制就不会再被二级指针绕晕。2.3 节点创建的封装把 malloc 和检查放在一起接下来是基础工具函数CreateNode。之所以单独封装一个创建节点的函数是因为插入操作经常要创建新节点每写一次插入就写一次 malloc 加空指针判断代码会非常啰嗦。封装之后所有插入函数里只需要一句Node *newNode CreateNode(e);就完事了统一管理还能避免漏掉空指针检查。Node *CreateNode(ElemType e) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data e; newNode-next NULL; return newNode; }malloc 失败返回 NULL 的情况虽然不常见但一旦发生后续所有对 newNode 的访问都是非法访问程序崩溃是小事产生难以排查的野指针问题才是大事。所以我始终坚持动态内存分配的返回值一定要检查。哪怕只是打印一条错误信息然后退出也远比带着 NULL 继续往下跑要安全得多。newNode-next NULL这一步也别省。虽然创建节点后马上就会在插入函数里重新设置 next但保留一个初始化的习惯可以防止哪天插入逻辑写复杂了忘记设置 next拿到的就是一个随机地址调试起来会让你怀疑人生。3. 核心操作遍历、插入、删除、查找、销毁3.1 遍历终止条件从 NULL 变成头节点一个字符都不能错遍历是第一个要面对的思想转变。普通单向链表的遍历条件是while (p ! NULL)单循环链表必须写成while (p ! L)这里的 L 是头节点。因为尾节点的 next 指向头节点所以当头节点的地址再次出现时说明已经绕着环走了一圈遍历结束。void Traverse(LinkList L) { if (L-next L) { printf(链表为空\n); return; } Node *p L-next; while (p ! L) { printf(%d , p-data); p p-next; } printf(\n); }我特意在遍历前加了一个空表判断。虽然就算链表为空p L-next之后p Lwhile 循环一次都不会进入输出一个空行也能正常结束但加上这个判断能让空表这个状态在语义上表达得更清晰。读代码的人一眼就能看出这个函数对空表有明确处理。遍历这个操作看起来简单但它其实是检验你对循环终止条件理解深度的试金石。如果你在写遍历的时候心里想的是走一圈就停那你的代码自然写成p ! L如果你心里想的还是走到尾巴就停那写出来的多半是p ! NULL然后程序就永远停不下来了。代码只是思维的外在表现先把脑子里的循环模型改过来代码才不会出错。3.2 插入操作头插法和尾插法都有各自的门道插入操作分为头插和尾插两种。头插是把新节点插在头节点后面作为第一个数据节点尾插是把新节点插在链表末尾。先看头插法它很直观void InsertHead(LinkList L, ElemType e) { Node *newNode CreateNode(e); newNode-next L-next; L-next newNode; }这里只需注意一点必须先让newNode-next L-next再让L-next newNode。如果把顺序反过来先改L-next newNode原来的第一个节点地址就丢了链表直接从中间断开后续的新节点后面跟的就不是原来那个节点了。这个先接后面再接前面的顺序在链表插入里属于基本功只要画一下连线图就能很清楚。尾插法稍微麻烦一点因为单循环链表只有一个方向的 next 指针要找到最后一个节点只能从头开始遍历void InsertTail(LinkList L, ElemType e) { Node *newNode CreateNode(e); Node *p L; while (p-next ! L) { p p-next; } newNode-next L; // 新节点成为新的尾节点next 指向头节点 p-next newNode; // 原来的尾节点指向新节点 }这里while (p-next ! L)终止时p 一定是尾节点因为只有尾节点的 next 才指向头节点。找到尾节点之后让新节点的 next 指向头节点再让原尾节点的 next 指向新节点两个赋值一前一后完成。顺序同样不能反过来否则尾节点的 next 丢失后面的节点就找不到了。尾插因为每次都从头遍历到尾时间复杂度是 O(n)。如果频繁做尾插一个常见的优化是加一个尾指针rear始终指向最后一个节点这样尾插就是 O(1)。但它带来的代价是在头插、删除、销毁等操作里如果尾指针指向的节点被删了或链表结构变了尾指针可能失效需要额外维护。工程上这叫用空间复杂度换时间复杂度或者反过来属于一个经典的均衡设计问题。初学阶段我会建议先用简单的遍历版本把核心逻辑学明白再去想尾指针优化。3.3 删除操作永远记得找到前驱节点删除是链表操作里最需要小心的。单链表的删除逻辑是要删掉某个节点必须找到它的前驱节点让前驱的 next 直接跨过这个节点指向它的后继然后释放掉这个节点。这个找前驱的思想贯穿所有单向链表的删除操作。按值删除一个节点的实现如下int DeleteNode(LinkList L, ElemType key) { Node *pre L; // pre 始终指向 p 的前驱 Node *p L-next; while (p ! L) { if (p-data key) { pre-next p-next; // 跨过 p让前驱指向 p 的后继 free(p); // 释放 p 的空间 return 1; // 删除成功 } pre p; p p-next; } return 0; // 没有找到值为 key 的节点 }这段代码的核心是两个指针一前一后同步移动pre 是指向当前节点 p 的前驱。当 p 的 data 等于 key 时直接让pre-next p-next把 p 摘下来然后 free。注意 pre 和 p 是同步移动的pre 先记下 p 当前的位置p 再往后走一步这样下一轮循环里 pre 仍然是 p 的前驱。有两点容易被忽略。第一free 之后不能再去访问 p 的任何内容因为你已经把它还给了系统第二删除后 return 退出只删第一个匹配到的节点。如果链表里有多个重复值需要全部删除的话不能在删除后直接 return而是让 pre 保持不动因为 pre 的 next 已经被更新了p 直接移动到新的后继节点继续检查。还有一个小细节这里删除的是数据值等于 key 的节点但现实中更常见的需求是按位置删除比如删除第 i 个节点。逻辑类似只是查找条件从p-data key变成了数到第 i 步。思路完全一样都是先找前驱再改指针再释放。3.4 查找返回节点指针还是返回位置查找操作相对简单就是遍历链表判断 data 是否等于目标值Node *FindNode(LinkList L, ElemType key) { Node *p L-next; while (p ! L) { if (p-data key) { return p; } p p-next; } return NULL; }之所以返回Node *而不是返回下标是因为链表在物理上是不连续的下标这个概念在链表里没有意义。你拿到一个节点的地址之后可以做两件事一是直接修改这个节点的 data二是基于这个节点做插入或删除。在工程上返回指针比返回下标有更强的表达力。需要注意一个陷阱FindNode返回的是一个指向链表内部节点的指针。在链表结构发生变化之后比如删除了某个节点、头插了一个新节点或者整个链表被销毁了之前保存的节点指针可能已经失效。下次再用这个指针之前最好重新查找一遍或者确认链表结构没有发生过影响它的变化。这个指针有效性的问题是链表使用中最容易踩的暗坑之一。3.5 销毁逐个释放别直接把头节点 free 掉链表销毁是很多初学者容易忽略的环节。写练习代码的时候可能无所谓程序一退出操作系统自己回收内存但在长期运行的程序里频繁创建链表却不释放内存会一点一点被吃光最终导致程序崩溃。单循环链表的销毁逻辑是从第一个数据节点开始逐个释放所有数据节点最后再把头节点释放。注意顺序绝对不能错必须先保存下一个节点的地址再释放当前节点。void DestroyList(LinkList L) { Node *p L-next; while (p ! L) { Node *temp p; // 保存当前节点 p p-next; // 先移动到下一个节点 free(temp); // 再释放当前节点 } free(L); // 最后释放头节点 }这里有一个非常经典的错误写法while (p ! L) { free(p); p p-next; }。一旦 free(p) 执行完p 指向的那块内存已经归还给系统p-next就成了访问已释放内存的非法操作行为是未定义的轻则段错误重则在嵌入式环境里直接触发硬件异常。所以务必养成先保存下一个节点的地址再释放当前节点的习惯。有人会问单循环链表销毁完之后要不要把头指针置为 NULL严格来说应该置因为如果头指针还保存着已经释放的内存地址后续一旦误用就会形成野指针问题。但置 NULL 这个动作没法在 DestroyList 函数内部完成因为函数内部拿到的是头指针的副本只能通过传二级指针的方式来修改调用方变量。所以我更推荐的做法是销毁之后在调用方手动把 L 置为 NULL。这是防御性编程的基本素养。3.6 单循环链表和双向循环链表的取舍单循环链表只有一个方向的 next 指针它最大的短板是已知一个节点你想找它的前驱做不到只能重新从头开始遍历。这在删除操作里体现得最明显每删一个节点都要维护一个 pre 指针或者从头找前驱。双向循环链表在每个节点里多了一个 prior 指针指向它的前驱这样从任意节点出发往前、往后都能走。代价是每个节点多占用一个指针大小的内存而且插入删除时多处理一个方向的指针代码更容易写错。取舍的标准其实很简单如果业务场景主要是正向遍历、尾部插入、按正向顺序报数单循环链表完全够用代码简单内存还省如果频繁需要反向查找、从尾部往前处理或者要快速定位一个节点的前驱那双向循环链表带来的便利会更值。4. 约瑟夫环实战为什么它天然适合单循环链表4.1 一个流传了一千多年的报数问题约瑟夫环问题讲的是n 个人围成一圈从第一个人开始报数报到 k 的人出列然后从他后面的那个人开始重新报数报到 k 的人再出列……直到所有人出列为止。最后出列的那个人是幸存者。这个问题最早可以追溯到公元 1 世纪的犹太历史学家约瑟夫斯他和 40 名士兵被围困决定宁死不降于是围成一圈每隔几个人处死一个人约瑟夫斯靠计算位置活到了最后。听起来很传奇但今天的意义在于它是检验循环数据结构理解程度的经典编程题。为什么这个问题天然适合单循环链表因为它描述的就是一个循环的、不断删除节点的过程n 个人是 n 个节点围成圈意味着尾节点要指向头节点报数 k 就是在链表上走 k 步出列就是删除一个节点从下一个人继续就是删除之后从后继节点重新开始。这一切行为单循环链表几乎就是为它量身定做的。4.2 用单循环链表建模的思路先想清楚我们要用什么形态的链表。约瑟夫环不需要空表这种状态也不需要额外的头节点所以这里直接用不带头节点的循环链表更适合一些。每个节点的 data 存人的编号从 1 到 n。关键点在于删除节点这个动作。在单链表里要删除当前指针指向的节点必须找到它的前驱。如果在遍历过程中用一个 p 指针不断移动当 p 指向要删的节点时你没法直接删它因为拿不到前驱。所以一个常用的技巧是让 p 始终指向待删除节点的前驱这样p-next就是要删除的节点。那么报数的逻辑可以这样表达当前从 p-next 这个节点开始报数 1数到 k 时实际上要往前走 k-1 步因为 p 已经站在了报数 1 的前一个节点上。每走一步p 移到它的后继走完 k-1 步后p 正好站在待删除节点的前驱位置。然后del p-next就是要出列的人输出编号摘除并释放它最后让 p 指向被删除节点的后继下一轮报数就从这个后继开始。4.3 完整代码20 行解决约瑟夫环下面是完整代码可以直接编译运行。这里假设 k 2因为 k1 时每报一个数删一个是另一个简单的边界情况后面我会专门讲。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; // 创建包含 n 个节点的单循环链表节点值为 1~n Node *CreateCircle(int n) { Node *head (Node *)malloc(sizeof(Node)); head-data 1; head-next NULL; Node *tail head; for (int i 2; i n; i) { Node *newNode (Node *)malloc(sizeof(Node)); newNode-data i; newNode-next NULL; tail-next newNode; tail newNode; } tail-next head; // 尾节点指向头节点形成环 return head; } // 约瑟夫环出列顺序n: 人数k: 报数出列的数 void Josephus(int n, int k) { if (n 0 || k 0) return; if (k 1) { // 特殊情况每次报到 1 就出列 for (int i 1; i n; i) { printf(%d , i); } printf(\n); return; } Node *p CreateCircle(n); // p 指向头节点报数起点 while (p-next ! p) { // 只剩一个节点时结束 // 报数 1 的人是 p-next报数 k 的人要走 k-1 步到达前驱 for (int i 1; i k - 1; i) { p p-next; } Node *del p-next; // 待出列节点 printf(%d , del-data); p-next del-next; // 摘除节点 free(del); // 释放空间 p p-next; // 从被删节点的后继开始下一轮报数 } printf(%d\n, p-data); // 最后一个幸存者 free(p); } int main() { printf(约瑟夫环 n7, k3 的出列顺序\n); Josephus(7, 3); return 0; }运行结果为约瑟夫环 n7, k3 的出列顺序 3 6 2 7 5 1 4你可以拿笔手动模拟一下7 个人围成一圈从 1 开始报数报 3 的出列。第一次报数到 33 号出列从 4 号开始报 15 号报 26 号报 36 号出列从 7 号开始报 11 号报 22 号报 32 号出列……一路推进最后剩下的 4 号确实和代码输出一致。这种手动模拟 代码验证的验证方法比任何单元测试都更能帮你建立对数据结构的直觉。4.4 复杂度和边界情况分析这个实现的时间复杂度是 O(n * k)。每出列一个人要走 k-1 步找前驱一共要出列 n-1 个人所以总的移动次数大约是 (n-1)*(k-1)。如果 k 很大这个算法会比较慢但这属于约瑟夫环问题本身的特点不是数据结构的问题。空间复杂度是 O(n)n 个节点。边界情况里最需要注意的是 k1。当报数 1 就出列时出列顺序其实很简单就是 1 到 n 的编号依次输出但上面那个循环逻辑处理不了因为每次循环里del p-next删的是报数 1 的人后面的那个节点。所以我在代码里单独加了 k1 的分支直接输出 1 到 n代码在逻辑上就完整了。我在实际面试和考试中看到过很多人死磕 k1 的边界导致整个题目没写完其实很可惜。边界处理不是死记硬背而是用心想一下这个场景下我的通用逻辑还成立吗不成立就单独写一个分支处理几行代码的事却能展现出你考虑问题是否周全。5. 调试中反复踩过的坑与排查经验5.1 死循环单循环链表最常见的翻车现场单循环链表调试过程中遇到最多的问题就是程序跑起来之后没有任何输出CPU 占用率跑到 100%整个程序卡死。这种症状大概率是死循环也就是遍历链表时循环终止条件写错了或者链表的环没有正确闭合导致工作指针永远走不到头。我自己的排查经验是先别急着看代码先画图。拿一张纸把链表当前的形态画出来从头节点开始沿着 next 指针一个一个画下去看它到底会不会回到头节点。如果画到一半回到某个中间的节点说明链表的 next 设置有误某个节点的 next 指向了不存在的内存地址如果一直画不完说明循环链表的环没有闭合到预期的位置。代码层面最常见的错误有两个。第一个是把遍历条件写成while (p ! NULL)这在循环链表中永远为真必然死循环第二个是删除或插入时某个节点的 next 没有被正确赋值导致链表的环在某处脱开变成了一条带环的残链遍历时会无限绕圈。5.2 指针悬空free 之后为什么还在访问我在给学弟学妹讲链表时经常打一个比方free 一个节点相当于把房间的钥匙还给了物业但你自己手机里还存着这个房间的地址。你拿着这个地址再去找它很有可能找到的是已经住了别人或者正在装修的房间拿到的东西完全不可控。放到代码里就是free(p)之后p 这个指针变量里仍然保存着原来的地址但你不能再通过 p 去访问任何内容了。可编译器不会拦你程序可能偶尔正常偶尔崩溃行为完全取决于这块内存是否已经被系统重新分配给别人。这就是未定义行为最恶心的地方——它不是必现的导致排查难度成倍增加。我的经验是动态链表代码里严格遵循两条纪律。第一free 之后立刻把指针置为 NULL这样误用的时候至少能在早期被发现第二释放一个节点之前永远先把它需要的后继地址保存下来也就是先取后删的套路。这两条纪律看起来简单但能避免绝大多数难缠的 bug。5.3 定位维也纳的三板斧调试法很多人定位链表 bug 时喜欢到处打 printf结果越打越乱。我自己总结了一套比较高效的三板斧排查法第一在关键操作前后打印结构信息。比如插入前后、删除前后打印当前链表的内容。如果插入后链表内容多了说明插入成功如果内容少了或者顺序乱了说明操作破坏了链。这种粗粒度定位能快速把人带到犯罪现场。第二只保留一块可疑区域的输出。定位到大致的函数之后把无关的 printf 全部注释掉只保留下一个关键点比如删除函数里 pre 和 p 的值一步一步看两个指针的移动是否符合预期。这比到处乱打印有效得多因为输出太多人的注意力反而会被分散。第三利用 gdb 之类的断点调试工具。在疑似出错的代码行上打断点单步执行每一步停下来打印 p、pre、newNode 的地址和值配合链表当前结构基本能一眼看出问题。C 语言的链表问题绝大多数都能通过这种数据流可视化的方式快速定位真正需要看汇编才能解决的情况极少。5.4 边界条件清单每次写完链表对照检查一遍我每次写完链表代码提交之前都会对照下面这张清单检查一遍可以帮你筛掉至少一半的 bug检查项正常情况需要警惕的错误空链表头节点 next 指向自己头节点 next 为 NULL 或野指针只有一个节点该节点 next 指向头节点该节点 next 指向 NULL遍历终止回到头节点就停写成 ! NULL 导致死循环删除唯一节点删除后成为空表头节点自身被误删或释放销毁链表全部释放完无泄漏只释放了头节点或只释放了部分节点插入第一个节点头插后 first 更新新节点 next 未设置链断裂插入最后一个节点尾节点 next 指向头节点新节点 next 指向 NULL这张清单不是考试要背的东西而是长期调试链表代码总结出来的标准动作。写代码的时候在这些边界情况上多想一分钟后面可能就省下一个小时的调试时间。尤其注意只有一个节点和删除唯一节点这两个状态它们是链表从非空到空、从空到非空的转折点最容易出错。5.5 单步调试配合画图比任何 IDE 的工具都好用很多教材喜欢给链表配各种可视化工具确实有帮助但我的体会是亲手画链表的状态迁移图比任何工具都更能建立直觉。你拿一张纸把每个节点画成一个方块里面写 data 和 next 地址然后手动模拟一次插入或删除先改哪个指针再改哪个指针画完你就知道代码为什么必须按这个顺序写。我在调式约瑟夫环代码时就是用这种方法验证出错的把每个节点的地址、data、next 全列出来手动走一遍删除流程代码里走一步纸上画一步很快就发现是删除节点的 p 在下一轮报数时没有从正确位置开始计数。这种问题如果不画图光看代码可能看两三个小时都找不出来。6. 内存受限场景下的替代方案单循环链表思想在单片机上的落地方案6.1 为什么动态内存分配在单片机上常常是个问题很多学 C 语言的朋友学了链表之后会产生一个疑问链表不是很好用吗为什么我在单片机上很少见到有人用 malloc 来写链表这里面的原因其实很现实。malloc 是标准库提供的动态内存分配函数在 PC 上有完整的堆管理机制操作系统虚拟内存充足就算分配得碎一点问题也不大。但在单片机上内存总共就那么几十 KB甚至几 KB堆区非常小而且很多嵌入式环境里根本没有标准的 malloc 实现或者实现了但碎片化问题非常严重。举个例子你连续 malloc 了很多小节点用完之后一部分被释放剩下的内存就成了一个个细小的空洞。下一次 malloc 一个大节点很可能找不到足够大的连续空间明明内存还有剩余却分配失败。在 PC 上这个问题可以通过虚拟内存和操作系统回收来缓解在单片机上内存碎片就是实打实的灾难。所以很多嵌入式项目干脆就禁用动态内存分配所有变量必须在编译期确定好大小。6.2 用静态数组模拟单循环链表在不允许动态分配内存的场景下单循环链表的思想依然可以用只不过存储空间从一个一个 malloc 出来的堆节点变成一块预先分配好的静态数组。数组的下标就用来代替指针充当连接节点的索引。#define MAX_SIZE 100 int data[MAX_SIZE]; // 数据域 int next[MAX_SIZE]; // 指针域存的是另一个节点的下标 // 初始化循环链表n 个节点连成环 void InitCircular(int n) { if (n MAX_SIZE) n MAX_SIZE; for (int i 0; i n; i) { data[i] i 1; next[i] (i 1) % n; // 最后一个节点的 next 指向 0形成环 } } // 遍历输出 void Traverse(int n) { int p 0; for (int i 0; i n; i) { printf(%d , data[p]); p next[p]; } printf(\n); }这其实就是静态链表的思路用数组下标代替指针用一圈已经分配好的内存模拟动态链表的行为。在单片机上做轮转调度、做各种表单管理时这种写法比直接裸用数组要灵活得多因为它不需要移动数据只需要修改 next 数组里的下标就能实现插入和删除。我见过不少单片机项目里即便硬件资源极其紧张依然会用这种静态链表来管理任务队列或 IO 事件。它带来的好处是空间预分配、无碎片、无动态内存管理开销同时保留了链表逻辑的灵活性。这个思路也再次说明学数据结构学的不是某个具体 API而是一种组织数据的思想换一个受限的环境你依然能用它的核心思想写出高效又稳妥的代码。6.3 怎么判断一个场景到底该不该用链表最后聊一个工程上的通用决策框架什么场景用数组好什么场景用链表好。数组的优点是随机访问 O(1)、内存连续、缓存友好缺点是中间插入和删除要移动大量元素O(n) 的成本。链表的优点是插入删除只要改指针、O(1) 搞定缺点是随机访问要遍历、内存不连续、每个节点还有额外的指针开销。所以你可以在脑海里形成一个简单的判断如果你的操作以按位置访问为主比如查第 10 个元素、改第 50 个元素数组更合适如果你的操作以在中间频繁插入删除为主比如维护一个实时变化的播放列表、任务调度队列链表更合适。如果是围成一圈循环访问、边访问边删除那就是单循环链表的绝对主场。实际工程里不会有标准答案但理解了数据结构在内存层面的根本差异之后你做出的选择才真正靠谱。这也是为什么我一直强调学习链表不能只看代码能跑还要理解它为什么会存在、在什么场景下才能真正发挥威力。我自己在写单循环链表这段代码时踩得最惨的一次是在遍历条件上一个p ! NULL写成p ! L的顺序颠倒直接让我排查了将近一个小时。后来我想明白一个道理这类数据结构问题十个有九个出在指针的边界状态上。如果你现在也被卡在某个链表 bug 里不要急着瞎试先画一张链表结构图然后对照我前面列的边界条件清单一步一步看大概率能在五分钟内定位问题。链表这种东西代码量不大但每一步都值得想清楚再写。
