linux内核代码中常用的两种链表：双向链表、哈希链表
双向链表struct list_head {
struct list_head *next, *prev;
};
内核中的链表是通过将链表节点嵌入到数据结构，将数据结构链接起来的，链表节点与数据的分离使其可以更操作起来更简单，并且能在内核发中通用。
内核中也定义了一些对链表节点进行操作的函数及宏定义：
1.链表定义
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name)
struct list_head name = LIST_HEAD_INIT(name)
2.插入节点
//在节点head之后插入new void list_add(struct list_head *new, struct list_head *head) //在节点head之前插入new void list_add_tail(struct list_head *new, struct list_head *head)
3.删除节点
//删除节点entry void list_del(struct list_head *entry)
4.替换节点
//用new节点替换掉old节点 void list_replace(struct list_head *old,struct list_head *new) //用new节点替换掉old节点，并初始化old static inline void list_replace_init(struct list_head *old,struct list_head *new)
另外，还定义了几个很有用的宏:
#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) #define list_for_each_safe(pos, n, head) for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)hash 链表
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
与双向链表不同的是，hash 链表有两个结构：表头struct hlist_head和节点struct hlist_node，并且节点中的前向指针pprev是个二级指针。
hash链表相关的宏及操作函数
#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL
static inline int hlist_unhashed(const struct hlist_node *h)
static inline void hlist_del(struct hlist_node *n)
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
static inline void hlist_add_before(struct hlist_node *n,
struct hlist_node *next)
static inline void hlist_add_behind(struct hlist_node *n,
struct hlist_node *prev)
#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
#define hlist_for_each(pos, head)
for (pos = (head)->first; pos ; pos = pos->next)
#define hlist_for_each_safe(pos, n, head)
for (pos = (head)->first; pos && ({ n = pos->next; 1; });
pos = n)
#define hlist_entry_safe(ptr, type, member)
({ typeof(ptr) ____ptr = (ptr);
____ptr ? hlist_entry(____ptr, type, member) : NULL;
})
#define hlist_for_each_entry(pos, head, member)
for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);
pos;
pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
