操作系统内核, 如同其他程序, 常常需要维护数据结构的列表. 有时, Linux 内核已经同时有几个列表实现. 为减少复制代码的数量, 内核开发者已经创建了一个标准环形的, 双链表; 鼓励需要操作列表的人使用这个设施.

　　当使用链表接口时, 你应当一直记住列表函数不做加锁. 如果你的驱动可能试图对同一个列表并发操作, 你有责任实现一个加锁方案. 可选项( 破坏的列表结构, 数据丢失, 内核崩溃) 肯定是难以诊断的.

　　为使用列表机制, 你的驱动必须包含文件 . 这个文件定义了一个简单的类型 list_head 结构:

　　以下是代码片段：

　　struct list_head { struct list_head *next, *prev; };

　　真实代码中使用的链表几乎是不变地由几个结构类型组成, 每一个描述一个链表中的入口项. 为在你的代码中使用 Linux 列表, 你只需要嵌入一个 list_head 在构成这个链表的结构里面. 假设, 如果你的驱动维护一个列表, 它的声明可能看起来象这样:

　　以下是代码片段：

　　struct todo_struct

　　{

　　struct list_head list;

　　int priority;

　　};

　　列表的头常常是一个独立的 list_head 结构. 图链表头数据结构显示了这个简单的 struct list_head 是如何用来维护一个数据结构的列表的.

　　链表头数据结构

　　链表头必须在使用前用 INIT_LIST_HEAD 宏来初始化. 一个"要做的事情"的链表头可能声明并且初始化用:

　　以下是代码片段：

　　struct list_head todo_list;

　　INIT_LIST_HEAD(&todo_list);

　　可选地, 链表可在编译时初始化:

　　以下是代码片段：

　　LIST_HEAD(todo_list);

　　几个使用链表的函数定义在 :

　　以下是代码片段：

　　list_add(struct list_head *new, struct list_head *head);

　　在紧接着链表 head 后面增加新入口项 -- 正常地在链表的开头. 因此, 它可用来构建堆栈. 但是, 注意, head 不需要是链表名义上的头; 如果你传递一个 list_head 结构, 它在链表某处的中间, 新的项紧靠在它后面. 因为 Linux 链表是环形的, 链表的头通常和任何其他的项没有区别.

　　以下是代码片段：

　　list_add_tail(struct list_head *new, struct list_head *head);

　　刚好在给定链表头前面增加一个新入口项 -- 在链表的尾部, 换句话说. list_add_tail 能够, 因此, 用来构建先入先出队列.

以下是代码片段：

　　list_del(struct list_head *entry);

　　list_del_init(struct list_head *entry);

　　给定的项从队列中去除. 如果入口项可能注册在另外的链表中, 你应当使用 list_del_init, 它重新初始化这个链表指针.

　　以下是代码片段：

　　list_move(struct list_head *entry, struct list_head *head);

　　list_move_tail(struct list_head *entry, struct list_head *head);

　　给定的入口项从它当前的链表里去除并且增加到 head 的开始. 为安放入口项在新链表的末尾, 使用 list_move_tail 代替.

　　以下是代码片段：

　　list_empty(struct list_head *head);

　　如果给定链表是空, 返回一个非零值.

　　以下是代码片段：

　　list_splice(struct list_head *list, struct list_head *head);

　　将 list 紧接在 head 之后来连接 2 个链表.

　　list_head 结构对于实现一个相似结构的链表是好的, 但是调用程序常常感兴趣更大的结构, 它组成链表作为一个整体. 一个宏定义, list_entry, 映射一个 list_head 结构指针到一个指向包含它的结构的指针. 它如下被调用:

　　以下是代码片段：

　　list_entry(struct list_head *ptr, type_of_struct, field_name);

　　这里 ptr 是一个指向使用的 struct list_head 的指针, type_of_struct 是包含 ptr 的结构的类型, field_name 是结构中列表成员的名子. 在我们之前的 todo_struct 结构中, 链表成员称为简单列表. 因此, 我们应当转变一个列表入口项为它的包含结构, 使用这样一行:

　　以下是代码片段：

　　struct todo_struct *todo_ptr = list_entry(listptr, struct todo_struct, list);

　　list_entry 宏定义使用了一些习惯的东西但是不难用.

　　链表的遍历是容易的: 只要跟随 prev 和 next 指针. 作为一个例子, 假设我们想保持 todo_struct 项的列表已降序的优先级顺序排列. 一个函数来添加新项应当看来如此:

　　以下是代码片段：

　　void todo_add_entry(struct todo_struct *new)

　　{

　　struct list_head *ptr;

　　struct todo_struct *entry;