linux建议开发者使用其内建的数据结构，而不要自作主张搞一套山寨的。本文讲解内核中常用的4种数据结构：链表，队列，映射，二叉树。
1.链表
链表包括单向链表（有一个后向指针），双向链表（有一个后向指针和一个前向指针），环形链表（首尾相连）。linux内核的标准链表采用环形双向链表形式实现。
1.1 链表数据结构
linux内核方式与众不同，它不是将数据结构塞入链表，而是将链表节点塞入数据结构。比如，一个普通的链表节点：
struct Node {
int data;
struct Node *pre;;
struct Node *next;
};
linux下的实现是把前后指针抽出来，形成单独数据结构：
struct list_head {
struct list_head *next;
struct list_head *prev;
};
然后插入数据节点中：
struct Node {
int data;
struct list_head list;
};
我们不必担心找不到父结构中所含有的变量（比如Node中的data），可以通过宏container_of()找到任何变量。其实现如下：
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *) ( (char *)__mptr - offsetof(type, member) ); })
使用这个宏，可以定义一个简单的函数便可以返回包含list_head的父类型结构体：
#define list_entry(ptr, type, member) container_of(ptr, type, member)
1.2 定义链表
list_head本身没有意义--它需要被嵌入到你自己的数据结构中才能生效。
链表使用前需要初始化，可以采用动态初始化和静态初始化。
1.3 链表头
内核链表各个结点无差别。由于遍历时需要一个特殊指针索引到整个链表，而不是从一个链表结点触发。定义特殊的索引节点：LIST_HEAD(fox_list)。其实它也是一个常规的list_head。
1.4 操作链表
添加节点：list_add
把节点添加到链表尾：list_add_tail
从链表中删除: list_del
把一个节点从一个链表移到另一个链表：list_move
检查链表是否为空：list_empty
把两个未连接的链表合并在一起：list_splice
1.5遍历链表
可以使用list_for_each()宏：
struct Node *node;
struct list_head *p;
list_for_each(p, &node_list) {
p = list_entry(p, struct Node, list);
}
也可以用list_for_each_entry()，捆绑以上两个宏。
list_for_each_entry_reverse()用于反向遍历。
2.队列
linux内核通用队列实现称为kfifo。其提供了两个主要操作：enqueue和dequeue，同时维护了两个偏移量：入口偏移和出口偏移。
2.1 创建队列
同样有动态和静态方法。
动态： int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask);
静态：DECLARE_KFIFO(name, size); INIT_KFIFO(name);
2.2 其他操作
压入数据：kfifo_i\n
出队列：kfifo_out
遍历队列：kfifo_out_peek
获取队列总大小：kfifo_size
获取队列数据大小：kfifo_len
获取队列还有的可用空间：kfifo_avail
判断是否为空：kfifo_is_empty
判断是否为满：kfifo_is_full
重置队列，清空所有数据：kfifo_reset
撤销一个使用kfifo_alloc()分配的队列：kfifo_free()
3.映射
一个映射，也常称为关联数组，其实是一个由唯一键组成的集合，而每个键必然关联一个特定的值。这种键到值的关联关系称为映射。映射要至少支持三个操作：
- Add(key, value)
- Remove(key)
- value = Lookup(key)
虽然，键到值的映射属于一个通用说法，但是更多时候特指使用二叉树而非散列表实现的关联数组。
linux内核提供了简单，有效的映射数据结构。但是它并非一个通用的映射。因为它的目标是：映射一个唯一的标识符（UID）到一个指针。除了提供三个标准的映射操作外，linux还在add操作基础上实现了allocate操作。这个allocate操作不但向map中加入了键值对，而且还可以产生UID。
idr数据结构用于映射用户空间的UID，比如将inodify_watch的描述符或者POSIX的定时器ID映射到内核中相关联的数据结构上，如inotify_watch或者k_itimer结构体。
3.1 操作
初始化：idr_init
分配一个新的UID：id_pre_get，idr_get_new
查找UID：idr_find
删除UID：idr_remove
撤销idr（只释放idr中未使用的内存）：idr_destory
强制删除所有UID：idr_remove_all
4. 二叉树
参考我另一个篇文章：红黑树和avl树的个人总结
linux中的红黑树rbtree实现没有提供搜索和插入例程，这些例程希望由rbtree的用户自定义。
5. 数据结构以及选择
如果对数据集合的主要操作是遍历数据，就使用链表。
如果代码符合生产者/消费者模式，则使用队列，特别是如果希望要一个定长缓冲。另一个方面，如果你需要存储一个大小不明的数据集合，那么链表可能更合适，因为可以动态添加任何数量的数据项。
如果需要映射一个UID到一个对象，就使用映射。映射可以帮助维护和分配UID。linux的映射接口是针对UID到指针的映射，它并不适合其他场景。但是如果你在处理发给用户空间的描述符，就考虑一下映射。
如果需要存储大量数据，并且检索迅速，那么使用红黑树。搜索的时间复杂度是对数关系，同时能保证按序遍历事件复杂度是线性。比其他数据结构复杂一点，但其内存开销不高。但是，如果没有执行太多次时间紧迫的查找，则红黑树不是最好选择。
另外，还有基树（trie类型）和位图。