内核使用的数据结构有双向链表，单向链表和hash链表。另外，基树和红黑树也是内核使用的数据结构。实际上，这也是程序代码中通常使用的数据结构，一些偏僻难的数据结构并不常见。
1. container
container是linux很重要的一个概念。有了container方法，才能实现对对象的封装。
分析一下container方法。
======================================================================
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
这个方法巧妙的实现了通过结构的一个成员找到整个结构的地址。有了container方法，list才
成为了一个通用的数据结构，通过container方法，还可以实现内核的封装，程序之间不暴露
内部的数据。
2. 双向链表list
List定义在/include/linux目录下。首先看看list的结构定义：
struct list_head {
struct list_head *next, *prev;
};
List是双向链表的一个抽象，list库提供了list_entry，使用了container方法，通过container 可以从list找到整个数据对象，这样list就成为了一种通用的数据结构。
======================================================================
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
内核定义了很多对list结构操作的内联函数和宏，计有：
LIST_HEAD：定义并初始化一个list链表 list_add_tail：加一个成员到链表尾list_del：删除一个list成员
list_empty：检查链表是否为空 list_for_each：遍历链表。得到链表指针。 list_for_each_safe：遍历链表。和list_for_each区别是可以删除遍历的成员 list_for_each_entry：遍历链表，通过container方法返回结构指针。3. hash list
Hash list和双向链表list很相似，它适用于hash表。看一下hash list的head定义：
struct hlist_head {
struct hlist_node *first;
};
和通常的list比较，hlist头只有一个指针，这样就节省了一个指针的内存。如果hash表非常
庞大，那么每个hash 表头节省一个指针，整个hash表节省的内存就很可观了。这就是内核
中专门定义hash list的原因。
Hash list库提供的函数和list很相似，计有：
l HLIST_HEAD：定义并初始化一个hash list链表头
l hlist_add_head：加一个成员到hash链表头
l hlist_del：删除一个hash list成员
l hlist_empty：检查hash 链表是否为空
l hlist_for_each：遍历hash 链表。
l hlist_for_each_safe：遍历链表。和hlist_for_each区别是可以删除遍历的成员
l hlist_for_each_entry：遍历hash 链表，通过container方法返回结构指针
4. 单向链表
内核中，没有提供单向链表的定义。但实际上，有多处使用了单向链表的概念。
======================================================================
for (i = 0, p -= n; i < n; i++, p++, index++) {
struct probe **s = &domain->probes[index % 255];
while (*s && (*s)->range < range)
s = &(*s)->next;
p->next = *s;
*s = p;
}
上面的例子是加入一个新的字符设备到系统的表里面。在系统的字符设备表里，
probe结构其实就是单向链表。这种结构在内核中应用很广泛。
5. red-black tree
红黑树位于/lib/rbtree.c文件。红黑树是一种自平衡的二叉树。实际上，红黑树可以看做是折半查找。我们知道，排序的快速做法是取队列的中间值比较，然后在剩下的队列中再次取中间值比较，迭代进行直到找到最合适的位置。红黑树实际就是实现了这种算法。
那么红黑树里面的“红黑”代表什么意思？红黑的颜色处理是避免树的不平衡。举个例子，如果1，2，3，4，5五个数字依次插入一颗红黑树，那么五个值都落在了树的右侧，如果6再插入这颗红黑树，那么需要比较五次。“红黑规则”就要将树旋转，树的根部要落在3这个节点，只需要比较两次，这样就避免了树的不平衡导致的问题。
内核中的io调度算法和内存管理中都使用了红黑树。红黑树有很多介绍的文章，读者可以结合代码分析一下。
6. radix tree
内核提供了一个基树库，代码在/lib/radix-tree.c文件。基树是一种空间换时间的数据结构，
通过空间的冗余减少了时间上的消耗。用一张图来分析：
