244.1.2C语言_链表理论

struct rt_list_node /* RT-Thread 的双向链表结点类型；它只保存链接关系，不直接保存业务数据。 */
{ /* 结构体定义开始。 */
    struct rt_list_node *next; /* 指向循环链表中的后继结点。 */
    struct rt_list_node *prev; /* 指向循环链表中的前驱结点。 */
}; /* 结构体定义结束。 */
typedef struct rt_list_node rt_list_t; /* 为该结构体取别名 rt_list_t，便于声明链表结点。 */

上面是课程所用 RT-Thread 5.0.2 在 rtdef.h 中的真实定义。rt_list_t 本身只有两个指针，属于侵入式链表结点：应用通常把它嵌入自己的结构体，再通过 rt_list_entry() 从链表结点地址找回所属的业务对象。这样，内核链表接口不需要知道业务结构体里究竟保存了什么。

一、链表

链表由结点和结点间的链接组成。每个结点通常包含业务数据以及一个或多个链接字段；程序沿链接字段访问前驱或后继，而不是像数组那样根据“首地址 + 下标 × 元素大小”定位元素。

需要纠正一个常见的绝对化说法：数组元素必须按元素顺序连续存放；链表结点不要求连续存放，但多个结点也可能碰巧相邻，或来自同一个静态数组。链表的本质是依靠指针建立逻辑顺序，不是“物理地址一定不连续”。链表也不一定依赖动态内存，静态对象同样可以连成链表。

链表可从两个互不冲突的维度分类：

• 单向链表或双向链表：每个结点只有后继链接，还是同时具有后继和前驱链接。
• 线性链表或循环链表：末端链接指向空指针，还是重新连回首结点。

因此，“尾结点的 next 为 NULL”描述的是线性单向链表；“尾结点的 next 指向头结点”描述的是循环单向链表。双向链表也可以是线性的或循环的。课程后半段分析的是 RT-Thread 的双向循环链表。

1.1 例题: 链表与数组比较

数组与链表不能只用“谁更快”概括，它们的成本发生在不同位置：

对比项	数组	链表
内存布局	元素连续，元素大小由类型决定，不一定是 1 字节	结点无须连续，每个结点还要保存链接字段
按下标访问	已知下标时通常为 O(1)	必须沿链接逐个走，通常为 O(n)
已知结点后的插入、删除	往往要移动后续元素，通常为 O(n)	修改少量链接即可，通常为 O(1)
查找插入位置	可按下标直接定位；按值查找仍取决于算法	若只知道值或序号，通常仍要先遍历，成本为 O(n)
CPU 缓存与空间开销	连续访问局部性好，没有每元素链接开销	访问位置分散，链接指针会占空间
容量管理	固定数组容量确定；动态数组扩容时可能搬迁	可逐结点增减，但分配和释放本身也有成本

所以，“链表插入是 O(1)”有一个必要前提：已经拿到了插入位置附近的结点地址。若先从表头寻找第 k 个结点，总成本仍是 O(n)。嵌入式系统还要考虑内存碎片、确定性和并发访问，不能因为链表便于增删就一律动态分配结点。

单向链表从某结点只能直接得到后继；若没有表头或额外信息，就不能直接得到前驱。双向链表用额外的 prev 指针换来反向遍历及已知结点时更直接的删除操作。

链表的基本操作包括初始化、插入、删除、判空、计数和遍历。任何修改都要维持结构不变量。对 RT-Thread 的双向循环链表，任一有效结点 x 都应满足 x->next->prev == x 和 x->prev->next == x。

1.2 例题: RT-Thread工程文件建立

视频在 RT-Thread Studio 中新建名为 02LIST 的工程，选择 STM32F103ZET6，并使用 ST-Link 调试。课程压缩包中的成品工程确实是 rttcode/02LIST，内核版本为 5.0.2，应用入口位于 applications/main.c。

调试器选项应与手里的硬件一致。视频选择的是 ST-Link；工程界面也提供 DAP-Link、J-Link、QEMU 等启动配置，因此不能把“所有人都必须选 ST-Link”理解成 RT-Thread 的通用要求。芯片型号必须与目标板 MCU 完全一致，课程跟做时才选择 STM32F103ZET6。

视频中被转录成“IDC 文件夹”的位置实际是工程的 rt-thread/include。本节查看两个文件：

• rtdef.h 定义 struct rt_list_node 和 rt_list_t。
• rtservice.h 定义初始化、插入、删除、判空、计数及遍历等链表接口。

源码行号会随版本变化，不应把“47 行左右”当作接口位置的一部分。应按符号名搜索，并确认当前工程所用的 RT-Thread 版本。

1.3 例题: rtservice.h函数分析

课程展示的接口名称应准确记为：rt_list_init()、rt_list_insert_after()、rt_list_insert_before()、rt_list_remove()、rt_list_isempty() 和 rt_list_len()。原笔记中的 rt_list_insert、rt_list_is_empty 都不是本工程里的实际名称。

这些接口处理的是 rt_list_t 链接结点，而不是某一种固定的业务数据。业务结构体把 rt_list_t 作为成员嵌入后，可以加入链表；取回业务对象时，再使用 rt_list_entry(node, type, member)。这就是“侵入式”的含义：链接字段属于业务对象本身，不另外分配一个包装结点。

本工程里的链表小函数以 rt_inline 定义在头文件中。在当前编译器配置下，rt_inline 会展开为带内部链接的 static inline 或等价形式。inline 是允许编译器内联展开的语义提示，并不保证每次调用都一定被替换成函数体；是否真正内联仍由编译器决定。

判空和计数的源码如下：

rt_inline int rt_list_isempty(const rt_list_t *l) /* 接收只读链表头，返回非零表示空表。 */
{ /* 判空函数开始。 */
    return l->next == l; /* 空循环链表的后继仍是头结点自身。 */
} /* 判空函数结束。 */

rt_inline unsigned int rt_list_len(const rt_list_t *l) /* 遍历链表并返回头结点之外的结点数量。 */
{ /* 计数函数开始。 */
    unsigned int len = 0; /* 从零开始累计数据结点数。 */
    const rt_list_t *p = l; /* 游标先指向哨兵头结点。 */
    while (p->next != l) /* 后继尚未绕回头结点时，链表中仍有未计数结点。 */
    { /* 循环体开始。 */
        p = p->next; /* 游标前进到下一个结点。 */
        len ++; /* 将刚到达的数据结点计入长度。 */
    } /* 循环体结束。 */

    return len; /* 返回遍历所得长度；该操作的时间复杂度为 O(n)。 */
} /* 计数函数结束。 */

const rt_list_t *l 表示函数不会通过 l 修改结点。rt_list_isempty() 为 O(1)；rt_list_len() 必须绕表一周，为 O(n)。链表损坏而不能回到头结点时，rt_list_len() 可能一直运行或访问非法地址，因此这些接口依赖调用者维护正确链接。

1.4 双向链表的初始化

rt_inline void rt_list_init(rt_list_t *l) /* 初始化以 l 为哨兵头结点的双向循环链表。 */
{ /* 初始化函数开始。 */
    l->next = l->prev = l; /* 先令 prev 指向自身，再把同一地址赋给 next。 */
} /* 初始化函数结束。 */

赋值运算从右向左结合，因此该语句等价于先执行 l->prev = l，再执行 l->next = l->prev。最终 next 和 prev 都指向 l。

这里的 l 通常是哨兵头结点。初始化后链表包含零个数据结点，所以 rt_list_isempty(l) 返回真，rt_list_len(l) 返回 0。图上虽然画着一个 rt_list_t 对象，却不能据此说“表里已经有一个数据块”；哨兵用于标记边界，计数和遍历均不把它当作普通数据结点。

课程后续的 02LIST 示例把 person1->list 同时当作循环起点和一个业务对象的链接成员，这种写法能够运行，但容易混淆“哨兵”与“数据结点”。阅读 RT-Thread 内核代码时，先确认传入的 l 是专用表头，还是某个实际对象的链接成员。

1.5 双向链表的插入

1.5.1 链表插入的基本概念与变量介绍

rt_list_insert_after(l, n) 把新结点 n 插到已有结点 l 后面。设插入前 s = l->next，完成后局部顺序应为 l <-> n <-> s。这里的 l 是定位点，n 才是待插入结点；原笔记“l 表示要被插入的节点”容易把两者角色说反。

调用前应满足：l 已属于一个有效链表，n 还没有链接在别的链表中。若把同一个 n 重复插入却不先移除，原链表会被破坏。接口自身不检查空指针、重复插入或并发修改。

1.5.2 链表插入的图形解析

不要只背四行赋值，可先画出三个对象：前驱 l、旧后继 s、新结点 n。插入前有两条关系：l->next == s、s->prev == l；插入后要得到四条关系：

• l->next == n
• n->prev == l
• n->next == s
• s->prev == n

代码顺序很关键。前两行仍需要读取旧的 l->next，所以要在第三行改写 l->next 之前保存并更新旧后继关系。函数执行中间，链表不变量可能暂时不成立；四条赋值全部完成后才恢复一致。

1.5.3 链表插入的代码解析

rt_inline void rt_list_insert_after(rt_list_t *l, rt_list_t *n) /* 把 n 插入到 l 之后。 */
{ /* 后插函数开始。 */
    l->next->prev = n; /* 让旧后继 s 的 prev 改为指向新结点 n。 */
    n->next = l->next; /* 让 n 的 next 指向旧后继 s；此时 l->next 仍未改写。 */

    l->next = n; /* 让 l 的 next 从旧后继 s 改为指向 n。 */
    n->prev = l; /* 让 n 的 prev 指回 l，至此四条双向链接全部闭合。 */
} /* 后插函数结束。 */

原笔记把第一行写成了 n->prev = l->next->prev，这不是视频或源码中的语句。真实第一行是 l->next->prev = n：赋值目标是旧后继的 prev 字段。左右两边颠倒会得到完全不同的效果。

该算法即使在空表头后插入也成立。初始化时 l->next == l，四条赋值完成后形成 l <-> n <-> l 的双向环，表中有一个数据结点。

1.6 双向链表的插入

本标题与上一节重复，可把这一节用于补全视频略过的“在前面插入”。rt_list_insert_before(l, n) 把 n 放到 l 前面：

rt_inline void rt_list_insert_before(rt_list_t *l, rt_list_t *n) /* 把 n 插入到 l 之前。 */
{ /* 前插函数开始。 */
    l->prev->next = n; /* 让旧前驱的 next 改为指向新结点 n。 */
    n->prev = l->prev; /* 让 n 的 prev 指向旧前驱；此时 l->prev 仍是旧值。 */

    l->prev = n; /* 让 l 的 prev 改为指向 n。 */
    n->next = l; /* 让 n 的 next 指向 l，完成双向链接。 */
} /* 前插函数结束。 */

在哨兵头结点 head 前插入，等价于追加到循环链表尾部；在 head 后插入，则等价于放到表首。这正是循环链表用一个头结点统一处理首尾边界的便利之处。

1.7 双向链表的删除

1.7.1 双向链表删除的原理

设待删除结点为 n，其前驱为 p = n->prev，后继为 s = n->next。删除的目标是让 p 与 s 直接相连，即 p->next = s、s->prev = p，随后把 n 的两个链接恢复为自指状态。

删除链表结点只解除链接，不会释放包含它的业务对象。若对象来自动态内存，调用者还要在确保无人继续引用后，用与分配方式匹配的接口释放对象。反过来，若对象仍在链表中就先释放，会留下悬空指针。

1.7.2 双向链表删除的代码逻辑

rt_inline void rt_list_remove(rt_list_t *n) /* 从当前双向循环链表中摘除结点 n。 */
{ /* 删除函数开始。 */
    n->next->prev = n->prev; /* 让后继结点的 prev 越过 n，直接指向 n 的前驱。 */
    n->prev->next = n->next; /* 让前驱结点的 next 越过 n，直接指向 n 的后继。 */

    n->next = n->prev = n; /* 把已摘除结点恢复为自指，便于识别其当前不在原链表中。 */
} /* 删除函数结束。 */

执行完前两行，原链表已经绕过 n；最后一行只整理被摘除结点自身，不负责释放内存。不要对专用哨兵头结点调用该函数，否则会丢失从头结点到原数据结点的可达关系。多个线程或中断同时修改同一链表时，还必须使用适合上下文的锁或临界区，单靠这三行赋值不具备并发安全性。

1.7.3 双向链表删除后的判断

删除后若要判断整张表是否为空，应把头结点传给 rt_list_isempty(head)，判断 head->next == head。检查刚删除的 n 只会发现它已经自指，不能证明原链表为空，因为原表里可能还有其他结点。

以 head <-> A <-> B <-> head 为例，删除 A 后得到 head <-> B <-> head，此时原表仍非空，而 A->next == A。这正是必须区分“被摘除的结点已隔离”和“整张链表没有数据结点”的原因。

完成本节后，应能不看源码画出插入和删除前后的四条链接，并能解释：为什么空表头的 next、prev 都指向自身；为什么 rt_list_len() 不计头结点；为什么删除结点不等于释放对象；以及第一行 l->next->prev = n 的赋值目标究竟是谁。