简介一册讲解带头结点链表、循环链表与双向链表核心概念的PPT课件主要面向正在学习数据结构与算法的初学者、备考者以及需要系统复习链表知识的编程人员课件从带头结点链表的设计思路讲起说明头结点便于统一处理空表与插入删除操作的优势随后重点分析循环链表判断空满状态的条件并提醒遍历时避免无限循环双向链表部分则聚焦插入与删除四步指针调整的顺序帮助读者避开常见错误。此外课件还通过集合运算和一元多项式相加的完整示例展示线性表在具体算法中的应用便于将概念落到代码实现上资源包内共1个PPT文件压缩包大小616KB图示与代码片段结合内容紧凑适合对照讲义自学或课堂讲解使用。目前已有415人学习/下载。学习后可系统掌握三类链表的特征与基本运算理解底层指针变化逻辑并进一步体会线性表结构在算法设计中的价值。1. 循环链表和双向链表课设、面试和菜单导航都绕不开的两种结构“循环链表和双向链表”这个标题看着是教科书里的基础章节实际上却是区分“背过链表”和“真会链表”的一道分水岭。循环链表解决的是“转圈”型问题比如约瑟夫环、轮询调度和播放列表循环双向链表解决的是“既要往前又要往后”的导航型问题比如编辑器撤销、浏览器历史和最常见的双向链表多级菜单。这篇笔记面向那些正在准备数据结构课设、复习面试题、或者要把链表写进嵌入式菜单里的人我会把常见实现、参数调整和排错路径一次说透。2. 循环链表把尾指针接回头结点才能解决“转圈”问题2.1 “转圈”场景为什么首选循环链表从轮询到约瑟夫环单链表的最后一个节点指向 NULL遍历到尾部就停了天然是“一条道走到黑”。但现实场景里有一类问题是“绕圈”音频播放器列表循环、RTOS 里的时间片轮转调度、系统里多个客户端轮流取资源它们都要求走到最后一个节点之后能回到第一个节点。如果拿单链表硬做每轮结束就要从头重新走一遍复杂度从 O(1) 退化到 O(n)如果拿数组做轮转删除一个出列元素要移动后续所有元素同样低效。循环链表解决的就是这个“收尾衔接”问题最后一个节点的 next 不再指向 NULL而是指回头结点或者第一个数据节点。这样遍历没有终点只有“回到起点”的概念。经典题目约瑟夫环本质上就是循环链表上的“计数 删除”操作每次报数到 m 就删掉当前节点然后从下一个节点继续报数整套流程和循环链表的遍历删除完全同构。常见做法是用两个指针从头部开始一个当前节点、一个前驱节点删除时改前驱的 next 即可时间复杂度 O(1)。2.2 带头结点版创建与遍历的最小可运行代码我会优先写带头结点的版本因为它对“空表”和“头部插入”的处理统一课设判分也看得清楚。关键点只有一个空链表时头结点自己指向自己表示“当前没有数据节点”。来看创建函数#include stdio.h #include stdlib.h typedef struct CNode { int data; struct CNode *next; } CNode; // 用数组 arr 构建一条带头结点的循环链表n 是元素个数 CNode *create_circular(int arr[], int n) { CNode *head (CNode*)malloc(sizeof(CNode)); CNode *tail head; head-next head; // 空链表头结点自环 for (int i 0; i n; i) { CNode *node (CNode*)malloc(sizeof(CNode)); node-data arr[i]; node-next head; // 新节点的 next 先指向头结点 tail-next node; // 前一个尾节点接上新节点 tail node; // 移动尾指针 } return head; }注意第 10 行和第 11 行的顺序先让 node-next 指向 head再把 tail-next 指向 node。如果把顺序写反tail-next 已经被 node 覆盖链表就在中间断了。循环链表里“新节点先认头、旧节点再接新节点”这条规则和普通链表尾插法一致只是多了一步指向 head。参数上n 为零时返回一个自环头结点此时遍历函数必须单独判空否则第一轮就会进入死循环。配套遍历函数要用 do-while 而不是 for// 打印整条循环链表空表输出 empty void print_circular(CNode *head) { CNode *p head-next; if (p head) { printf(empty\n); return; } do { printf(%d , p-data); p p-next; } while (p ! head); // 回到头结点说明绕完一圈 printf(\n); }这里最容易被新手写成while (p ! NULL)但循环链表里根本没有 NULL尾节点的 next 是 head这样判断会让程序一直绕圈。do-while 保证了至少执行一次循环体也就保证了空链表之外的场景都能正常输出最后一个节点。想验证链表是否成环最简单的方法是在遍历里加一个计数器超过节点总数就直接报错退出。2.3 约瑟夫环把报数出列映射成遍历与删除约瑟夫环的常见表述是n 个人围成一圈从第 1 个人开始报数报到 m 的人出列然后从下一个人重新报数求全部出列顺序。用循环链表实现时我一般不带头结点直接用数据节点首尾相接语义上更贴“围成一圈”。先构建环形链表// 创建 1..n 的环形链表返回第一个节点 CNode *create_ring(int n) { CNode *head NULL; CNode *tail NULL; for (int i 1; i n; i) { CNode *node (CNode*)malloc(sizeof(CNode)); node-data i; node-next node; // 先自环后续再修正 if (head NULL) { head node; tail node; } else { tail-next node; // 旧尾接到新节点 tail node; tail-next head; // 新尾回环到头 } } return head; }创建时最后一个节点的 next 始终回指 head这样就只有数据节点、没有头结点。接下来是约瑟夫环主逻辑// n 个人报数报到 m 出列打印出列顺序 void josephus(int n, int m) { CNode *p create_ring(n); // p 是当前报数者 while (p-next ! p) { // 只剩一个节点时它自环 CNode *pre p; while (pre-next ! p) { // 找到 p 的前驱 pre pre-next; } for (int i 1; i m; i) { // 报数 m-1 次 pre p; p p-next; } printf(%d , p-data); // 报到 m 的人 pre-next p-next; // 前驱越过 p CNode *tmp p; p p-next; free(tmp); } printf(%d\n, p-data); free(p); }重点说两个参数m1 时 for 循环一次都不执行pre 是上一轮找到的前驱删除仍然安全m 大于 n 时for 循环会绕很多圈时间复杂度是 O(n*m)n 在十万以内可以直接用再大建议改成保留 pre 指针的写法把内部查找前驱的 O(n) 去掉。这里的“找前驱”循环可能有性能浪费但胜在逻辑直观出 bug 的概率低。测试时给 n7、m3输出顺序是 3 6 2 7 5 1 4跑通这个用例就说明基本逻辑没问题。3. 双向链表多一个 prev 指针换来的是前后双向的可逆操作3.1 为什么要多存一个 prev单链表的“复盘困境”单链表有个天然短板只能往后走。想回到上一个节点要么从头重新遍历要么额外维护一个栈。可现实里到处都是“后退”需求浏览器后退按钮、编辑器 CtrlZ、路由器配置菜单回到上一级都要求数据结构能双向移动。双向链表在每个节点里多存一个 prev 指针指向前一个节点本质上是为“后悔药”付的存储成本。这个成本在 64 位系统上大约是每个节点多 8 字节换来的是“给定节点删除”从 O(n) 降为 O(1)。单链表删除一个节点需要从头找到它的前驱双向链表因为节点自己存了 prev直接就能拿到前驱。插入操作同理已知位置双向插入也是 O(1)。但代价不只是内存插入和删除都要维护两条链出错概率成倍上升指针顺序写错链表当场断成两截或者变成环。下面这张表是我在课设里常用的对比能力单链表双向链表双向循环链表节点额外指针1 个2 个2 个给定前驱删除O(1)O(1)O(1)给定节点本身删除需找前驱 O(n)O(1)O(1)反向遍历不支持支持支持且到尾部无缝回开头典型场景栈、邻接表菜单导航、LRU、编辑器内核链表、环形缓冲实际选型时我会这样判断如果代码里只有“向后追加”和“从头部弹出”单链表就够一旦出现“选中当前项后返回上一项”这类交互直接上双向链表不要等后来补 prev 指针那会比一开始写多费三倍时间。3.2 插入与删除的指针赋值顺序口诀与常见错误双向链表的核心操作就两个在某个节点之后插入新节点、删除某个给定节点。两段代码都不长但指针赋值顺序错一个链表就会从中间断开。先看插入在 p 之后插入 stypedef struct DNode { int data; struct DNode *prev; struct DNode *next; } DNode; // 在 p 节点之后插入 s 节点 void insert_after(DNode *p, DNode *s) { s-next p-next; // 1. s 先认识 p 的后继 if (p-next) { p-next-prev s; // 2. p 的后继回头认 s } s-prev p; // 3. s 的前驱指向 p p-next s; // 4. p 的 next 指向 s }口诀是“先让 s 认齐前后邻居再让后邻居回头最后让 p 指向 s”。第 1 步和第 2 步必须在 p-next 被覆盖之前完成否则 p 原本的后继就找不到了。有个常见错误写法是把第 1 步漏掉只写后面三步结果 s-next 是野值遍历到 s 之后直接崩。另一个错误是先写p-next s再写p-next-prev s此时 p-next 已经变成 s改的是 s 自己的 prev原后继就永远回不来了。删除节点 p 的代码同样短// 删除 p 节点并释放内存 void remove_node(DNode *p) { if (p-prev) { p-prev-next p-next; } if (p-next) { p-next-prev p-prev; } free(p); }这里有个隐藏问题删除的是头结点时p-prev 为 NULL外部持有的 head 指针会变成野指针。常见做法是让 remove_node 返回新的头结点或者调用方在删除后检查 head 是否等于 p是的话把 head 更新为 p-next。这一点在课设里非常容易踩我先在这里标一句第 5 章再展开细说。3.3 双向循环链表内核链表为什么要绕一圈双向链表再往前一步把最后一个节点的 next 指向头结点、头结点的 prev 指向最后一个节点就成了双向循环链表。它的优势是从任意节点出发都能遍历整条链删除尾节点也能 O(1) 找到它前面的节点。Linux 内核的 list_head 结构就是典型的不带头结点的双向循环链表每个内核对象嵌入这个结构体用它把同类对象串起来管理。但我一般在课设里不会一上来就用双向循环链表。普通双向链表的边界判断是“NULL 就到头了”双向循环链表要判断“回到起点”每次遍历多一层环检测。如果只是为了菜单导航、LRU 缓存这类场景普通双向链表足够只有当业务明确要求“列表尾部之后回到头部”且这个行为是常态比如轮播菜单、环形任务队列才值得用双向循环版本。面试复习时可以两个都写一遍课设交普通版即可避免给自己增加排错负担。4. 双向链表多级菜单从字段映射到可运行的导航代码4.1 菜单导航为什么是双向链表的天然主场多级菜单几乎是每个嵌入式项目和网站后台都会遇到的模块用户用“上”“下”切换同级选项用“确认”进入子级用“返回”回到上级。这个交互模型里天然存在两类关系同级菜单项之间的前后顺序、父子菜单之间的上下级关系。前者正是双向链表最擅长的事——每个节点存 prev 和 next前后移动 O(1)后者则是树形结构的事用 parent 和 child 两个指针表达层级。我之前见过有人用数组加下标实现菜单插入一个新菜单项要把后面所有项后移删除还要缩容代码里到处是 memmove也有人用单链表结果“上一项”这个操作要遍历整个列表因为它没法后退。双向链表多级菜单的核心思路就是用四个指针覆盖四个方向的移动把“上、下、进入、返回”四种操作都变成 O(1)。字段映射关系可以这样理解用户操作菜单行为使用的字段上一项同级往前移动prev下一项同级往后移动next确认 / 进入进入第一个子菜单child返回回到上级菜单parent注意 child 指向的是“第一个子项”而不是当前项本身。一个菜单项可以有多个子项子项之间用 prev/next 串成双向链表菜单项本身通过 child 挂到父级下面。这样一来整个菜单就是“一个树外壳、每个节点内部藏一条双向链表”的组合结构。4.2 节点字段与建树代码横向双链、纵向父子实现双向链表多级菜单第一步是定义节点结构。我会把四个方向的指针放在同一个结构体里再带上 id 和 label 用于界面显示和定位typedef struct MenuNode { int id; // 菜单项 ID char label[32]; // 显示文案 struct MenuNode *parent; // 上级菜单根节点为 NULL struct MenuNode *child; // 第一个子菜单叶子节点为 NULL struct MenuNode *prev; // 同级上一个 struct MenuNode *next; // 同级下一个 } MenuNode;建树分两步先串同级再挂上下级。常见做法是写两个工具函数// 把 list 数组里的 n 个节点串成双向链表 void link_siblings(MenuNode *list[], int n) { for (int i 0; i n; i) { list[i]-prev (i 0) ? list[i - 1] : NULL; list[i]-next (i n - 1) ? list[i 1] : NULL; } } // 把 first_child 作为 parent 的子链表挂接 void attach_child(MenuNode *parent, MenuNode *first_child) { parent-child first_child; for (MenuNode *s first_child; s ! NULL; s s-next) { s-parent parent; } }link_siblings 参数 n 表示这一级菜单项个数函数内部用数组下标直接确定 prev/next简洁且不容易串链。attach_child 里这个 for 循环很关键它遍历整条子链表把每个子节点的 parent 都指向上级而不仅仅是第一个子项。如果只设 first_child-parent那第二个子项返回上级时会拿到野指针。初始化菜单可以这样写MenuNode root {.id 0, .label 主菜单}; MenuNode setting {.id 1, .label 设置}; MenuNode play {.id 2, .label 播放}; MenuNode vol {.id 3, .label 音量}; MenuNode light {.id 4, .label 亮度}; MenuNode *lv1[] {setting, play}; MenuNode *lv2[] {vol, light}; link_siblings(lv1, 2); link_siblings(lv2, 2); attach_child(root, setting); attach_child(setting, vol); attach_child(play, NULL);这里attach_child(play, NULL)明确把“播放”的子项置空避免 malloc 出来的节点里残留野指针。如果你的菜单是运行时动态增删的把静态数组换成逐节点 calloc 即可删除菜单项时被删节点要从两条链上都摘下来之后立刻把它的指针置 NULL防止二次 free。4.3 导航函数与越界策略停在原处还是回绕菜单系统暴露给上层的导航函数应当极薄只做移动不做业务逻辑这样界面层调起来清爽。我一般写成这样MenuNode *nav_next(MenuNode *cur) { return cur-next ? cur-next : cur; } MenuNode *nav_prev(MenuNode *cur) { return cur-prev ? cur-prev : cur; } MenuNode *nav_enter(MenuNode *cur) { return cur-child ? cur-child : cur; } MenuNode *nav_back(MenuNode *cur) { return cur-parent ? cur-parent : cur; }每个函数都有兜底当前项为 NULL 或越界时返回自己界面层可以据此判断“到底了别动”。这个“越界策略”是菜单产品里一个需要提前确认的参数默认停在原处适合大多数设置页另一种策略是回绕——在最后一项按“下”跳回第一项在第一个子项按“返回”跳到最后一个子项。实现回绕时有个性能坑不要写while (cur-prev) cur cur-prev去找同级链表头那是 O(n)。常见做法是在 MenuNode 里额外存一个 first 指针或者由菜单结构体保存当前级别的 head建树时一次性挂好导航时直接 O(1) 拿到。返回操作还有一个产品语义问题按“返回”到底回上级还是回同级前一项这取决于你的产品定义。多数菜单按“返回”是回到 parent但有些遥控器把“返回”映射成“同级上一个”两者不能混在一个函数里。我见过不少翻车案例就是 nav_back 里用了 prev结果用户按两下返回直接跳到了爷级菜单。4.4 四个边界条件空菜单、根节点、叶子节点、删头节点菜单系统里最容易出问题的不是正常路径而是四个边界状态。第一是空菜单root.child 为 NULL此时 nav_enter 返回自身界面应该显示“无子项”而不是继续访问 cur-child-label。第二是根节点parent 为 NULLnav_back 在根节点按返回应当保持原样如果产品要求“在根节点按返回退出菜单”那是应用层的回调逻辑不能在链表层处理。第三是叶子节点child 为 NULL确认键应该被禁用或给出提示音。第四是删除子链的头节点如果删的是第一个子项父节点的 child 要同步指向原链表第二个节点否则整条子链表会从菜单里消失。这四个边界我建议在建树函数里就通过断言兜住而不是等用户实际操作时暴露。比如 assert 根节点的 parent 为 NULL、叶子节点的 child 为 NULL、attach_child 传入的子链表不能夹杂未初始化的 prev/next。菜单系统是一次建树、反复导航前面多一道检查运行时就能少一次莫名其妙的段错误。5. 链表实验与课设的避坑记录现象、原因、解决5.1 循环链表遍历死循环判终条件写错成 p ! NULL现象运行遍历程序后终端卡死CtrlC 都来不及按整个终端假死。原因新手在写 while 条件时习惯性沿用单链表的p ! NULL但循环链表里尾节点的 next 指向头结点根本没有 NULL这个条件永远为真。解决我统一用 do-while 加p ! head判断先执行一次循环体再判断是否回到起点。空表单独处理head-next 指向自身就输出 empty。写成代码是三行CNode *p head-next; do { printf(%d , p-data); p p-next; } while (p ! head);5.2 双向链表删除后回退越界只改了前驱的 next现象删除某个节点后从头部往后遍历一切正常但按 prev 回退时走到了一个已经 free 掉的节点输出乱码甚至崩溃。原因删除代码里只写了p-prev-next p-next漏掉了p-next-prev p-prev。后向链还挂着已删除节点回退时就踩进回收内存。解决删除函数里两边都要断干净。这属于“只修了一条链”的经典问题我建议写完删除立刻写一个一致性校验函数每次操作后跑一遍见 6.1。5.3 约瑟夫环收尾崩溃带头结点版的判终条件不同现象约瑟夫环输出前面大部分人没问题最后剩两个节点时程序崩溃或者输出完删除节点后还多打印一个垃圾值。原因带头结点的循环链表和不带头结点的版本“只剩一个节点”的判断条件不一样。带头结点版里数据节点的 next 指向头结点不是指向自己判断“只剩一个”不能写p-next p不带头结点的版本最后一个数据节点的 next 才指向自己。解决先想清楚自己用的是哪个版本。带头结点版判断p-next head不带头结点版判断p-next p。我实际写约瑟夫环时直接不带头结点语义更清晰。5.4 多级菜单把 parent 和 prev 混用返回按钮跳两层现象菜单在第二级按“返回”直接跳到了根级而不是回到当前项的上一级。原因nav_back 实现里写的是cur-prev而不是cur-parent。当当前项不是该级第一项时pref 是同级的上一项当它是第一项时prev 为 NULL于是跳到了上一级的入口刚好跳两层。解决返回上级必须用 parent 字段同级切换才用 prev。如果产品要求“返回键同级前一项”那就换一个函数名比如 nav_prev不要让返回键同时承担两种语义。5.5 同一份代码本地能跑、换个编译器就崩未初始化指针现象在本地 IDE 里跑得正常提交到在线判题系统或者换一台新电脑编译链表操作随机崩溃有时输出错几次才崩像是“玄学”。原因malloc 出来的节点结构体里prev、next、child 这些指针没有全部初始化里面是堆上的旧数据。本地编译器碰巧分配的内存比较干净换个环境就是随机值。解决创建节点一律用 calloc或者写一个 init_node 函数把每个字段显式置 NULL。free 之后再把指针置 NULL能拦住大部分重复释放问题。链表这类代码指针初始化是最便宜的保险。6. 验证写法与进阶自检函数、内存检查与 LRU 缓存6.1 自检函数返回节点数并校验前后向一致性链表代码最大的问题是不容易直接看出哪里断了。我的习惯是写一个自检函数每次插入、删除后都调用它// 校验双向链表完整性返回节点数-1 表示双向链不一致-2 疑似成环 int verify_dlist(DNode *head) { DNode *p head; int n 0; while (p) { if (p-next p-next-prev ! p) return -1; if (p-prev p-prev-next ! p) return -1; p p-next; if (n 100000) return -2; } return n; }返回 -1 说明前向链和后向链有一处没对上-2 说明链表里有环。上限 100000 可以根据场景调整菜单系统 128 就够内核链表可以调更大。6.2 最小用例集、编译参数与 valgrind 检查我写链表课设时固定跑四个最小用例空链表 veridy 返回 0插入一个节点返回 1插入两个节点再删除一个返回值恢复随机插入 100 个再随机删除 50每次操作后都调用 verify。全部通过后再做内存检查。编译调试用gcc -g -DDEBUG demo.c -o demo然后跑valgrind --leak-checkfull ./demo看到 definitely lost 为 0 才敢交。没有 valgrind 的环境至少保证每次 free 后置 NULL并避免重复 free。这两个动作能挡住大多数内存类翻车。6.3 进阶双向链表加哈希表实现 LRU 缓存验证完基础操作我建议你顺手做一个 LRU 缓存练习哈希表负责 O(1) 定位 key双向链表负责 O(1) 调整最近访问顺序。get 时把节点移到链表头put 时若 key 已存在则更新并移到头部否则插入头部超容量就删链表尾并同步把对应 key 从哈希表删除。这里的血泪经验是删尾节点时只摘链表、忘了删哈希表里的 key下次访问这个 key 会命中一个已 free 的节点轻则脏数据重则重复 free。这比单纯背知识点更能说明双向链表在真实系统里的位置。我自己的习惯是每写完一个操作就调用 verify_dlist最后再 valgrind 扫一遍链表这块基本不会翻车。希望帮到你。本文还有配套的精品资源点击获取