数据结构（嵌入式视角）

嵌入式开发对数据结构的要求：不追求面面俱到，但链表 / 队列 / 哈希表必须能手写。

一、复杂度速查

结构	插入	删除	查找	备注
数组	O(n)	O(n)	O(n) 顺序 / O(1) 索引	缓存友好
链表	O(1)	O(1)	O(n)	插入删除不移动元素
动态数组	O(1) 摊销	O(n)	O(1) 索引
哈希表	O(1) 摊销	O(1) 摊销	O(1) 摊销	哈希冲突代价高
二叉搜索树	O(log n) 摊销	O(log n)	O(log n)	可能退化为 O(n)
红黑树	O(log n)	O(log n)	O(log n)	自平衡
跳表	O(log n) 摊销	O(log n)	O(log n)
堆	O(log n) 插入	O(log n)	O(1) 取极值	优先队列
栈/队列	O(1)	O(1)	-

二、单链表（必须手写）

1. 侵入式（Linux 内核风格）

struct list_head {
    struct list_head *next, *prev;
};
static inline void INIT_LIST_HEAD(struct list_head *list) {
    list->next = list;
    list->prev = list;
}
static inline void list_add(struct list_head *node, struct list_head *head) {
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
}
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

使用：

struct task {
    int id;
    struct list_head node;
};
struct list_head tasks = LIST_HEAD_INIT(tasks);

struct task *t = malloc(sizeof(*t));
t->id = 1;
list_add(&t->node, &tasks);

list_for_each(p, &tasks) {
    struct task *cur = list_entry(p, struct task, node);
    printf("%d\n", cur->id);
}

2. 非侵入式

struct node {
    int data;
    struct node *next;
};

三、循环缓冲区（Ring Buffer）

struct ring {
    char *buf;
    size_t cap;     // 必须是 2 的幂（便于位运算取模）
    size_t head;    // 写位置
    size_t tail;    // 读位置
};
size_t ring_write(struct ring *r, const void *data, size_t n);
size_t ring_read (struct ring *r, void *out,       size_t n);

应用：UART DMA 接收、音频、生产者/消费者。

四、队列（队列库）

数组实现：循环队列
链表实现：无界队列
优先队列：二叉堆（O(log n) 取出极值）

五、哈希表

1. 哈希函数

字符串：djb2、FNV-1a、MurmurHash、xxHash
整数：乘法哈希（如 key * 2654435761）

2. 冲突解决

链地址法（separate chaining）：常用
开放地址法（open addressing）：线性/二次/双重哈希

3. 嵌入式简化版

#define HASH_SIZE 256
struct kv { char *key; void *value; struct kv *next; };
struct kv *table[HASH_SIZE];   // 每个 slot 一个链表头

六、动态数组（vector）

struct vec {
    void  **data;
    size_t  size;
    size_t  cap;
};
int   vec_push(struct vec *v, void *p);
void *vec_pop (struct vec *v);
void *vec_at  (struct vec *v, size_t i);

七、栈（手写练习）

数组栈：固定大小，O(1)
链表栈：动态大小

八、红黑树（仅作了解）

Linux 内核 rbtree.h：进程调度 CFS、epoll 使用
可参考 lib/rbtree.c 实现

九、内核中的数据结构

结构	用途
`list_head`	通用双向链表
`hlist`	哈希表桶链表（节省空间）
`rbtree`	CFS 调度、epoll
`radix tree`	页缓存
`idr`	ID 到指针映射
`kfifo`	无锁环形队列