Linux内核中的链表：设计、实现与应用
Linux 内核实现了循环双向链表，其设计可谓独树一帜。它最显著的特征是用于表示元素的结构体中不包含data成员，仅包含用以连接其它节点的指针。文件include/linux/types.h给出了list_head结构体的定义：
// in file include/linux/types.h
struct list_head {
struct list_head *next, *prev;
};应用程序在使用这种链表时，需要将其“内嵌”到应用自定义的结构体中。
zbud_header
例如，内存分配器（memory allocator）linux/mm/zbud.c中定义了结构体zbud_header。
/*
* struct zbud_header - zbud page metadata occupying the first chunk of each
* zbud page.
* @buddy: links the zbud page into the unbuddied/buddied lists in the pool
* @first_chunks: the size of the first buddy in chunks, 0 if free
* @last_chunks: the size of the last buddy in chunks, 0 if free
*/
struct zbud_header {
struct list_head buddy;
unsigned int first_chunks;
unsigned int last_chunks;
};zbud_header除了包含应用层数据first_chunks和last_chunks，还包含一个链表元素struct list_head buddy。外层的zbud_header类型的结构体就是通过内嵌其中的struct list_head链表元素结构体（prev与next指针）互相关联在一起的。
task_struct
内核使用链表辅助进程管理，在sched.h中定义了task_struct
struct task_struct {
struct list_head tasks;
struct list_head sibling;
};- 任务队列：内核使用
list_head来管理进程描述符（task_struct）中的链表，例如：task_struct->tasks：将所有进程通过双向链表连接起来。task_struct->sibling：用于管理同一父进程的子进程链表。
- 等待队列：进程在等待某些资源时，会加入到等待队列（
wait_queue_head_t），这些队列通常使用list_head实现。
内核链表操作
Linux 内核中的链表支持以下操作：
-
初始化：
LIST_HEAD、LIST_HEAD_INIT、INIT_LIST_HEAD -
查询链表：
list_is_last、list_empty、list_is_singular、list_entry、list_first_entry、list_last_entry、list_first_entry_or_null、list_next_entry、list_prev_entry -
插入元素：
__list_add、list_add -
删除元素：
__list_del、list_del -
替换元素：
list_replace -
遍历链表：
list_for_each、list_for_each_prev、list_for_each_entry、list_for_each_entry_reverse、list_prepare_entry、list_for_each_entry_continue、list_for_each_entry_continue_reverse、list_for_each_entry_from、list_for_each_entry_from_reverse -
单个链表操作：
list_rotate_left、__list_cut_position、list_cut_position -
多个链表操作：
list_move、list_move_tail、__list_splice、list_splice、list_splice_tail、list_splice_init、list_splice_tail_init
源码解析
list_entry
由于该链表在设计时不包含数据域，需要嵌入到应用层的结构体中使用，因此很多时候需要根据链表中的元素获取该元素所在的应用层结构体。list_entry宏就起到该作用。它的实现使用了container_of宏。
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_head within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)类似地，list_next_entry根据当前应用层结构体指针pos获取链表中下一个（应用层）结构体（的地址）。(pos)->member取得应用层结构体内的member成员，是该结构体内嵌的链表元素，(pos)->member.next根据该链表元素的next指针取得链表中的下一个元素（指针类型）。最后，通过list_entry获取(pos)->member.next所在的应用层结构体。
/**
* list_next_entry - get the next element in list
* @pos: the type * to cursor
* @member: the name of the list_head within the struct.
*/
#define list_next_entry(pos, member) \
list_entry((pos)->member.next, typeof(*(pos)), member)