1. 链表
1.1. 单向链表和双向链表
略
1.2. 环形链表
单向：末节点指向首节点；双向：末节点的next指向首节点，首节点的prev指向末节点。
1.3. Linux实现
将链表塞进自定义的数据结构中：
struct foo {
// ...data member
struct list_head list; // 链表
}
通过list成员可以轻易找到该元素的前一个/后一个元素。
Linux提供一个宏container_of，可找到struct foo的其它变量：
#define container_of(ptr, type, member) ({ \
const typeof(((type *)0)->member) * __mptr = (ptr); \
(type *) ( (char*)__mptr - offsetof(type,member)); \
})
2. 队列
Linux通用队列实现为kfifo，实现在kernel/kfifo.c，定义在<linux/kfifo.h>
它的存储上限固定，线程安全（使用无锁技术）。
3. Map
Linux对map的实现不是搜索树/散列表，而是通过映射一个UID到一个指针。
struct idr用于映射用户空间的UID，用户可通过idr分配UID，并通过UID找到对应的指针。
4. 二叉树
Linux的二叉树主要是红黑树（rbtree）
