企业官网建设流程全解析

一、为什么 RTOS 内核需要双向链表

在 RT-Thread 中，双向链表是组织内核对象的重要基础。链表中的每个节点都保存两个指针：

• next：指向直接后继节点；

• prev：指向直接前驱节点。

与单向链表相比，双向链表可以从任意节点向前或向后遍历。更重要的是，在已经获得目标节点地址的前提下，插入和删除节点都只需要修改固定数量的指针，时间复杂度为O(1)。

需要注意：双向链表并不会让“按值查找”变成O(1)。如果没有目标节点的地址，仍然需要遍历链表，时间复杂度为O(n)。它的优势主要体现在双向遍历以及已知节点位置时的快速插入、删除。

二、RT-Thread 双向链表的结构

课件版本中，链表节点定义在rttypes.h：

/** * Double List structure */ struct rt_list_node { struct rt_list_node *next; /**< point to next node. */ struct rt_list_node *prev; /**< point to prev node. */ }; ​ typedef struct rt_list_node rt_list_t;

rt_list_t既可以表示普通节点，也可以表示链表头。RT-Thread 使用的是循环双向链表，初始化后的头结点满足：

head.next == &head head.prev == &head

可以把空链表理解为头结点的两个指针都绕回自己：

这里的head是哨兵头结点，不存放实际业务数据。它让空链表、首节点和尾节点都能采用统一的指针操作，减少边界条件判断。

三、链表初始化

RT-Thread 提供了宏初始化和内联函数初始化两种方式，课件版本中均定义在rtservice.h。

1. 使用宏初始化

#define RT_LIST_OBJECT_INIT(object) { &(object), &(object) } ​ rt_list_t list = RT_LIST_OBJECT_INIT(list);

这种方式适合在定义链表对象时直接完成初始化。

2. 使用函数初始化

rt_inline void rt_list_init(rt_list_t *l) { l->next = l->prev = l; } ​ rt_list_t list; rt_list_init(&list);

这种方式适合链表对象已经定义，之后再进行初始化的场景。

无论采用哪种方式，本质都是让next和prev指向节点自身。初始化不是可选步骤；未初始化的指针参与插入或删除会导致非法内存访问。

四、在指定节点之后插入

1. 函数实现

rt_inline void rt_list_insert_after(rt_list_t *l, rt_list_t *n) { l->next->prev = n; /* 1 */ n->next = l->next; /* 2 */ l->next = n; /* 3 */ n->prev = l; /* 4 */ }

假设原链表局部关系为：

A <-> C

现在要把新节点B插入A之后，最终关系应变为：

A <-> B <-> C

四条语句分别完成：

1. C.prev = B：让原后继节点C的前驱指向B；

2. B.next = C：让B的后继指向C；

3. A.next = B：让A的后继指向B；

4. B.prev = A：让B的前驱指向A。

关键点是先保存并使用原有连接关系，再改写l->next。如果过早覆盖原指针，就可能丢失节点C的地址。

2. 基本用法

rt_list_t list = RT_LIST_OBJECT_INIT(list); rt_list_t *new_node = rt_malloc(sizeof(rt_list_t)); ​ if (new_node != RT_NULL) { rt_list_insert_after(&list, new_node); }

当参数l是哨兵头结点&list时，rt_list_insert_after(&list, new_node)会把新节点放到链表首部。

五、在指定节点之前插入

1. 函数实现

rt_inline void rt_list_insert_before(rt_list_t *l, rt_list_t *n) { l->prev->next = n; /* 1 */ n->prev = l->prev; /* 2 */ l->prev = n; /* 3 */ n->next = l; /* 4 */ }

假设原链表局部关系为：

C <-> A

将新节点B插入A之前，最终关系为：

C <-> B <-> A

四条语句分别完成：

1. C.next = B：让原前驱节点C的后继指向B；

2. B.prev = C：让B的前驱指向C；

3. A.prev = B：让A的前驱指向B；

4. B.next = A：让B的后继指向A。

2. 基本用法

rt_list_t list = RT_LIST_OBJECT_INIT(list); rt_list_t *new_node = rt_malloc(sizeof(rt_list_t)); ​ if (new_node != RT_NULL) { rt_list_insert_before(&list, new_node); }

由于链表是循环结构，头结点的前驱就是尾节点。因此：

• rt_list_insert_after(&list, new_node)：插入到链表首部；

• rt_list_insert_before(&list, new_node)：插入到链表尾部。

六、删除指定节点

1. 函数实现

rt_inline void rt_list_remove(rt_list_t *n) { n->next->prev = n->prev; /* 1 */ n->prev->next = n->next; /* 2 */ n->next = n->prev = n; /* 3 */ }

假设待删除节点为B：

A <-> B <-> C

删除后变为：

A <-> C B <-> B

执行过程如下：

1. C.prev = A：让后继节点跳过B，直接指向A；

2. A.next = C：让前驱节点跳过B，直接指向C；

3. B.next = B.prev = B：让被删除节点恢复为自环状态。

第三步很有意义：删除后的节点不再保留指向原链表的悬空关系，而且在结构上重新成为一个独立的空链表节点。

2. 删除与释放内存不是一回事

rt_list_remove()只负责把节点从链表中摘除，并不会释放节点占用的内存。

如果节点是动态申请的，可以在摘链后释放：

rt_list_t *del_node = /* 指向链表中的某个动态节点 */; ​ rt_list_remove(del_node); rt_free(del_node); del_node = RT_NULL;

这里要特别区分“对象”和“指针”：

/* del_node 是对象，传入它的地址 */ rt_list_t del_node; rt_list_remove(&del_node); ​ /* del_node 是指针，直接传入指针值 */ rt_list_t *del_node = /* ... */; rt_list_remove(del_node);

只有通过rt_malloc()等接口动态分配的内存，才应交给rt_free()。如果链表节点是静态对象、栈对象，或嵌入在其他结构体中，就不能直接释放该节点地址。

七、四个核心操作对比

链表的遍历和按条件查找仍然是O(n)。

八、把指针操作记成三个模板

1. 初始化：自己指向自己

next = self prev = self

2. 插入：先接新节点两侧，再替换原连接

原来：A <-> C 插入：A <-> B <-> C

插入操作始终需要建立四条连接：

A.next = B B.prev = A B.next = C C.prev = B

3. 删除：前后节点互连，删除节点自环

原来：A <-> B <-> C 删除：A <-> C，B 自环

对应的核心关系是：

A.next = C C.prev = A B.next = B.prev = B