RTT学习-双向链表

一、为什么 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四条语句分别完成C.prev B让原后继节点C的前驱指向BB.next C让B的后继指向CA.next B让A的后继指向BB.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四条语句分别完成C.next B让原前驱节点C的后继指向BB.prev C让B的前驱指向CA.prev B让A的前驱指向BB.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 */ }假设待删除节点为BA - B - C删除后变为A - C B - B执行过程如下C.prev A让后继节点跳过B直接指向AA.next C让前驱节点跳过B直接指向CB.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()。如果链表节点是静态对象、栈对象或嵌入在其他结构体中就不能直接释放该节点地址。七、四个核心操作对比操作核心效果时间复杂度rt_list_init(l)让l-next、l-prev都指向lO(1)rt_list_insert_after(l, n)将n插入l后面O(1)rt_list_insert_before(l, n)将n插入l前面O(1)rt_list_remove(n)将已知节点n从链表摘除O(1)链表的遍历和按条件查找仍然是O(n)。八、把指针操作记成三个模板1. 初始化自己指向自己next self prev self2. 插入先接新节点两侧再替换原连接原来A - C 插入A - B - C插入操作始终需要建立四条连接A.next B B.prev A B.next C C.prev B3. 删除前后节点互连删除节点自环原来A - B - C 删除A - CB 自环对应的核心关系是A.next C C.prev A B.next B.prev B