链表链接到标题

链表包含单向链表和双向链表：

单链表 ： Zephyr 中单向链表以常数时间 O ( 1 ) 访问链表的头部和尾部元素，在头部前和尾部后插入元素，移除链表的头部元素。但要删除链表中的节点，则需要遍历链表进行搜索，因此需要线性时间 O ( n ) 。单链表节点内只存储指向下一个节点的一个指针。单向链表实现在下列文件中：

zephyr/include/zephyr/sys/slist.h zephyr/include/zephyr/sys/sflist.h

双向链表：Zephyr 中双向链表支持与单向链表相同的操作，并且还额外提供了在常数时间 O ( 1 ) 内在任意位置 ( 头部、尾部或内部节点 ) 进行插入和删除节点的能力。为了实现这些功能，双向链表每个节点需要存储两个指针，因此在运行时的代码和内存空间相较于单向链表会有些额外开销。双向链表实现在下列文件中：

zephyr/include/zephyr/sys/dlist.h

包缓冲区链接到标题

包缓存包含 MPSC 和 SPSC：

MPSC 缓冲区 ( 多生产者单消费者 ): Multi Producer Single Consumer Packet Buffer ( MPSC ) 是一个用于存储数据包的循环缓冲区，按照先进先出的顺序进行处理。只有一个上下文 ( 消费者 ) 来消费数据。可能会有多个上下文 ( 生产者 ) 写入。数据包的生产和消费都分为两个步骤。生产者首先分配一定数量的空间，然后填充数据并提交。消费者首先声明要消费的数据包，获取指向数据包的指针和长度，在使用完这些数据后释放数据包。这种方法可以减少内存复制的次数，提高效率。MPSC 实现在下列文件中：

zephyr/include/zephyr/sys/mpsc_pbuf.h zephyr/lib/os/mpsc_pbuf.c

SPSC 缓冲区 ( 单生产者单消费者 ): Single Producer Single Consumer Packet Buffer ( SPSC ) 是一个用于存储数据包的循环缓冲区，按照先进先出的顺序进行处理。只有一个上下文 ( 消费者 ) 来消费数据，也只用一个上下文 ( 生产者 ) 产生数据。SPSC 消费者需要通过拷贝才能得到数据。SPSC 实现在下列文件中：

zephyr/include/zephyr/sys/spsc_pbuf.h zephyr/lib/os/spsc_pbuf.c

红黑树链接到标题

排序的节点规模在运行时可能变得非常大，这时使用链表进行搜索操作的效率会变得很低 O(n) 。为了解决这个问题，Zephyr 提供了一种平衡树实现。平衡树在搜索和删除操作上的时间复杂度为 O(log2(n)) 。Zephyr 中平衡树采用红黑树算法。红黑实现在下列文件中：

zephyr/include/zephyr/sys/rb.h zephyr/lib/os/rb.c

环形缓冲区链接到标题

环形缓冲区是一个循环缓冲区，其内容按照先进先出的顺序存储，可以按照下面两种模式操作

字节模式：原始字节可以入队和出队
数据项模式：带有元数据的多个 32 位字数据项，以最大 1020 字节的块从环形缓冲区入队和出队

环形缓冲区实现在下列文件中：

zephyr/include/zephyr/sys/ring_buffer.h zephyr/lib/os/ring_buffer.c

参考链接到标题

https://docs.zephyrproject.org/latest/kernel/data_structures/index.html

链表 链接到标题

包缓冲区 链接到标题

红黑树 链接到标题

环形缓冲区 链接到标题

参考 链接到标题

链表链接到标题

包缓冲区链接到标题

红黑树链接到标题

环形缓冲区链接到标题

参考链接到标题