简介循环链表与双向链表专项讲解PPT适合正在学习数据结构、尤其需要理清线性表链式存储及其变体的学生或开发者。课件从带头结点的链表切入系统梳理循环链表的判断空满条件、双向链表插入与删除的四步指针调整等核心要点并配有集合运算与一元多项式相加的算法应用示例帮助读者脱离死记硬背真正理解底层逻辑。资源为单个PPT文件大小616KB携带方便可直接用于课堂自学或备课参考。已有414人学习查看过该课件内容密度适中重点突出。通过本讲可掌握链式结构的核心操作技巧并结合多项式加法案例体会线性表在实际算法中的落地方式适合作为数据结构课程的配套巩固材料。1. 为什么这两张链表图几乎锁死了系统级代码的骨架能问出循环链表和双向链表区别的人多半已经在代码里撞上了段错误或者被 JDK、Redis、Linux 内核里那些绕来绕去的 next 和 prev 指针搞到失眠。链表不是教学玩具操作系统进程调度、内存分配器里的空闲块管理、Redis 的列表对象底层跑的几乎都是这两个变体的组合。循环链表把尾节点重新指回头节点让绕一圈变成 O(1) 操作双向链表给每个节点多一个 prev 指针让删除节点不再需要找前驱。两者叠加数据结构领域里许多看似复杂的算法约瑟夫环、LRU 淘汰、时间轮就只是指针的几次重新指向。本文假设你会手写单链表但不熟悉这两个变体将从节点布局讲到边界条件再落到可运行的代码和调试方法遇到链表问题时能直接对照排查。2. 双向链表插入与删除时指针的先后次序不能乱双向链表的核心不是多了个 prev 字段那么简单这个字段让删除任意节点的代价从 O(n) 降到了 O(1)。代价是每次插入和删除时需要多维护两条指针关系次序一旦颠倒链表立刻断裂或形成环。2.1 双向链表的节点结构和内存布局先定义最基础的双向链表节点。以下代码以 C 语言为例因为 C 暴露了指针操作的完整细节理解后迁移到 Java、Go、Rust 都只是语法差异。typedef struct dnode { int data; /* 数据域实际工程中可能是任意业务对象 */ struct dnode *prev; /* 指向前驱节点 */ struct dnode *next; /* 指向后继节点 */ } dnode_t;/* 创建一个带头结点的空双向链表 */ dnode_t *list_init(void) { dnode_t *head (dnode_t *)malloc(sizeof(dnode_t)); if (head NULL) return NULL; head-prev head; /* 空表时头结点的前后指针都指向自己 */ head-next head; return head; }注意head-prev head这行这是很多简化实现的写法让头结点自身形成闭环判空条件就统一成了head-next head。不用特殊处理NULL后面会看到这和循环链表是同一个套路。内存布局上每个节点有三个字段连续存储prev和next各占一个指针宽度64 位系统下是 8 字节数据按对齐规则填充。2.2 插入节点的正确次序先连新节点再拆旧链接在pos节点之后插入新节点new_node常见错误是先改pos-next再想回头取旧的后继节点时发现指针已经丢了。标准做法是最先完成新节点的左右链接再去断开旧链接。void insert_after(dnode_t *pos, dnode_t *new_node) { if (pos NULL || new_node NULL) return; /* 步骤1先把新节点的两个指针分别挂到 pos 和 pos 的原后继 */ new_node-prev pos; new_node-next pos-next; /* 步骤2修改原后继节点的 prev让它指回新节点 */ pos-next-prev new_node; /* 步骤3修改 pos 的 next让它指向新节点 */ pos-next new_node; }三步操作的顺序是硬约束步骤 2 必须在步骤 3 之前因为步骤 2 要访问pos-next一旦步骤 3 执行完pos-next就不再是原来的后继节点了。代码里没有专门维护链表长度实际工程中如需要可在结构体里加size_t len插入时len。操作时间复杂度需要访问的指针数量最易出错点在已知节点后插入O(1)4 条先改 pos-next 导致丢失后继在已知节点前插入O(1)4 条和后插镜像对称方向写反删除已知节点O(1)2 条忘了把前驱的 next 接到后继删除值等于某个数的节点O(n)查找到为止没考虑头结点被删2.3 删除已知节点prev 指针的价值在删除场景才完全体现单链表删除节点必须知道前驱节点而双向链表只要拿到目标节点自己就能通过prev定位前驱从而完成删除且不遍历。void remove_node(dnode_t *target) { if (target NULL) return; /* 前提不是头结点或者有额外的保护机制防止删 head */ dnode_t *before target-prev; dnode_t *after target-next; before-next after; /* 前驱直接跨过 target 指向后继 */ after-prev before; /* 后继的 prev 指回前驱 */ target-prev NULL; /* 保险起见把被删节点的指针清空 */ target-next NULL; /* 防止悬垂引用调试时能立刻看出节点已脱离链表 */ free(target); }/* 更严谨的写法考虑 target 是头结点的场景 */ int remove_node_safe(dnode_t *head, dnode_t *target) { if (head NULL || target NULL || head target) return -1; /* 业务上一般不允许删头结点返回 -1 表示参数不合法 */ target-prev-next target-next; target-next-prev target-prev; target-prev target-next NULL; free(target); return 0; }这里的边界条件是很多面试题爱问的点删的是第一个数据节点时target-prev是头结点操作同样成立删的是尾节点时target-next是头结点因为采用了首尾互连的初始化方式after-prev before这行真正更新的是头结点的prev——等等这行会改到头结点吗不会因为采用的是 2.1 节里 head 自环的设计尾节点是最后一个数据节点时它的 next 指向的是 headhead 的 prev 在删除过程中被修正。整个过程不需要判断是不是头以外的情况这就是统一空表设计带来的收益。2.4 用表格对照双向链表和单链表在操作上的差异双向链表的核心收益是删除已知节点的代价从 O(n) 降为 O(1)代价是每个节点多了一个指针内存占用增加了约 33%64 位下从 16 字节变 24 字节。空间换时间在内存动辄几百 GB 的服务器上几乎可以忽略但在嵌入式环境里需要认真权衡。提示C 语言里通过offsetof宏和container_of宏可以把链表节点的 prev/next 嵌进任意业务结构体里不需要让业务结构体本身变成链表节点。这是 Linux 内核的经典做法在第 4 章会直接用到。3. 循环链表判空、遍历终止与约瑟夫环的落地循环链表和单链表的唯一区别是尾节点的next不再指向NULL而是指回头结点或第一个数据节点。这个改动让代码少了一堆if (next NULL)的判空分支但也让遍历的终止条件从指针是否为 NULL变成了指针是否回到了起点。初学者最容易在这里写出死循环。3.1 循环链表的构造与判空条件typedef struct cnode { int data; struct cnode *next; } cnode_t; /* 创建带头结点的循环链表 */ cnode_t *clist_init(void) { cnode_t *head (cnode_t *)malloc(sizeof(cnode_t)); if (head NULL) return NULL; head-next head; /* 唯一的头和尾:自己指向自己 */ return head; } /* 尾部插入节点 */ void clist_append(cnode_t *head, int value) { cnode_t *tail head; /* 先假定 head 就是尾 */ cnode_t *new_node (cnode_t *)malloc(sizeof(cnode_t)); if (new_node NULL) return; new_node-data value; /* 从头开始找尾:尾节点的 next 指向 head */ while (tail-next ! head) { tail tail-next; } new_node-next head; /* 新节点指向头,保持循环 */ tail-next new_node; /* 原尾节点指向新节点 */ }判空条件在循环链表里极简head-next head意为头结点后面没有任何数据节点。这个条件成立时链表为空不成立时至少有 1 个节点。插入时分两种情况空表的尾就是头结点本身while循环一次都不会执行直接挂接非空表则从头遍历到尾再把新节点接上并把尾指针指向head。如果频繁在尾部追加且链表很长每次都遍历到尾部就退化成 O(n) 了。工程上的改进是完全不遍历直接记录tail指针。还有一种更巧的写法是用尾指针代替头指针只用tail一个指针就能同时访问头部tail-next和尾部。3.2 循环链表遍历的终止条件不止一种写法用 do-while 循环遍历时只要p-next ! head就继续但要注意第一轮的条件判断必须在进入循环体之前执行否则空表会漏判。/* 正确的遍历:do-while 保证至少访问一次 */ void clist_traverse(cnode_t *head) { cnode_t *p head-next; /* 跳过哨兵节点,从第一个数据节点开始 */ if (p head) return; /* 空表直接返回 */ do { printf(%d , p-data); p p-next; } while (p ! head); /* 回到头结点说明绕完一圈 */ } /* 错误示范:以下写法会死循环 */ void clist_traverse_wrong(cnode_t *head) { cnode_t *p head-next; while (p-next ! head) { /* 最后一个数据节点的 next head被跳过 */ printf(%d , p-data); p p-next; } /* 且没有输出尾节点更糟的是如果 p 移动到 head 后继续 p-next 就死循环 */ }第二种写法while (p ! head)配合if (p head) return;的预判以及第三种写法for (p head-next; p ! head; p p-next)本质上都是拿哨兵节点当哨位。选择哪种取决于你要不要特殊处理空表场景。遍历循环链表的另一个常见应用是判断链表中是否存在环。因为循环链表本身就是环判断是否有环在这个场景下没有意义但判断一个普通链表里是否出现了环就用快慢指针Floyd 判圈算法让slow每次走一步、fast每次走两步如果两者相遇就说明存在环。3.3 约瑟夫环用循环链表实现是最直观的解法约瑟夫环问题的经典描述N 个人围成一圈从第 1 个人开始报数报到 M 的人出列剩下的人继续从 1 开始报数求最后留下的那个人。数组模拟的每次删除要移动后续元素时间复杂是 O(n^2)用循环链表删除出列节点是 O(1)整体降到 O(n*M)N 很大、M 较小时优势非常明显。int josephus(cnode_t *head, int m) { if (head NULL || head-next head) return -1; cnode_t *p head-next; /* 从第一个数据节点开始报数 */ cnode_t *victim; while (p-next ! p) { /* p-next p 说明只剩一个节点 */ /* 找到报数为 m 的节点的前驱 */ for (int count 1; count m - 1; count) { p p-next; } victim p-next; p-next victim-next; /* 删除 victim */ if (victim head) head head-next; /* 修改头指针的场景 */ free(victim); p p-next; /* 从下一个节点继续报数 */ } int result p-data; free(p); return result; }/* 调用示例:N7, M3, 答案是 4 */ cnode_t *head clist_init(); for (int i 1; i 7; i) clist_append(head, i); int survivor josephus(head, 3); printf(survivor: %d\n, survivor);代码里的for (int count 1; count m - 1; count)是在找报数者的前驱。如果 M1循环条件count 0天然不成立victim 就是 p 本身此时要单独处理 p 逐渐前移的情况如果 M2循环体执行 1 次p 停在报数者的前驱上。为什么是m - 1不是m因为 p 默认指向了第一个报数者走了 m-1 步正好找到第 m 个人。提示糖果面试题里还有个变种每轮删除后从被删节点的下一个节点开始重新报数。上面代码p p-next已经处理了这点如果题目的起点不同只需调整循环次数。3.4 循环链表尾节点的判空是新手最容易出 bug 的地方循环链表中没有NULL所有是否走到尽头的判断都要改为是否回到了头。常见的问题是把单链表里的while (p ! NULL)直接搬过来结果循环链表根本不会自然结束或者是while (p ! head)时p 初始就指向 head空表导致直接跳过循环体在循环外访问 p 时报空指针。建议统一用一个宏来定义遍历边界#define C_LIST_END(p, head) ((p) ! (head))既保证语义清晰也方便后续把链表改成并发安全的版本时统一收口。4. 双向循环链表两个特性叠加后的实际落地与内核级实现把循环链表的尾首相连和双向链表的 prev 指针放在一起得到的结构就是双向循环链表。它同时具备两个方向的 O(1) 插入删除和从任一节点出发可以遍历整个链表的特性。这是教科书里画起来最复杂的图却是工程上用得最普遍的结构。4.1 双向循环链表的插入和删除只需要头结点一个锚点初始化时让head-next head-prev head这个自环既是空表判据也是遍历终止哨兵。插入和删除操作与 2.2 节代码几乎一样唯一的区别是删除最后一个数据节点时head 的 next 和 prev 同时恢复成指向自身完美回到初始状态。typedef struct dclist_node { int data; struct dclist_node *prev; struct dclist_node *next; } dcnode_t; /* 双向环形链表:尾插 */ void dc_append(dcnode_t *head, int value) { dcnode_t *new_node (dcnode_t *)malloc(sizeof(dcnode_t)); if (new_node NULL) return; new_node-data value; /* 尾节点的定义:head-prev 就是双向环形链表的最后一个数据节点 */ dcnode_t *tail head-prev; new_node-next head; /* 新节点的 next 指向头 */ new_node-prev tail; /* 新节点的 prev 指向旧尾 */ tail-next new_node; /* 旧尾的 next 指向新节点 */ head-prev new_node; /* 头的 prev 也指向新节点,保持双向循环 */ }有了头结点做锚点找尾节点就是 O(1) 操作不需要像 3.1 节那样遍历。这是双向循环链表比单向循环链表最大的优势任意方向 O(1) 插入和删除遍历可以正向或反向且没有空指针判断。4.2 用双向循环链表实现一个可复用的 LRU 缓存LRULeast Recently Used缓存淘汰策略在 Redis、CPU Cache、数据库 Buffer Pool 里都有应用。经典实现是哈希表加双向链表的组合哈希表负责 O(1) 查找双向链表负责 O(1) 删除和位置调整。#define CACHE_CAPACITY 8 #define KEY_MAX 1024 typedef struct cache_item { int key; int value; dcnode_t node; /* 内嵌链表节点,而非指针 */ } cache_item_t; static dcnode_t cache_list; /* 头结点,静态分配 */ static cache_item_t *cache_table[KEY_MAX]; /* 哈希表简化版:key 直接作下标 */ /* 访问缓存:命中则把节点移动到链表头部 */ void cache_get(int key) { cache_item_t *item cache_table[key]; if (item NULL) return; /* 未命中 */ /* 把节点从当前位置摘下来 */ item-node.prev-next item-node.next; item-node.next-prev item-node.prev; /* 插到链表头部(head 之后) */ item-node.next cache_list.next; item-node.prev cache_list; cache_list.next-prev item-node; cache_list.next item-node; } /* 插入缓存:超出容量时删除链表尾部节点 */ void cache_put(int key, int value) { if (cache_table[key] ! NULL) { /* 更新已有 key */ cache_table[key]-value value; cache_get(key); /* 顺便提到头部 */ return; } cache_item_t *new_item (cache_item_t *)malloc(sizeof(cache_item_t)); new_item-key key; new_item-value value; cache_table[key] new_item; dcnode_t *tail cache_list.prev; /* O(1) 拿到尾部 */ if (tail ! cache_list) { /* 链表非空才淘汰 */ cache_item_t *old (cache_item_t *)((char *)tail - offsetof(cache_item_t, node)); cache_table[old-key] NULL; tail-prev-next tail-next; /* 从链表摘除尾部 */ tail-next-prev tail-prev; free(old); } /* 头插新节点 */ new_item-node.next cache_list.next; new_item-node.prev cache_list; cache_list.next-prev new_item-node; cache_list.next new_item-node; }代码里用了内嵌节点而不是节点指针这是缓存场景减少一次内存访问的关键设计。offsetof和container_of的配合让业务结构体cache_item_t可以拥有零散的链表指针字段而不是被链表节点包含。缓存容量达到上限时头部是最近使用的尾部是最久未使用的淘汰尾部正好与 LRU 策略匹配。4.3 Linux 内核的 list_head 是双向循环链表的最高水准体现Linux 内核里到处可见的struct list_head就是双向循环链表但它的结构体里只有指针没有数据数据通过container_of宏挂接。这个过程也是嵌入式开发中面试常考的一个点内核链表头本身不存储业务数据它只是一个空转的枢纽。比较项教科书链表Linux 内核 list_head节点是否包含数据包含不含业务结构体内嵌 list_head从节点访问数据直接访问container_of 计算偏移删除操作需要知道什么具体业务节点list_del 只需要传递链表节点双循环是否有特性利用部分是完全依赖双循环特性实现 O(1) 各种操作/* Linux 内核关于 list_head 的核心定义(简化) */ struct list_head { struct list_head *next, *prev; }; static inline void __list_add(struct list_head *new_node, struct list_head *prev, struct list_head *next) { next-prev new_node; new_node-next next; new_node-prev prev; prev-next new_node; } #define container_of(ptr, type, member) \ ((type *)((char *)(ptr) - offsetof(type, member))) #define list_for_each(pos, head) \ for (pos (head)-next; pos ! (head); pos pos-next)list_for_each宏定义的遍历终止条件pos ! head是循环链表灵魂的体现。无论是内核里的定时器管理、进程任务列表还是驱动里的设备队列靠的都是这套循环加双向的组合。理解这套宏之后再看 Redis 的quicklist、JAVA 的LinkedHashMap底层思路完全一致。5. 验证链表实现正确性的三个调试技巧5.1 用链表完整性检查函数在测试阶段自动校验写一个独立的校验函数每次增删后调用能自动检查双向链表的对称性和循环链表的闭环性第一时间暴露指针错误。int check_list(dcnode_t *head) { if (head NULL) return -1; dcnode_t *p head; int count 0; do { /* 双向一致性:每个节点的 next 的 prev 必须是自己 */ if (p-next-prev ! p) { printf(broken at node %d: next-prev mismatch\n, count); return -1; } /* 循环性:从头出发必须能走回自身 */ if (count 0 p head) { printf(loop detection failure\n); return -1; } p p-next; count; } while (p ! head); printf(length%d, validation passed\n, count - 1); return count - 1; /* 减去头结点 */ }校验函数不只是给测试用线上跑关键节点时也可以用条件编译或标记开关来控制是否启用。它能发现两类典型错误插入时少了一条指针赋值或者删除后没有把相邻节点的指针重新对接。5.2 打印指针地址而非只打印数据用 GDB 看链表拓扑调试链表问题时只打印 data 字段看不出结构。打印每个节点的地址、prev 地址、next 地址手工画一张拓扑图很快能定位问题。void debug_print_list(dcnode_t *head) { dcnode_t *p head; int idx 0; do { printf([%d] node%p prev%p next%p\n, idx, p, p-prev, p-next); p p-next; } while (p ! head idx 20); /* 加一个保险,避免打印死循环 */ }5.3 通过断点观察插入/删除执行的现场指针变化在 GDB 里把断点打在head-next被修改的那一行单步观察赋值前后链表的内容变化。双向链表的插入代码执行步骤是对称的先连新节点到后驱再连前驱到新节点。如果调试中发现只有一个方向的指针发生了变化那一定是某一步漏写了。循环链表的死循环问题也可以通过 GDB 的finish命令让程序执行到从函数返回观察是否停不下来结合ctrl-c中断后查看当前的p指向哪就能反推出终止条件写错的位置。本文还有配套的精品资源点击获取