双向链表结构 链接到标题
Zephyr 双向链表实现在下列文件中：zephyr/include/zephyr/sys/dlist.h。
Zephyr 以 sys_dlist_t 存储双向链表数据 ( 即每个链表元素存储指向下一个和上一个元素的指针 ) 。与单向链表有专门的链表结构不同，双向链表直接使用节点数据结构作为链表结构：
/** @cond INTERNAL_HIDDEN */
struct _dnode {
union {
struct _dnode *head; /* 用作 sys_dlist_t 时，指向链表头 */
struct _dnode *next; /* 用作 sys_dnode_t 时，指向下一个节点 */
};
union {
struct _dnode *tail; /* 用作 sys_dlist_t 时，指向链表尾 */
struct _dnode *prev; /* 用作 sys_dnode_t 时，指向前一个节点 */
};
};
/**
- @brief Doubly-linked list structure.
*/
typedef struct _dnode sys_dlist_t;
/**
- @brief Doubly-linked list node structure.
*/
typedef struct _dnode sys_dnode_t;
双向链表的结构如下图：
这种结构在链表任意位置插入删除的时间复杂度都是 O ( 1 ) 。
API 对应 链接到标题
双向链表的大多数操作和单向链表相同，可以直接参考单链表的使用:
节点空间应该由用户分配，通常是嵌入到用户容器节点的结构中
struct container_node {
sys_dnode_t node;
void *data;
};
struct container_node *msg = malloc ( sizeof ( struct container_node )) ;
通过访问用户节点成员 msg->node 访问链表节点，当有链表节点 node 时 可以使用 SYS_DLIST_CONTAINER 获取用户节点:
sys_dnode_t *list_node = sys_dlist_get ( &test_list ) ;
struct container_node *msg = SYS_DLIST_CONTAINER ( list_node, msg, node ) ;
其他API对应，功能一致，有个别API不太一样（加粗标识）：
sys_dlist_init ( )：sys_slist_init ( )初始化链表sys_dlist_prepend ( )：sys_slist_prepend ( )在链表头部添加节点sys_dlist_append ( ) ``sys_slist_append ( )在链表尾部添加节点sys_dlist_insert ( ) ``sys_slist_insert ( )指定节点前插入新节点，单向链表是在指定节点后插入新节点sys_dlist_remove ( ) ``sys_slist_remove ( )删除指定节点， 单向链表是删除指定节点后的节点sys_dlist_peek_head ( ):sys_slist_peek_head ( )读取链表头节点sys_dlist_peek_tail ( ):sys_slist_peek_tail ( )读取链表尾节点sys_dlist_peek_next ( ):sys_slist_peek_next ( )读取指定节点的下一个节点sys_dlist_is_empty ( ):sys_slist_is_empty ( )判断链表是否为空sys_dlist_get ( ):sys_slist_get ( )取出链表头节点sys_dlist_len ( ):sys_slist_len ( )获取链表长度SYS_DLIST_STATIC_INIT:SYS_SLIST_STATIC_INIT静态初始化链表SYS_DLIST_FOR_EACH_NODE:SYS_SLIST_FOR_EACH_NODE遍历链表节点SYS_DLIST_FOR_EACH_NODE_SAFE:SYS_SLIST_FOR_EACH_NODE_SAFE安全遍历链表节点SYS_DLIST_FOR_EACH_CONTAINER:SYS_SLIST_FOR_EACH_CONTAINER遍历链表容器节点SYS_DLIST_FOR_EACH_CONTAINER_SAFE:SYS_SLIST_FOR_EACH_CONTAINER_SAFE安全遍历链表容器节点
以上 API 在单向链表中都有对应的 API，使用方法可以参考 Zephyr 内核数据结构 单向链表 一文
无对应 API 链接到标题
以下API是双向链表特有：
sys_dlist_peek_prev读取指定节点的前一个节点sys_dnode_is_linked检查节点是否在链表中sys_dlist_insert_at在特定位置插入节点
以上 API 中前两个很简单，参考头文件中说明即可，现在说明第三个：
static inline void sys_dlist_insert_at ( sys_dlist_t *list, sys_dnode_t *node,
int ( *cond ) ( sys_dnode_t *node, void *data ) , void *data )
在链表 list 中，但节点 pos 的数据和 data 满足 cond 计算的条件时，将 node 节点插入到 pos 后。示例如下
struct container_node {
sys_dnode_t node;
void *data;
};
static sys_dlist_t test_list;
static struct container_node test_node_1;
static struct container_node test_node_2;
static struct container_node test_node_3;
static struct container_node test_node_4;
//匹配函数就是将 data 和链表中节点地址比较，相同则匹配
int cond ( sys_dnode_t *node, void *data )
{
return ( node == data ) ? 1:0;
}
void main ( void )
{
//初始化双向链表
sys_dlist_init ( &test_list ) ;
//向双向链表中加入三个节点
sys_slist_append ( &test_list, &test_node_1.node ) ;
sys_slist_append ( &test_list, &test_node_2.node ) ;
sys_slist_append ( &test_list, &test_node_3.node ) ;
//在满足 cond 条件的 node 节点后插入 test_node_4，这里匹配的节点是 test_node_2
//相当于是在 test_node_2 后插入 test_node_4
sys_dlist_insert_at ( &test_list, &test_node_4.node,
cond, &test_node_2.node ) ;
}
双向链表的使用更多可以参考 zephyr/tests/unit/list/dlist.c
参考 链接到标题
https://docs.zephyrproject.org/3.5.0/kernel/data_structures/dlist.