简介：一册讲解带头结点链表、循环链表与双向链表核心概念的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); }

重点说两个参数：m=1 时 for 循环一次都不执行，pre 是上一轮找到的前驱，删除仍然安全；m 大于 n 时，for 循环会绕很多圈，时间复杂度是 O(n*m)，n 在十万以内可以直接用，再大建议改成保留 pre 指针的写法，把内部查找前驱的 O(n) 去掉。这里的“找前驱”循环可能有性能浪费，但胜在逻辑直观，出 bug 的概率低。测试时给 n=7、m=3，输出顺序是 3 6 2 7 5 1 4，跑通这个用例就说明基本逻辑没问题。

3. 双向链表：多一个 prev 指针，换来的是前后双向的可逆操作

3.1 为什么要多存一个 prev：单链表的“复盘困境”

单链表有个天然短板：只能往后走。想回到上一个节点，要么从头重新遍历，要么额外维护一个栈。可现实里到处都是“后退”需求：浏览器后退按钮、编辑器 Ctrl+Z、路由器配置菜单回到上一级，都要求数据结构能双向移动。双向链表在每个节点里多存一个 prev 指针，指向前一个节点，本质上是为“后悔药”付的存储成本。

这个成本在 64 位系统上大约是每个节点多 8 字节，换来的是“给定节点删除”从 O(n) 降为 O(1)。单链表删除一个节点需要从头找到它的前驱；双向链表因为节点自己存了 prev，直接就能拿到前驱。插入操作同理，已知位置双向插入也是 O(1)。但代价不只是内存：插入和删除都要维护两条链，出错概率成倍上升，指针顺序写错，链表当场断成两截或者变成环。下面这张表是我在课设里常用的对比：

实际选型时我会这样判断：如果代码里只有“向后追加”和“从头部弹出”，单链表就够；一旦出现“选中当前项后返回上一项”这类交互，直接上双向链表，不要等后来补 prev 指针，那会比一开始写多费三倍时间。

3.2 插入与删除的指针赋值顺序：口诀与常见错误

双向链表的核心操作就两个：在某个节点之后插入新节点、删除某个给定节点。两段代码都不长，但指针赋值顺序错一个，链表就会从中间断开。先看插入，在 p 之后插入 s：

typedef 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)。

字段映射关系可以这样理解：

注意 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 为 NULL，nav_back 在根节点按返回应当保持原样；如果产品要求“在根节点按返回退出菜单”，那是应用层的回调逻辑，不能在链表层处理。第三是叶子节点：child 为 NULL，确认键应该被禁用或给出提示音。第四是删除子链的头节点：如果删的是第一个子项，父节点的 child 要同步指向原链表第二个节点，否则整条子链表会从菜单里消失。

这四个边界我建议在建树函数里就通过断言兜住，而不是等用户实际操作时暴露。比如 assert 根节点的 parent 为 NULL、叶子节点的 child 为 NULL、attach_child 传入的子链表不能夹杂未初始化的 prev/next。菜单系统是一次建树、反复导航，前面多一道检查，运行时就能少一次莫名其妙的段错误。

5. 链表实验与课设的避坑记录：现象、原因、解决

5.1 循环链表遍历死循环：判终条件写错成 p != NULL

现象：运行遍历程序后终端卡死，Ctrl+C 都来不及按，整个终端假死。原因：新手在写 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-check=full ./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 扫一遍，链表这块基本不会翻车。希望帮到你。

本文还有配套的精品资源，点击获取