循环链表：从约瑟夫环到操作系统调度器的工程实战

先说一个挺常见的现象很多人学数据结构时循环链表是“学了但基本只在考试里见过”的知识点。刷题时最标准的题目就是约瑟夫环做完之后会觉得这玩意儿除了模拟淘汰游戏好像也没别的用处。我在做了一段时间系统级开发和嵌入式相关的工程后才把这部分认知翻了篇——循环链表的核心价值根本不在于刷题而在于它天然表达了“转一圈再转一圈”这种语义而系统底层到处都是这种语义。这篇文章就围绕循环链表的真实应用场景展开适合正在学数据结构的学生、刚接触系统编程的开发者以及想把算法和工程实践对起来的同行。我会把每个场景的原理、代码和踩坑点都拆开讲清楚。1. 循环链表和普通链表在语义层上的差别才是它被选中的原因1.1 三种链表结构的核心差异先看一个最简单的对比。线性表在物理存储上无所谓我们可以用数组、单链表、双向链表、循环链表去表示同一组数据但这几种结构在“访问逻辑”上差别很大。很多人只记住了“循环链表就是尾节点指向头节点”却没有深想这一步改变带来了什么。我习惯用下面这张表来总结常见结构的核心特征结构是否区分头尾遍历结束条件删除尾部节点效率找前驱节点典型适合场景数组明确下标越界O(n) 移动元素直接下标访问定长、随机访问频繁单链表明确某个节点的 next 为空O(n)O(n)头插头删多、内存碎片化双向链表明确尾部 next 为空O(1) 已知尾节点时O(1)前后遍历都频繁单向循环链表不明确走回起点O(n)O(n)循环轮转、天然重复遍历双向循环链表不明确走回起点O(1)O(1)需要双向轮转、中间动态删除这里最值得注意的是“是否区分头尾”这一行。在普通链表里尾节点是一个边界到了边界就要停下来而循环链表里没有“边界”的概念只有“起点”。换句话说循环链表把“最后一个节点”和“第一个节点”之间那条链路直接打通了从任何一个节点出发都能走完整个集合且回到自身。1.2 循环链表擅长表达三类语义理解了结构差异再看使用场景就有章可循。循环链表在工程里被选中通常是因为它精准命中了以下三种语义之一。第一是轮转语义。比如多个进程轮流使用 CPU、多台服务器轮流处理请求、多个窗口轮流叫号这些场景都有一个共同点处理完最后一个对象之后下一个仍是第一个。如果用数组实现需要维护一个currentIndex每次越界就取模但用循环链表只需要让指针走到p-next当指向头节点时跳过一次或者直接让尾节点的 next 指向真实的首节点不需要任何取模逻辑。数组取模的写法虽然不难但在“需要频繁动态增删参与者”的前提下数组的插入删除代价很高这是后话。第二是环形存储语义。典型的代表就是环形缓冲区生产者写满尾部后回到头部继续覆盖旧数据消费者永远拿着自己的读指针向前推进。这种“空间被复用旧数据被覆盖”的行为本质上就是一个循环链表在管理缓存区域。第三是从头开始重复执行的语义。比如多轮比拼、回合制游戏、循环播放列表。一轮结束后下一轮的起始点要和上一轮结束点无缝衔接循环链表直接满足这个需求不需要外部再维护一个“是否重新开始”的状态变量。所以我的建议是遇到一个问题先别看它要不要用链表先看它的行为会不会“绕圈回到起点”。如果会循环结构大概率是靠谱选项如果只是普通的从头到尾线性访问那用普通链表或数组反而更简单。2. 操作系统时间片轮转里的环形队列与一个简化调度器操作系统中的时间片轮转调度Round-Robin简称 RR是循环链表最经典、也最贴合其设计初衷的系统级应用。搞懂了它你就知道为什么教科书在讲调度时总爱画一个环形队列。2.1 为什么轮转调度天然是“环形”的时间片轮转的基本思想很朴素系统维护一个就绪进程队列每个进程只能运行一个固定长度的时间片比如 100 毫秒。时间片用完后不管进程是否运行完都把它挂到队列尾部调度器再取队首进程继续运行。这个描述里最容易被忽略的两个字是“队尾”。问题是这个“队尾”并不是一个固定的边界。因为进程会随时创建、唤醒、阻塞、退出队列里的成员在不断变化。假设当前队列顺序是 A-B-C当前运行的是 C。C 用完时间片后下一个应该轮到谁是 A。但如果这是普通单链表C 的 next 是空你不得不额外用一个指针记录队首再手动跳回去。而循环链表里C-next 指向 A调度器只需要做一次current current-next就完成了“回到开头”的动作。更微妙的是在就绪队列中每个进程是“平等”的系统并不希望任何节点拥有“我是队列头”的特殊权利。用循环链表管理时调度器只保存一个“当前进程”指针不需要单独维护头尾指针队列本身自我闭环。这种设计在有大量进程切换、频繁插入和删除时尤其干净。2.2 用 C 语言实现一个简化版 RR 调度器为了把上面的抽象概念落地我写了一个简化版本用单向循环链表模拟三个进程的轮转执行。每个进程节点里放一个time_left字段表示还需要多少 CPU 时间每次调度器给当前进程分配一个固定的时间片如果进程的时间被耗尽就打印“执行完毕”并将其移出链表否则轮到下一个进程。#include stdio.h #include stdlib.h #define TIME_SLICE 2 typedef struct Process { int pid; int time_left; struct Process *next; } Process; // 创建进程并把它插入到环形链表中 Process* create_process(Process *head, int pid, int time_left) { Process *p (Process*)malloc(sizeof(Process)); p-pid pid; p-time_left time_left; p-next NULL; if (head NULL) { p-next p; // 第一个节点指向自己形成环 return p; } // 找到尾节点把新节点插入到尾节点之后 Process *tail head; while (tail-next ! head) { tail tail-next; } tail-next p; p-next head; return head; } // 从链表中删除指定进程返回新的链表头 Process* remove_process(Process *head, Process *target) { if (head NULL) return NULL; if (head-next head) { free(head); return NULL; } Process *prev head; while (prev-next ! target) { prev prev-next; } if (target head) { head target-next; } prev-next target-next; free(target); return head; } void schedule(Process *head) { Process *current head; while (head ! NULL) { printf(进程 [%d] 开始剩余时间 [%d]\n, current-pid, current-time_left); // 执行一个时间片 if (current-time_left TIME_SLICE) { current-time_left - TIME_SLICE; printf(进程 [%d] 时间片用完剩余 [%d]排到队尾\n, current-pid, current-time_left); current current-next; } else { printf(进程 [%d] 本次执行完毕\n, current-pid); Process *next current-next; head remove_process(head, current); current next head ? head : next; if (current NULL) break; } } printf(所有进程执行结束\n); } int main() { Process *head NULL; head create_process(head, 1, 3); head create_process(head, 2, 5); head create_process(head, 3, 8); schedule(head); return 0; }这段代码里有个容易被忽略的细节当链表里只剩一个节点时它的next是自己。所以在remove_process中第一件事就是判断head-next head如果成立直接释放当前节点并返回NULL。否则单向链表找前驱需要从头遍历这在小规模模拟里没问题但在真实的调度器中通常会改用双向循环链表让每个节点都有prev指针删除任意节点时就不需要遍历找前驱了。2.3 调度实现里的实际教训第一点时间片的大小直接影响系统开销。时间片太大后到的进程等待时间会变长交互性变差时间片太小上下文切换本身就消耗大量资源。真实的调度器还会引入多级反馈队列、优先级等机制但底层“环形轮转”的思想始终保留。第二点删除当前节点时一定要先把next指针存下来。我在上面代码中特意写了Process *next current-next;如果你先调用remove_process再访问current-next那已经是未定义行为了因为节点已经被free。第三点如果链表很长频繁的进程退出会让“找前驱”变成 O(n) 操作。真实内核里就绪队列很少用单向链表更多用双向循环链表。所以面试或项目里只要涉及“环形结构加频繁删除”优先考虑双向版本这不是炫技是为了少干活。3. 约瑟夫环问题的链表模拟我见过的两种常见写法约瑟夫环几乎是循环链表最出名的入门题但不同人的实现差异很大。我这里不是只给出一份答案而是想把两种典型写法和背后的权衡讲清楚。3.1 约瑟夫环的题面与最直观的思路约瑟夫环问题描述很简单假设 N 个人围成一圈从第 1 个人开始报数报到 M 的人出列然后从出列者的下一个人重新开始报数报到 M 的人再出列直到所有人都出列。要求输出出列顺序或者找出最后一个留在圈里的人。这个问题在纸上推演一轮你会发现所有操作都发生在“一个圈”上。每一次删除后下一次报数的起点正好是删除节点的后继节点。这是最直观的循环链表使用场景因为“删除当前节点后立刻访问后继节点”就是p-next的天然能力。如果把问题改成数组删除一个元素后要移动后续所有元素复杂度太高即使用“标记法”跳着遍历每个报数步骤都要反复判断是否已被淘汰代码也不简洁。3.2 用单向循环链表模拟的代码与缺陷最省内存的做法是用单向循环链表。但单向链表删除某个节点时必须找到它的前驱所以在模拟报数的过程中单链表实现的麻烦点就出现了你得走到被删除节点的前面一个节点才能安全改写next。#include stdio.h #include stdlib.h typedef struct Node { int num; struct Node *next; } Node; // 创建单向循环链表返回头节点 Node* create_list(int n) { Node *head NULL, *tail NULL; for (int i 1; i n; i) { Node *p (Node*)malloc(sizeof(Node)); p-num i; p-next NULL; if (head NULL) { head p; p-next head; } else { tail head; while (tail-next ! head) tail tail-next; tail-next p; p-next head; } } return head; } void josephus_single(Node *head, int m) { Node *p head; // 找到头节点的前驱作为“报数时的前一位置” Node *prev head; while (prev-next ! head) prev prev-next; while (head-next ! head) { // 报数 m-1 次让 prev 指向待删除节点的前驱 for (int i 1; i m; i) { prev prev-next; } Node *del prev-next; printf(出列%d\n, del-num); if (del head) head del-next; prev-next del-next; free(del); } printf(最后留下%d\n, head-num); free(head); }这段代码里最绕的地方就是那个prev指针。它不只是为了找前驱同时也充当了“报数计数器”的载体每报一个数字prev向后移动一次。等m-1次报数完成prev-next就是要删除的节点。3.3 用双向循环链表让逻辑更直白同样是约瑟夫环如果节点里有prev指针整个逻辑会清楚不少从当前位置出发报数时用一个cur指针走 M-1 次然后del cur出列后cur cur-next删除节点时用pre-next nxt; nxt-prev pre;就完事了。不再需要维护“前驱的前驱”也不需要考虑删除head时的特殊情况因为循环链表的每个节点都平等。我个人的建议比较直接如果你只是模拟报数题目规模又不大单链表版本足够它省内存也让人理解“找前驱”的代价但如果这个逻辑要被嵌进更大的系统中后续还有大量“删除任意节点并继续遍历”的操作用双向循环链表写起来和改起来都能省一半的脑力。另一点值得说的复杂度问题模拟约瑟夫环的复杂度是 O(N*M)对于海量数据必然跑不动这时候就该转向数学解法用递推公式直接求最后一个幸存者。这说明一个规律数据结构解决的是“过程模拟”问题而数学模型解决的是“结果计算”问题。工程和算法题都要学会区分这两种处境。3.4 这类模拟在工程里到底有什么用很多人会觉得约瑟夫环仅仅是考试题。但你仔细看游戏里的“淘汰轮换”“按顺序踢出队伍”“定时循环清退超时连接”等逻辑本质都是一个环形集合加上“每隔 M 个删除一个”的操作。再比如某些在线房间系统会周期性检查成员存活状态把失联的玩家移出房间同时轮流从某个起点开始检查——这就是约瑟夫环的工程形态。虽然不至于每次都绕成一道数学题但环形链表作为底层容器是很常见的。4. 播放列表、环形缓冲和时钟置换近在身边的循环应用循环链表并不只藏在操作系统调度里很多你每天都在用的软件底层都有着类似的循环结构。4.1 播放列表的循环模式为什么适合双向循环链表音乐播放器里常见的“列表循环”逻辑是播放完最后一首歌后回到第一首继续播放。如果播放列表允许用户随时增加歌曲、删除歌曲、调整顺序那么用双向循环链表维护当前播放位置会非常自然。每一首歌的节点里next指向下一首prev指向上一首播放器只需要保存一个“当前播放节点”指针。用户点“上一首”current current-prev点“下一首”current current-next最后一首的next指向第一首天然完成循环。可能有人会说现实中播放器底层不一定用链表用数组加取模也能做。确实很多简洁实现都是用数组索引加(index 1) % total完成的。这恰恰说明一个道理如果集合长度固定、很少增删数组加取模更合适如果集合经常变化、要支持任意位置插入删除链表才显出优势。拿音乐播放器举例用户在列表中间插一首歌数组可能需要移动大量元素双向循环链表直接在相应位置拼接指针就好。这类操作的实时性虽然在普通播放器里感觉不出来但在大型点播系统、直播轮播台这类频繁修改播放队列的场景里差别就出来了。4.2 环形缓冲区数组实现循环语义的代表另一个非常常见的循环应用是环形缓冲区。比如音频硬件采集数据时生产者麦克风驱动不断写入 PCM 数据消费者音频处理线程不断读出数据进行播放。如果数据生产速度和消费速度不完全一致就需要一块缓存区垫在中间。缓冲区如果满了新数据应该覆盖最旧的数据而不是阻塞等待。实现环形缓冲区最常用的方案是数组加两个指针写指针指向下一个可写入位置读指针指向下一个可读位置。每当指针到达数组末尾就把它折回到数组开头。这个“折回”行为本质上就是把数组当作了一个循环链表来使用只是没有显式的指针节点而已。用数组实现有几大好处内存连续、可以整块申请、CPU 缓存友好、读写延迟低。因此在音视频、网络协议栈、串口驱动里环形缓冲区基本都是数组实现。相比之下如果每个数据包都做成链表节点反而会因为频繁 malloc 和节点不连续导致性能下降。这个例子给我们一个重要启示循环语义不等于必须用链式存储。选择哪种实现关键看节点大小是否固定、增删是否频繁、是否对内存连续性有要求。4.3 后者说操作系统内存管理里的类似场景浏览器历史记录、最近使用的文件列表等“淘汰最老记录”的逻辑也是循环应用的变种。真正让我印象深刻的是操作系统页面置换算法里的一种方案它在内存管理模块中维护一个环形链表每个节点代表一个页面。它的工作方式是系统维护一个环形指针类似时钟的时针。当需要淘汰一个页面时从当前指针指向的位置开始扫描如果页面的访问位是 0就淘汰它如果是 1就把访问位清 0指针继续前进直到找到可淘汰的页面。这个机制完美利用了循环链表的“转圈”特性把有限的内存页面当成一个环来重复检查既不会漏掉任何一个页面也不会轻易停在某个中间位置。这个算法在计算机专业课程里经常出现但很少有人把它和数据结构里的循环链表联系起来。我每次讲到这儿都会特意提一句这不是孤立的算法而是循环链表在真实系统里被完整应用的一个范本。5. 游戏回合、动态负载均衡与循环链表的边界情况最后一个部分聊聊循环链表在游戏逻辑、负载均衡中的实践以及它的一些“坑”。这些内容不算是冷知识但确实容易被刚起步的开发者忽略。5.1 回合制游戏中的行动队列回合制游戏里所有角色要按一个固定顺序轮流行动A 出手、B 出手、C 出手再回到 A。传统做法是用数组存储行动序列配合一个turnIndex每回合执行完(turnIndex 1) % count。但如果战斗过程中有角色死亡、被移除、新角色加入数组就需要频繁移动或重建。我在一个模拟项目里试过用双向循环链表管理战斗序列每个角色节点保存出手顺序死亡角色直接从链表中摘除新加入的角色在合适位置插入。操作粒度和数组完全不同代码也更贴近“这一轮该谁行动”的直觉。而且当某个角色获得额外回合、被眩晕跳过时只需要在环形链表中灵活移动当前指针不用处理数组下标错乱的问题。当然如果采用严格的回合制且角色数量固定直接用数组仍是最简洁的。这个选择逻辑和播放器一致动态变化频繁则链表占优否则数组占优。5.2 动态负载均衡里的轮询策略负载均衡器里的轮询调度是另一个高频出现环形的场景。最简版本index (index 1) % serverCount。但如果服务器列表会动态增删比如某台机器服务降级被摘除、扩容时加入新机器用数组实现就要定期重建列表。循环链表可以在不重建整体结构的前提下把宕机节点移除、把新节点插入到合适位置当前正在轮询的指针也能平滑过渡。在这个场景里双向循环链表还有一个额外优势如果希望从当前节点反向遍历或者删除当前指针指向的节点不需要从头找前驱实现成本更低。真实系统中节点数量可能成百上千每次删除都从头遍历是不现实的。5.3 循环链表最容易被反噬的三个边界情况分享了这么多应用之后必须说几个我在实测里踩过、或者帮别人排查过的坑。第一个坑是while (p ! head)死循环。很多人写循环链表的遍历习惯用while (p ! NULL)但循环链表里除了空链表几乎没有NULL出现因此遍历条件必须改成“回到起点判定”。如果绕到中间某个节点时才意识到自己忘了处理头指针程序大概率已经死循环了。解决办法是在遍历前用变量保存起点然后每次移动后检查p-next start或p start来决定是否继续。第二个坑是释放链表时的闭环。普通链表释放只需要从头部逐个free循环链表如果处理不当第一个节点释放后原来尾部节点的next还指向已经被释放的地址再次访问会触发未定义行为。正确的释放方式通常是先断开环路让尾节点指向NULL把环退化成普通链表再按常规方式逐个释放。或者用一个计数器记录节点数量数到 N 个节点后停止。第三个坑是“读取环形缓冲区的覆盖问题”。虽然环形缓冲区用数组实现但思想上承接自循环链表如果没有正确管理读指针和写指针的距离读端可能读到被覆盖的数据写端也可能覆盖掉未读数据。这个问题比链表指针的威力藏得深得多调试起来也更隐蔽通常要靠打印读写指针和缓存占用量来定位。这些边界情况看似细节但在工程实践中往往就是线上故障的源头。我刚接触循环链表时总觉得理论简单、代码也很好写真正进入复杂系统后才意识到结构的简单只体现在纸面上落到内存管理和边界判断上时每一步都需要小心翼翼。/如果把前端到后端这些年碰到的数据结构和应用场景都摆出来循环链表给我的印象从来不是“难”而是“容易小看”。它既可以是操作系统调度器里的核心队列也可以是一款播放器里的循环播放逻辑。判断一个场景该不该用它我的经验就一句话先看问题的行为是不是要绕圈再看集合里的元素是不是会频繁增删。如果两个条件都满足循环链表就是比数组取模更贴合的做法如果只有一个条件就得结合内存连续性、定位性能等因素做取舍。最后分享一个我自己的小习惯在使用循环链表时我会特意给链表保留一个“哨兵节点”让真实数据节点串在哨兵后面。这样即使链表为空也仍然存在一个自环结构代码里对“空表”和“非空表”的处理可以统一很多边界判断会因此干净很多。这个习惯是我在做了几个包含进程管理、消息转发的模拟项目后总结出来的对减少 bug 很有效。希望这篇文章能把循环链表从“考试结构”变成你工具箱里一个真正有辨识度的工具。