链表是很经典的数据结构, 在linux内核里大量使用. 本文首先简单介绍下链表, 然后再来看下这种数据结构在内核中的使用方式.

一单链表

单链表(Singly Linked List)是最单的链表, 假设我们有个结构体如下,

struct list_element
{
    void *data;
    struct list_element *next; // 指向下一个struct list_element元素的指针
}

由struct list_element形成的单链表形式如下图所示, 最后一个元素的next值为NULL

单链表的单是单向的意思, 因为遍历单链表只能沿着一个单一的方向. 链表中的每个元素都有一个指向下一个元素的指针.

二双向链表

双向链表(Doubly Linked List)可以沿着2个方向进行遍历. 给struct list_element添加一个元素prev, 如下,

struct list_element
{
    void *data;
    struct list_element *next; // 指向下一个struct list_element元素的指针
    struct list_element *prev; // 指向前一个struct list_element元素的指针
}

由struct list_element形成的双向链表形式如下图所示, 第一个元素的prev值和最后一个元素得next值都是NULL.

链表中每个元素都含有2个指针元素, 分别指向前一个元素和后一个元素.

三单循环链表

单循环链表(Circular Singly Linked List)建立在单链表基础之上, 只要把单链表最后一个元素的next指针指向链表中第一个元素就可以了.

四双向循环链表

双向循环链表(Circular Doubly Linked List)建立在双向链表基础之上, 只要

把链表中最后一个元素的next指针指向链表中第一个元素
把链表中第一个元素的prev指针指向链表中最后一个元素

五内核中的双向循环链表

linux内核以一种比较巧妙的方式使用双向循环链表. 它把链表元素中用于指向前一个元素和后一个元素的2个指针(就是prev和next)单独抽取出来, 放到结构体struct list_head里,

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

然后在其它结构体成员里定义一个struct list_head的变量,

struct test {
    void *data;
    struct list_head list;
};

这样当我们有多个struct test变量时, 就可以使用变量里的list来把它们链接起来, 形成一个特殊的双向循环链表, 如下图双向循环链表需要一个切入点, 这样才知道从哪里开始遍历, 所以一般会先定义一个链表头, 然后在这个链表头后面添加链表元素, 最终形成的链表会是如下这种形式, 这个链表头是一个单独的struct list_head变量, 一般会声明为一个全局变量, 这样就方便找到这个链表头, 然后对整个链表进行遍历.

注意: list里的prev和next指向的是struct list_head类型的变量，而不是包含struct list_head类型变量的变量。

这样的链表添加和删除元素都是O(1)的时间复杂度, 效率非常高.

六相关API

本文参考的内核版本是4.9.75, 可能和其它版本的链表api略有不同, 但是总体目标还是一样的. (路径: include/linux/list.h)

定义和初始化链表头 调用方法是LIST_HEAD(name), 这样调用后产生的链表头如下,
添加链表元素 有2个方法, list_add()和list_add_tail(), 其中new是要添加进链表的新元素, head就是使用LIST_HEAD定义的链表头. __list_add()方法定义如下, 为什么会有2个添加方法呢？假设我们有1个新元素要添加到链表中来, 如果添加到链表头的右边, 那么就使用list_add()方法如果添加到链表头的左边, 那么就用list_add_tail()方法
删除链表元素