1. 为什么嵌入式开发绕不开循环链表做嵌入式这几年我越来越觉得数据结构不是面试题里的抽象概念而是实打实的工程工具。尤其是循环链表它在单片机、RTOS、驱动开发里出现的频率远比你想象的高。很多人学数据结构时觉得循环链表只是单链表的小改动不过就是把尾节点的 next 指向头节点而已原理确实是这样但真正到了嵌入式场景里你会发现这个“小改动”带来的边界处理差异、遍历方式的改变、以及内存管理的坑足以让你写出来的代码在稳定性和可维护性上拉开差距。先说一个很典型的场景按键扫描。一个产品里有十几个按键每个按键可能有短按、长按、双击、组合键事件不断产生。如果用固定数组做队列你得考虑数组满了怎么办、头尾指针怎么移动、取数据时怎么避免越界。用循环链表来做事件缓冲天然就是一个环形结构尾节点的 next 永远指向头节点遍历时不需要判空到 NULL 再从头开始只要判断“是否回到了头节点”即可。这一个特性在写状态机事件分发时特别顺手。再比如任务调度。很多轻量级 RTOS 里的就绪队列、延时队列内部实现就包含循环链表。每个任务控制块TCB作为一个节点调度器不断沿链表旋转找到最高优先级可运行任务。这种场景下循环链表让“轮转”这个动作变成了自然的指针移动而不是数组下标从头到尾再归零的麻烦操作。我之所以专门写一篇关于循环链表的文章是因为它在嵌入式里不仅是一个数据结构更是一种“内存布局思维”。你学的不是那个链表本身而是“在固定内存、无动态分配或受限动态分配、实时性要求高的环境下怎么组织数据流”。这篇文章我会结合嵌入式场景从核心原理讲到代码实现再给出一段完整的环形缓冲区案例最后聊聊调试时容易踩的坑。适合看这篇文章的人正在学嵌入式但觉得数据结构用不上的学生刚开始写单片机驱动想优化事件处理的开发者以及想系统整理链表知识的工程师。如果你已经能把单链表写得很溜这篇文章能帮你把循环链表彻底吃透并且知道它和单链表在嵌入式选型时该如何权衡。2. 核心设计思路循环链表到底解决什么问题2.1 从单链表到循环链表变化的不只是头尾相接单链表的典型结构是每个节点包含数据域和指针域最后一个节点的 next 指向 NULL。遍历时从头节点出发遇到 NULL 就停止。这在逻辑上很干净但有一个隐性成本每次要回到头部重新遍历时你必须保存着头指针或者从头再走一遍。循环链表则把尾节点的 next 指向头节点整个链表成了一个环。这样一来从任意节点出发都能遍历全部节点无需关心头在哪。这个特性在嵌入式里意味着调度器可以在任意位置继续运行下一个任务而不必每次从头开始扫描事件缓冲可以持续接收新事件老事件被覆盖后指针自然回绕。但注意这个“无需关心头在哪”也是一把双刃剑。因为没有 NULL 作为终止标志遍历时必须有一个明确的停止条件。最常见的做法是指定一个头节点遍历到头节点时停止另一个做法是记录当前节点的指针遍历回到当前节点时停止。这两种方式取决于你用的是“带头节点”还是“不带头节点”的实现。2.2 带头节点和不带头节点嵌入式里怎么选循环链表有两种常见实现方式不带头节点和带头节点。不带头节点的循环链表head 指针直接指向第一个有效数据节点。尾节点的 next 指向 head。这样一来整个环里全是数据节点遍历时从 head 出发回到 head 停止。这种结构紧凑适合你不关心“空闲节点”的场景比如任务就绪表每个节点都有实际含义。带头节点的循环链表有一个专门的头节点它的数据域不放有效数据只作为链表操作的锚点。尾节点的 next 指向头节点。遍历时通常从头节点的 next 开始遇到头节点停止。这种结构的好处是插入、删除不需要特殊处理空链表的情况头节点永远存在代码逻辑统一。但代价是多一个节点的内存开销。在嵌入式里怎么选我的经验是如果内存极其紧张且逻辑上每个节点都是有效数据用不带头节点如果代码可维护性优先且需要频繁插入删除、处理多种边界条件带头节点更省心。举个实际项目例子我写过一个多通道传感器数据采集模块每个通道对应一个缓存节点通道数量固定采集任务和上报任务之间用循环链表传递数据这里用的是不带头节点因为通道节点本来就是静态分配的不存在“空节点”的概念。而另一个需要动态增删日志条目的模块我用的是带头节点因为插入删除的边界情况太多了带头节点能让我少写一半的判断逻辑。2.3 循环链表的三个关键操作和单链表差在哪循环链表的插入、删除、遍历大体思路和单链表一致但有三处细节完全不同。第一处插入操作。在单链表尾部插入时你要先遍历到最后一个节点然后把新节点 next 指向 NULL再把尾节点 next 指向新节点。循环链表尾部插入也类似但最后一步是把新节点的 next 指向头节点而不是 NULL。如果你忘了这一步链表就不再是环了可能导致遍历时飞指针。第二处删除操作。删除节点时你要找到前驱节点把前驱的 next 指向被删节点的 next。在循环链表里如果被删的是头节点你要更新 head 指针如果被删的是尾节点你要让新的尾节点 next 指向头节点。这两种边界情况和单链表完全一样但在循环链表里更容易被忽略因为你看不到 NULL 给你“兜底”一旦处理错链表就断成两截。第三处遍历操作。这是差别最大的地方。单链表遍历有 NULL 作为终止符循环链表没有。你得用“是否到达头节点”或“是否回到起始节点”来判断。写 while(p ! head) 或者 do-while 结构取决于你的起点。很多初学者栽在这里写了个 for 循环想当然地以 NULL 结束结果死循环。这个在嵌入式的实时系统里是非常严重的问题——死循环等于系统卡死。3. 循环链表的具体实现从结构体到核心操作这段直接给出可在单片机或 Linux 环境下编译运行的代码以不带头节点、单一循环方向为例这也是嵌入式里最常见的形态。所有代码基于 C11未使用任何平台特殊语法。3.1 结构体定义与初始化typedef struct Node { int data; /* 数据域嵌入式里根据需求换成 uint8_t、任务指针等 */ struct Node *next; /* 指针域指向下一个节点 */ } Node; typedef struct List { Node *head; /* 指向第一个有效节点空表时为 NULL */ int count; /* 节点数量便于快速判断长度 */ } List; void List_Init(List *list) { list-head NULL; list-count 0; }这里我把链表头单独封装成一个结构体而不是直接用一个 Node 指针。原因是项目里往往不只一个链表实例封装后便于管理多个链表count 字段能在需要时 O(1) 获取长度省去遍历计数的开销。在嵌入式里能省一个循环就省一个循环尤其在一个主频只有几十兆赫兹的 MCU 上。3.2 尾部插入最常用的操作int List_InsertTail(List *list, int data) { Node *new_node (Node *)malloc(sizeof(Node)); if (new_node NULL) { return -1; } new_node-data data; if (list-head NULL) { /* 空链表新节点既是头也是尾自指成环 */ list-head new_node; new_node-next new_node; } else { /* 找到尾节点尾节点是 next 指向 head 的那个节点 */ Node *tail list-head; while (tail-next ! list-head) { tail tail-next; } tail-next new_node; new_node-next list-head; } list-count; return 0; }尾部插入的逻辑核心是“找到尾节点”。循环链表里没有哪个节点直接告诉你“我是尾”你得靠判断 tail-next 是否回到了 head回到就说明当前节点是尾。这段代码里有两处要注意第一空链表的情况下新节点的 next 指向自己形成一个单节点环。这一步不能漏漏了的话链表无法自洽后续插入会断链。第二单节点循环链表里头节点的 next 就指向自己所以“尾节点”就是头节点本身。这就是为什么 while 循环里没有遍历到任何节点就结束了因为 tail-next 已经是 head。3.3 删除指定节点找到前驱是关键int List_Remove(List *list, Node *target) { if (list-head NULL || target NULL) { return -1; } Node *prev list-head; Node *curr list-head; /* 遍历整个环直到回到头节点 */ do { if (curr target) { if (curr list-head) { /* 删除的是头节点 */ if (curr-next curr) { /* 只剩一个节点删除后链表为空 */ list-head NULL; } else { /* 找到尾节点让它指向新的头节点 */ Node *tail list-head; while (tail-next ! list-head) { tail tail-next; } list-head curr-next; tail-next list-head; } } else { /* 普通节点前驱直接指向后继 */ prev-next curr-next; } free(curr); list-count--; return 0; } prev curr; curr curr-next; } while (curr ! list-head); return -1; /* 未找到目标节点 */ }这段代码看着长但核心逻辑只有一句删除任意节点必须先找到它的前驱把前驱的 next 指向被删节点的后继。循环链表的难点在于边界如果删的是头节点新的头节点是谁如果删的是尾节点怎么找到新的尾如果是唯一节点删完之后链表变成空表head 清零。在实际项目里删除节点这个操作用得很多。按键事件处理完要移除、任务跑完要下队、日志满了要淘汰最旧的条目都会调删除。我建议你把这段代码封装成独立函数然后做一遍完整的边界测试尤其是单节点删除和头节点删除这是最容易出 bug 的地方。3.4 遍历do-while 才是循环链表的最佳拍档void List_Traverse(List *list, void (*handler)(int)) { if (list-head NULL) { return; } Node *curr list-head; do { handler(curr-data); curr curr-next; } while (curr ! list-head); }这里我特意用 do-while 而不是 while。原因很简单当链表中只有一个节点时用 while 先判断条件再执行条件为真curr-next 就是 head但你可能想执行一次结果 while 会因为“已经回到头”而直接跳过。但 do-while 保证至少执行一次。用 for 循环同样可以写但可读性差一些。我个人习惯是循环链表相关的遍历、寻找节点统一用 do-while让“至少执行一次”成为语义的一部分配合“回到头即停止”的终止判断逻辑最清楚。4. 嵌入式实战用循环链表实现环形缓冲区这一节我把循环链表放到一个具体场景里——串口接收转 DMA 处理。这个模块在很多嵌入式项目中都会用到非常具有代表性。4.1 为什么不用数组做环形缓冲区很多人第一反应是环形缓冲区用数组加头尾指针不就行了吗确实固定大小的数组环形缓冲是嵌入式里的经典方案占用内存少、访问快、无动态分配但缺点是容量固定数据满时要么丢弃新数据要么覆盖旧数据。在某些场景下这个“丢数据”是不可接受的。举个例子一个设备同时采集传感器数据、接收上位机指令、记录运行日志。不同类型的数据长度不同出现频率也不同。如果用固定数组你得为每种类型分别分配缓冲区内存利用率低如果统一分配一个大数组又可能造成浪费。而循环链表的好处是节点可以动态分配数据多时多占几个节点数据少时节点释放回堆内存利用率高。当然代价是动态 malloc 可能产生内存碎片所以这个方案适合有较充足堆空间的场景比如跑着 RTOS 的 MCU或者 Linux 嵌入式平台。4.2 环形缓冲区的完整实现这个模块解决的核心问题生产者和消费者之间数据传递。生产者是串口中断或 DMA 回调消费者是主循环里的处理逻辑。typedef struct RingNode { uint8_t *data; uint16_t len; struct RingNode *next; } RingNode; typedef struct RingBuffer { RingNode *head; /* 队头最早的数据 */ RingNode *tail; /* 队尾最新的数据 */ uint16_t count; } RingBuffer; void RingBuffer_Init(RingBuffer *rb) { rb-head NULL; rb-tail NULL; rb-count 0; } /* 生产者调用入队 */ int RingBuffer_Push(RingBuffer *rb, uint8_t *data, uint16_t len) { RingNode *node (RingNode *)malloc(sizeof(RingNode)); if (node NULL) { return -1; } node-data data; node-len len; if (rb-head NULL) { rb-head node; rb-tail node; node-next node; /* 成环 */ } else { node-next rb-head; /* 新节点指向头 */ rb-tail-next node; /* 旧尾指向新节点 */ rb-tail node; /* 更新尾指针 */ } rb-count; return 0; } /* 消费者调用出队 */ int RingBuffer_Pop(RingBuffer *rb, uint8_t **data, uint16_t *len) { if (rb-head NULL) { return -1; /* 空缓冲 */ } RingNode *node rb-head; *data node-data; *len node-len; if (rb-head rb-tail) { /* 只有一个节点出队后为空 */ rb-head NULL; rb-tail NULL; } else { rb-head node-next; rb-tail-next rb-head; /* 维持环状 */ } free(node); rb-count--; return 0; }这个实现值得注意的地方是我同时维护了 head 和 tail 两个指针。很多教材上的循环链表只维护一个 head尾部插入时要遍历整个链表才能找到尾节点复杂度 O(n)。在缓冲场景里每个数据都要走一次 O(n) 的插入实时性完全不行。维护 tail 后插入变成 O(1)出队也是 O(1)两个指针同步更新。有读者可能会问为什么入队函数里只传 data 指针而不复制数据这在嵌入式里是一个设计选择。如果每个节点都 malloc 一块数据空间再 memcpy内存开销大且拷贝耗时。我个人的做法是数据本身由生产者提供并持有节点只保存指针和长度消费者用完数据后负责释放或复用。这样把内存所有权关系理清了不会出现谁释放谁的问题。当然这种做法要求生产者和消费者之间有明确的约定不能出现生产者释放了数据但消费者还没读的情况。4.3 缓冲区使用示例/* 模拟串口接收回调 */ void UART_RxCallback(uint8_t *buf, uint16_t len) { RingBuffer_Push(rx_ring, buf, len); } /* 主循环中的处理逻辑 */ void MainLoop_Task(void) { uint8_t *data NULL; uint16_t len 0; while (RingBuffer_Pop(rx_ring, data, len) 0) { ProcessData(data, len); } }主循环只处理出队不关心数据是从哪来的中断只负责入队不关心数据会被怎样消费。这个解耦是环形缓冲区最重要的价值。你可以在一个模块上接多个生产者、多个消费者只要保证入队和出队操作的互斥性比如关中断或使用 RTOS 的互斥锁。我在实际项目中把这种环形缓冲用在了一个嵌入式网关设备上四个串口同时收发数据每个串口对应一个循环链表缓冲主控芯片是双核异构架构一个核跑 Linux 负责协议处理另一个核跑裸机程序负责实时采集缓冲节点在两个核的共享内存里用循环链表组织数据效果非常稳定。5. 循环链表的经典应用约瑟夫环与任务轮转环形缓冲区是循环链表最常见的嵌入式应用但它不是唯一一个。这一节聊聊另外两个经典场景顺便给出实现思路。约瑟夫环是数据结构教材里的经典题目虽然实际工程中用得少但它极适合用来理解循环链表的核心操作。5.1 约瑟夫环循环链表的天然考题约瑟夫环描述是n 个人围成一圈从某个人开始报数报到 m 的人出列然后下一个人继续从 1 报数直到所有人都出列。这个“围成一圈”精确匹配了循环链表的结构。节点就是人报数过程就是沿 next 指针移动。实现思路void Josephus(int n, int m) { List circle; List_Init(circle); for (int i 1; i n; i) { List_InsertTail(circle, i); } Node *curr circle.head; Node *prev NULL; /* 找到尾节点作为 prev 的初始值 */ prev circle.head; while (prev-next ! circle.head) { prev prev-next; } while (circle.count 0) { /* 报数 m-1 次因为 curr 已经算报到 1 */ for (int i 1; i m; i) { prev curr; curr curr-next; } int out curr-data; /* 从环中删除 curr 节点 */ Node *next curr-next; if (curr circle.head) { circle.head next; } prev-next next; free(curr); circle.count--; curr next; printf(出列: %d\n, out); } }这段代码的难点只有一处删除当前节点时要知道它的前驱。因为循环链表是单向的你必须用 prev 指针时刻跟随。每次移动时 prev 和 curr 同步更新这样当 curr 指向要出列的人时prev 恰好指向他的前驱删起来就顺理成章。很多教科书在讲约瑟夫环时用数组模拟思路是让下标模 n 实现回绕。但用循环链表实现的优势在于删除操作是真正 O(1) 的不需要把后面的元素前移。当 n 很大时性能差距非常明显。我曾在某高校的实验室做过一个测试n 取一万m 取一百数组法需要反复 memmove循环链表法大约快一个数量级。5.2 任务轮转循环链表在 RTOS 调度中的思路很多轻量级 RTOS 的任务调度器里就绪任务链表就是一个循环链表。每个任务节点包含任务控制信息、状态、优先级等调度器沿着链表循环找到首个可运行任务就切换过去。这个机制的妙处在于它天然实现了时间片轮转。每个任务运行完自己的时间片后调度器把指针移到下一个节点下一次调度就从新节点开始不需要从头扫描所有任务。这个场景下循环链表和数组的最大区别是数组的轮转靠下标自增后取模实现。if 判断一次有没有越界取模一次得到回绕后的下标。循环链表则把这次回绕融进了指针本身你移动指针就是轮转永远不可能越界。这背后的思维差异是数组需要显式处理边界链表通过结构自身化解边界。5.3 其他嵌入式场景一览除了环形缓冲和任务轮转循环链表在嵌入式里还有几个常见用途内存池的空闲块管理用循环链表把所有空闲块串成一个环分配时从当前位置向后找释放时把块挂回当前位置附近能减少碎片化。日志系统的写读指针管理。多个日志条目按时间顺序组织满了之后覆盖最旧的条目天然的循环结构。多级菜单界面。很多嵌入式产品的人机界面是树形菜单但同级菜单项的切换就是循环的——最后一个菜单项按“下”键回到第一个。用循环链表组织同级菜单项切换就是移动节点指针。图形界面里的焦点循环。控件焦点从最后一个 Tab 回绕到第一个和菜单切换是同一类问题。6. 循环链表与单链表的选型对比嵌入式中该怎么选这一节把循环链表和普通单链表放在一起做个多维度对比帮你在项目里快速判断该用哪个。6.1 操作复杂度对比操作单链表尾指针循环链表尾指针头部插入O(1)O(1)尾部插入O(1)需尾指针或 O(n)O(1)需尾指针头部删除O(1)O(1)尾部删除O(n)O(n)需找前驱遍历遇 NULL 停止遇头节点停止从中间开始遍历不支持支持单链表如果维护一个尾指针尾部插入也是 O(1)这点和循环链表持平。但单链表从任意节点开始无法遍历完整链表循环链表可以。当你的业务逻辑天然是“环”形时比如轮转、循环覆盖、周期调度循环链表是唯一合理的选择。尾删除操作两种链表都是 O(n)因为单向结构找前驱只能从头遍历。如果项目里尾部删除很频繁可以考虑双向循环链表代价是多一个 prev 指针的内存开销。6.2 内存开销对比单链表每个节点一个指针循环链表也是每个节点一个指针二者在节点层面没有内存差异。差别在于链表的整体结构单链表有一个 NULL 终止节点概念上的循环链表没有。但单链表如果想快速判断是否为空、是否遍历结束需要维护额外的头指针信息。编译器层面这点差异基本可以忽略不计。真正影响内存决策的是你有没有为每个节点分配独立的存储空间。如果节点总数固定且数量不大用静态分配的循环链表池节点从池里取出和归还不依赖 malloc能有效避免堆碎片。具体做法是定义一个大数组每个元素是 Node用一个静态链表把所有空闲节点串起来需要时从空闲链取一个释放时还回去。这种技巧在资源紧张的 MCU 上非常实用。6.3 什么时候别用循环链表循环链表不是万能的。有两个场景我明确不建议用它数据规模固定且小、访问模式以随机访问为主需要频繁随机查找某个下标的节点。比如说一个温度传感器采集任务每秒钟采一个值保留最近 100 个值的滚动窗口。这个用固定数组加环形指针就够了因为下标可以直接算出链表反而多一个 next 指针的开销。再比如你需要经常按索引访问第 k 个节点链表做不到 O(1) 随机访问必须从头遍历 k 次这时数组是更合理的选择。所以我的选型判断标准很简单数据流是天然循环的用循环链表数据操作是以固定下标为主用数组节点数量动态变化、增删频繁用链表数据规模固定、实时性要求极高优先用静态数组。7. 常见问题与调试经验速查7.1 我在实际项目中踩过的三个坑第一个坑尾节点没有指回头节点导致链表上有 NULL。表现是一次遍历后指针变成 NULL再想回到头部就无从下手了。排查方法是打印每个节点的 next 值看有没有出现 0x00000000。如果出现顺着这个节点往回查多半是它当初创建时 next 没有正确指向头。第二个坑删除头节点后其他节点还拿着旧的 head 指针。解决方法是删除后立刻更新所有相关指针特别是在多线程或中断环境下对外暴露的接口里要一致地更新。我见过有人在中断里删了一个节点主循环还在用旧 head 遍历结果直接访问了已释放的内存。第三个坑遍历时死循环。这个在多任务环境里特别隐蔽——一个任务在遍历循环链表另一个任务在插入节点直接打破了你遍历开始时保存的终止条件。比如你保存了 head 作为终止标志另一个任务插入新节点在头节点前面遍历就可能绕过头节点永远停不下来。解决办法是遍历期间禁止链表修改或者遍历不依赖终止标志改为固定次数。7.2 调试现场实录有一次调试一个跑着循环链表的多通道采集模块现象是系统偶尔死机概率不高但一旦出现就完全卡死。我一开始怀疑是中断冲突逐段排查后发现在链表删除函数里少了一个环节当删除的是唯一的头节点时我没有把 tail 也置空。此时 head 已经是 NULL但 tail 还指向已释放的节点。下一次入队时因为 head 为 NULL 走了空链表分支tail 没有被更新但出队时判断 head tail两者不相等代码以为还有节点访问了已释放的内存崩溃。这个例子提醒我所有涉及多处指针更新的操作必须同时考虑 head 和 tail 两个指针不能只更新其中一个。后来我把这两段更新逻辑封装成了一个小函数任何入队出队都先调用它问题彻底消失。7.3 边界条件自检清单每次写完循环链表相关代码后我会按这个清单自查一遍空链表插入第一个节点时新节点的 next 是否指向自身删除唯一节点后head 和 tail 是否都变为 NULL删除头节点时是否更新了 head 并且让新的尾节点指向新的头遍历时终止条件是否依赖了可能在执行过程中被修改的变量插入、删除操作在中断和主循环并发调用时是否有保护机制链表节点释放后指针是否被置为 NULL避免悬空。这份清单不是凭空想出来的是多次线上问题换来的。每一条都有对应的真实故障案例而这个清单里的检查项加起来不过六行却能挡住绝大多数链表相关的线上事故。8. 关于循环链表的最后几点心得体会做了多年嵌入式开发我最深的感受是数据结构的重要性不在于你知道多少种而在于每种你能不能在恰当的场合用对。循环链表就是最典型的例子——单链表大家都学过但“把尾接到头上”这一步思维跨越才是真正把数据结构融入工程思维的分水岭。在实际编码中我建议你做两件事。第一把常用的循环链表操作封装成一个可复用的库包括创建、插入、删除、遍历、查找、清空统一命名规范。这样多个项目都能直接复用不需要每次重写。第二在写链表代码前先把边界条件画一遍或者用笔在纸上走一遍流程。链表类的 bug 95% 发生在边界条件上提前想清楚后面能省下大量调试时间。如果你正在学嵌入式或者正在准备面试我特别建议你把循环链表和环形缓冲区写一遍哪怕不用到项目里光是这个过程就能帮你建立对指针操作、内存管理、边界处理的肌肉记忆。练完之后你会发现看很多 RTOS 源码或者驱动代码时心里明显有底了。最后分享一个小技巧当你面对一个“似乎应该用循环链表但又不确定”的需求时就问自己一个问题——数据流回绕到起点的行为是业务逻辑内在需求还是只是为了处理数组越界的手段如果是前者用循环链表如果是后者数组加模运算就够了。这个判断标准救了我很多次希望它也对你有用。