简介面向数据结构初学者与算法爱好者该课件系统讲解带头结点链表、循环链表和双向链表的存储特征与基本运算。内容突出循环链表空满条件的判断以及双向链表插入、删除算法中指针更新的关键细节并借助清晰的图示与多项式加法实例展示线性表在实际问题中的典型应用。资源共1个演示文稿文件压缩包大小约616KB结构紧凑非常适合用于课堂教学、自学复习或考前快速梳理。目前已有415人学习浏览。通过本课件学习者可以快速理解几种链表变体的设计动机与操作差异掌握从单链表到循环、双向链表的扩展思路并领会线性表在集合运算、多项式表示与合并同类项等场景中的落地方法为后续算法学习打下扎实基础。1. 循环链表和双向链表为什么我劝你别只背“增删改查”每次聊到链表我都会先问一句你除了“增删改查”真的把指针理清过吗这份资源是《数据结构与算法》第五讲主题是循环链表和双向链表还带着带头结点的链表特征、基本运算以及两个线性表应用示例——集合运算和一元多项式加法。适合两类人一类是写了几年业务代码却被面试里“链表翻转”“判断环”问住的老开发另一类是刚学完顺序表、想通过手写链表加深理解的初学者。它的价值不在概念多深而在于把几个最容易被忽略的细节讲透头结点到底要不要存数据、循环链表怎么判空判满、双向链表插入时先动哪根指针。2. 带头节点的链表头节点不存业务数据为什么反而更好用2.1 头节点的两个作用存表信息和统一算法处理PPT 在第 5.1 节里点了一句核心在线性链表的第一个结点前面增设一个特殊结点称为头结点。它逻辑上不属于线性链表作用有两个一是存一些线性表相关的信息最典型的就是把链表长度存进头节点的数据域二是让算法处理更统一不必针对“第一个位置插入”和“删除第一个节点”单独写分支。没接触过头节点的读者可能觉得多一个节点是浪费。实际写代码时不带头节点的链表在表头插入时必须修改头指针本身代码里经常出现head newNode删除第一个节点时还要head head-next。这很容易在函数传参时出问题尤其是 C 语言里用形参传指针你在函数内部改了头指针外部却还是旧地址随之而来的就是访问野指针。带头节点后head永远不换插入和删除只要找到前驱改前驱的next就行全程没有“头指针被搬走”的危险。2.2 带头节点链表的插入删除代码骨架与参数说明PPT 给的插入删除思路和普通链表基本一致只是多了一个永不变化的头节点。我建议入门阶段这样写#include iostream using namespace std; struct Node { int data; Node* next; Node(int v 0, Node* n nullptr) : data(v), next(n) {} }; // 带头节点的链表head-data 用来存链表长度 class HeadedList { private: Node* head; public: HeadedList() : head(new Node(0, nullptr)) {} // 在逻辑位置 pos从 0 开始前插入值为 value 的节点 void insert(int pos, int value) { Node* pre head; // 从头节点开始找前驱 int i 0; while (pre-next ! nullptr i pos) { pre pre-next; // pre 停在待插入位置的前一个节点 i; } Node* cur new Node(value, pre-next); pre-next cur; head-data; // 每插入一个节点长度加 1 } // 删除逻辑位置 pos 上的节点 void remove(int pos) { Node* pre head; int i 0; while (pre-next ! nullptr i pos) { pre pre-next; i; } if (pre-next nullptr) return; // 位置越界 Node* del pre-next; pre-next del-next; delete del; head-data--; // 删除后长度减 1 } int length() const { return head-data; } };代码里的pre始终是目标节点的前驱。插入时先执行new Node(value, pre-next)让新节点的next指向原后继再把pre-next指向新节点这一步不能反反了会丢掉整段后继链表。删除时用pre-next跳过被删节点最后delete释放内存。pos传 0 时就是在第一个真实节点前插入但这段代码完全没有针对pos 0写额外分支这就是头节点的意义逻辑统一边界消失。有个参数细节值得强调。insert里允许pos等于当前长度这时插入在尾部remove里如果pos超过长度pre-next已经是nullptr直接return避免误删。养成“先判后动”的习惯能少写很多野指针排查代码。另一个问题是头节点用data存长度后插入删除都必须记得更新漏一次就会导致length()返回错误值。2.3 头指针、头节点、首元节点三个易混概念我在代码评审时见过不少人图能画对一上机就卡住。这三个词必须分清头指针是指向链表第一个节点的指针变量保存的是地址头节点是第一个节点之前的那个特殊节点数据域通常不存业务数据首元节点是真正存放第一个业务数据的节点。带头节点的链表里头指针指向头节点头节点指向首元节点。常见翻车是把头节点当真当成“第 0 个数据节点”遍历时从head开始输出把head-data里的长度也打印了出来。正确遍历应该从头节点下一个节点开始也就是head-next。还有一个容易混淆的点删除首元节点后如果链表变空带头节点的链表里head-next nullptr但head本身还在不带头节点的链表变空时头指针必须置nullptr。两种形态的“空”长得完全不一样写代码前先想清楚自己用的是哪一种。3. 循环链表判空判满和遍历终止条件是核心考点3.1 循环链表为什么成环最后一个节点指向哪里PPT 对循环链表的定义很简洁把第一个节点视为最后一个节点的后继把最后一个节点视为第一个节点的前趋整个链表就形成一个环。放到单链表上就是最后一个节点的next不再置nullptr而是指回第一个节点。如果是带头节点的循环链表最后一个节点指向头节点头节点又指向第一个真实节点。这个结构最大的好处是从链尾走到链头很方便。想象一个轮询任务队列处理完队尾任务马上要回到队头重新开始循环链表天然满足不需要从头遍历也不需要额外保存头指针。缺点也很直接链表没有明显的尾端如果你的遍历终止条件还按单链表写curr-next ! nullptr循环永远不结束程序会卡死在遍历里。为什么 PPT 特别强调“带头节点的循环链表”因为带不带头节点判空条件不一样。不带头节点时空表是头指针本身为nullptr遍历时要先保存首元节点地址终止条件写成curr ! first。带头节点时空表是head-next head也就是头节点的next指向自己遍历终止条件统一成curr ! head语义更好理解。3.2 遍历和插入删除的终止条件把 NULL 换成 head循环链表的插入删除算法主体和单链表几乎一样差别在查找终止条件。单链表用空指针判断“走到头了”循环链表必须用“回到头节点”判断。最常用的带头节点写法如下#include iostream using namespace std; struct CNode { int data; CNode* next; CNode(int v 0, CNode* n nullptr) : data(v), next(n) {} }; // 创建空循环链表头节点指向自己 CNode* createCircularList() { CNode* head new CNode(); head-next head; // 空表特征头节点的 next 指向自己 return head; } // 判空头节点的 next 是否还是自己 bool isEmpty(CNode* head) { return head-next head; } // 遍历带头节点的循环链表终止条件 curr head void traverse(CNode* head) { CNode* curr head-next; while (curr ! head) { // 回到头节点说明转了一圈 cout curr-data ; curr curr-next; } cout endl; }关键就那一行while (curr ! head)。如果照抄单链表的while (curr ! nullptr)编译器不会报错程序也不立刻崩溃表现就是进程一直转圈CPU 占用率被拉满。用调试器看堆栈时只会看到同一个函数反复进出非常磨人。解决办法就是把循环链表的终止条件统一改成“回到头节点”。在插入删除时循环链表还有一个单链表没有的坑查找第pos个节点时如果位置越界单链表可以用pre-next nullptr判断循环链表不会遇到nullptr而是会绕回到头节点。所以循环链表查找时不能用“后一个节点是否为空”判断越界而要在移动前先判断pre-next ! head。这个细节在 PPT 里只有一句话但实际写错的人非常多。3.3 定长循环队列的空满判断一个空格子的代价PPT 里提到“循环链表要掌握判断链表空满的条件”这里必须展开说一句链式循环链表其实没有“满”的概念只要内存够想加多少节点都行。“空满判断”真正高频出现的场景是用数组模拟的循环队列。数组长度固定front和rear都是下标队列空时front rear。但如果数组塞满rear绕一圈追上frontfront rear又会成立空和满就变得无法区分。标准解法是故意浪费一个存储位让永远有一个空格子作为缓冲class CircularQueue { private: int* arr; int capacity; int front; // 队头下标 int rear; // 队尾下标指向下一个写入位置 public: explicit CircularQueue(int cap) : capacity(cap), front(0), rear(0) { arr new int[cap]; } bool isEmpty() const { return front rear; } bool isFull() const { // 留一个空位否则空和满都是 front rear return (rear 1) % capacity front; } void push(int val) { if (isFull()) return; arr[rear] val; rear (rear 1) % capacity; } int pop() { if (isEmpty()) return -1; int val arr[front]; front (front 1) % capacity; return val; } };capacity如果是 5实际最多只能存 4 个元素。判断满用(rear 1) % capacity front判断空用rear front。要多说一句的是这个代价在 Linux 内核的环形缓冲区、消息队列实现里都很常见有的实现用加一个“计数变量”的方式区分空满有的用“放弃一格”的方式。看到 PPT 里的“判空判满”先搞清楚它说的是链式还是数组实现链式场景判满没有意义数组场景判空判满才是考点。4. 双向链表插入删除的指针顺序错一步就丢链4.1 节点结构更长换来的是反向遍历和 O(1) 找前驱双向链表节点在图上通常是prior | info | next三部分info存数据next指向后继prior指向前驱。相比单链表每个节点多了一个指针存储成本上去了换来两个能力一是可以从任意节点向前遍历二是删除任意节点时不需要从头找前驱。单链表要删除节点 p必须知道 p 的前驱封装deleteNode(p)时只能从头遍历来定位双向链表里p-prior就在手边算法简洁很多。工程上标准库的std::list做成双向链表正是因为在插入删除频繁的场景双向链表任意位置操作的复杂度稳定在 O(1)。这不是说你随时都应该手写链表但只有理解底层机制才能解释清楚为什么std::list的迭代器在插入后不失效、为什么它的内存不连续。后面讲的“双向链表多级菜单”应用本质上也是在用prior和next做前后导航用parent指针做返回路径。4.2 在节点 p 之前插入 q四步指针赋值的先后顺序PPT 给的插入片段是经典的四步代码骨架如下struct DNode { int info; DNode* prior; DNode* next; }; // 在节点 p 之前插入节点 q void insertBefore(DNode* p, DNode* q) { q-next p; // 1. q 的后继指向 p q-prior p-prior; // 2. q 的前驱指向 p 的原前驱 p-prior-next q; // 3. p 的原前驱的后继指向 q p-prior q; // 4. p 的前驱指向 q }很多初学者背口诀“先改 q再改 p”这句话对但不精确。第 2 步的p-prior必须在第 4 步之前读取否则第 4 步一改原来的前驱节点就找不回来了。第 1 步和第 2 步的顺序可以交换因为改的都是 q 自己的字段第 3 步要在第 2 步之后才安全因为它必须用到p-prior指向的旧前驱第 4 步必须放到最后因为它会真正覆盖p-prior。插入后如果反向遍历乱序或者链表出现环多半是第 3、4 步写反了。举例说明先执行p-prior q再执行p-prior-next q此时p-prior已经是 q 自己后一条语句等价于q-next q链表直接自环。这种问题在调试器里看到的是指针指向了自己段错误都不报进程却打转排查成本很高。4.3 删除节点 p两个指针域变化边界别漏删除比插入简单只涉及两个指针// 删除节点 p void eraseNode(DNode* p) { if (p-prior ! nullptr) { p-prior-next p-next; // 前驱的后继跳过 p } if (p-next ! nullptr) { p-next-prior p-prior; // 后继的前驱跳过 p } delete p; }第一行让p-prior直接指向p-next第二行让p-next的prior指回p-prior。把 p 摘除前后画一张图两条线的变化非常直观。边界条件是 p 没有前驱或没有后继时两个 if 缺一不可。忘记判断next删除尾部节点时会对空指针执行-prior直接段错误忘记判断prior删除头节点时会写坏头指针。生产环境里用裸指针手写双向链表容易漏delete或留下悬空指针真正在业务里实现菜单、缓冲区功能时我更建议用std::list或std::vector。手写链表的意义在于考试、面试和底层原理理解这两件事要分清场合。练习手写链表时可以用 AddressSanitizer 或 Valgrind 检查内存错误能省掉大量无头绪的排查时间。5. 从集合运算到多项式加法线性表应用中的常见问题排查5.1 集合运算 DiDiff伪代码的索引偏移与返回值语义PPT 第 5.4 节给出了一个对称差(A-B)∪(B-A)的算法思路扫描 B 中的每个元素如果它也在 A 中就从 A 删除如果不在就插入到 A。这是在线性表上做集合运算的经典入门但课件伪代码里隐藏了一个很容易翻车的索引问题Locate返回的是下标位置而Delete需要的却是逻辑序号两者常常差 1因为顺序表下标从 0 开始。我按自己的实现习惯把这段改成可运行的 C11 版本避免被课件里的位置偏移干扰#include vector using namespace std; // 在顺序表 a 中查找 value返回下标找不到返回 -1 int locate(const vectorlong a, long value) { for (size_t i 0; i a.size(); i) { if (a[i] value) { return static_castint(i); } } return -1; } // 计算 (A-B)∪(B-A)结果直接保存在 A 中 // 返回值统一为“从 A 中删除的元素个数” int symmetricDifference(vectorlong a, const vectorlong b) { int removedCount 0; for (long val : b) { int pos locate(a, val); if (pos 0) { a.erase(a.begin() pos); // 元素在 A 中删除 removedCount; // 删除计数 1 } else { a.insert(a.begin(), val); // 不在 A 中插入到表头 } } return removedCount; }原伪代码在 if 分支里j--else 分支里j最后返回 j。可是注释写的是“返回从 a 中删除的元素的数目”这个 j 的语义根本对不上删除时减一插入时加一返回值混入了插入的数量。我第一次照抄课件复现时单元测试直接挂掉后来改成单独维护removedCount才通过验证。另一个坑是插入位置。原伪代码的Insert(b.Get(i), 1)表示插入到表的第 1 个位置也就是表头。插入到表头本身不影响当前对 B 的遍历却会导致 A 的链表头不断变化后续每次locate都要重新扫描性能明显下降。数据量小无所谓数据量上来以后这个设计会拖慢整个程序。5.2 多项式加法指数比较、同类项合并与节点摘除PPT 最后给了一元多项式加法把B(x)加到A(x)上。多项式每个节点存系数和指数并且规定已经合并过同类项、不保留零系数项、各项按指数升序排列。这样两个多项式链表都是有序链表加法本质就是有序表合并指数相同就合并系数指数不同就原样接上。下面这段是按带头节点非循环链表写的核心函数#include iostream using namespace std; struct PolyNode { float coef; // 系数 int exp; // 指数 PolyNode* next; PolyNode(float c, int e, PolyNode* n nullptr) : coef(c), exp(e), next(n) {} }; // 将 B 多项式合并进 AB 链表合并后被拆空 void addPoly(PolyNode* A, PolyNode* B) { PolyNode* p A-next; // p 指向 A 当前节点 PolyNode* pPrev A; // p 的前驱初始是 A 的头节点 PolyNode* q B-next; // q 指向 B 当前节点 while (p ! nullptr q ! nullptr) { if (p-exp q-exp) { // A 的指数小p 本身就在结果里直接前进 pPrev p; p p-next; } else if (p-exp q-exp) { // B 的指数小把 q 摘下来插到 A 中p 之前 PolyNode* qNext q-next; q-next p; pPrev-next q; pPrev q; // 插入后 q 成为新的前驱 q qNext; } else { // 指数相等合并同类项 p-coef q-coef; if (p-coef 0) { // 和系数为 0从 A 中删除 p pPrev-next p-next; delete p; p pPrev-next; } else { pPrev p; p p-next; } // 无论 p 是否被删q 都要从 B 中摘掉 PolyNode* qNext q-next; delete q; q qNext; } } // 如果 B 还剩节点整体接到 A 尾部 if (p nullptr q ! nullptr) { pPrev-next q; } }这段代码有三个易错点。第一个是p-exp q-exp分支q 被插进 A 链表后pPrev必须立刻更新成 q因为下一轮 p 还在原地它的前驱已经换成 q 了漏掉这一步后续插入会串位。第二个是系数相加为 0 时p 已经被delete不能再写p p-next否则访问的是悬空指针正确做法是用pPrev-next作为新的 p。第三个是合并完成后B 的节点要么搬到 A要么被释放B 链表不再独立存在。如果业务要求保留 B需要对节点做值拷贝再插入那套逻辑复杂一个量级。5.3 三个高频翻车现场现象、原因、解决这里记录我复现课件代码时三次真实的排查过程每条都按当时的排查路径写。第一循环链表遍历死循环。现象程序打印到固定位置后不再往下走CPU 占用接近 100%调试器堆栈里只有一个函数反复入栈。原因遍历终止条件写成了curr-next ! nullptr把单链表习惯带到了循环链表上循环链表最后一个节点的 next 指向头节点永远不会为空。解决把终止条件改成curr ! head无头节点版本则保存首元节点地址后比较curr ! first。从那以后我写循环链表遍历会先注释掉所有业务逻辑把遍历骨架单独跑通再填内容。第二双向链表插入后反向遍历乱序。现象在 p 之前插入 q 后从链表尾部向前遍历q 出现的位置错误某些节点被重复访问。原因插入四步里第 2 步和第 4 步乱序p-prior被提前覆盖原来的前驱节点丢失所有反向引用跟着错。解决严格按q-nextp、q-priorp-prior、p-prior-nextq、p-priorq的顺序执行第 2 步没有读完旧前驱前绝不让p-prior被改动。之后我写完插入函数都会对照 PPT 的图把四步标成 (1)(2)(3)(4) 再提交。第三DiDiff 照抄伪代码后结果差一个元素。现象同一组数据手算集合对称差和程序输出不一致删除数量少了 1。原因顺序表删除元素后后续元素下标前移而 for 循环没有同步调整 i跳过了下一个待检查元素。解决删除逻辑里每次重新定位实际下标或者从后往前扫描让删除动作不干扰遍历进度。这段经历让我养成了一个习惯写删除类循环第一件事就是确认下标会不会因为元素前移而后错。6. 用双向链表做多级菜单导航一次验证内功的实战6.1 多级菜单的数据结构设计与导航逻辑把 PPT 里双向链表的插入删除放到真实场景里验证我推荐做一个小项目多级菜单导航。很多轻量设备的按键菜单、嵌入式显示界面、命令行交互界面都是用双向链表把同级菜单项串起来再给每个节点挂一个子链表。这种结构就是典型的“双向链表多级菜单”同一层内用next和prev横向移动跨层用child和parent纵向进出。#include string #include iostream struct MenuItem { std::string title; // 菜单显示文本 MenuItem* prev; // 同级上一个 MenuItem* next; // 同级下一个 MenuItem* parent; // 返回上一级 MenuItem* child; // 当前节点的子菜单链表头 MenuItem(const std::string t) : title(t), prev(nullptr), next(nullptr), parent(nullptr), child(nullptr) {} }; // 进入子菜单没有子节点则停留在当前 MenuItem* enterSubmenu(MenuItem* cur) { return (cur cur-child) ? cur-child : cur; } // 同级移动delta 为 -1 表示上一个1 表示下一个 MenuItem* moveSibling(MenuItem* cur, int delta) { if (delta 0 cur-prev) return cur-prev; if (delta 0 cur-next) return cur-next; return cur; } // 返回上一级没有父节点则停留在当前 MenuItem* backToParent(MenuItem* cur) { return (cur cur-parent) ? cur-parent : cur; }这里enterSubmenu和backToParent是纵向的两条路正好对应节点上的child和parent指针moveSibling是横向的两条路对应prev和next。完整菜单系统里只需要维护一个“当前所在节点”的指针按键事件调用这三个函数之一再重绘界面菜单层级就自然展开了。6.2 菜单系统的验证方法与边界处理写完不要用肉眼盯着屏幕觉得没问题我的习惯是构造三层菜单用断言检查指针的一致性。void checkConsistency(MenuItem* listHead) { MenuItem* cur listHead; while (cur) { if (cur-prev) cur-prev-next cur; if (cur-next) cur-next-prev cur; cur cur-next; } }这段不是生产里的修复逻辑而是把双向链表的对称性当成不变量来检查每个节点的prev和next必须互相指向对方。然后重点测三个边界第一个菜单项按“上”不能飞出菜单最后一个按“下”不能飞出根菜单按“返回”不能崩溃。我第一次做这个项目时赶功能没做一致性检查结果在“返回上一级”漏了更新 parent 的 next 指针菜单从第二层回第一层时第一层直接丢了两个菜单项。从那以后我每次写完链表操作都强制走一遍对称性检查和越界测试几行断言能拦住九成手写指针的翻车。希望帮到你。本文还有配套的精品资源点击获取