企业官网建设流程全解析

简介：循环链表与双向链表专项讲解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++。

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 指向的是 head，head 的 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; }

/* 调用示例:N=7, M=3, 答案是 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++)是在找报数者的前驱。如果 M=1，循环条件count < 0天然不成立，victim 就是 p 本身，此时要单独处理 p 逐渐前移的情况；如果 M=2，循环体执行 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 缓存

LRU（Least 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 的核心定义(简化) */ 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指向哪，就能反推出终止条件写错的位置。

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