双链表

双链表大概是软件中最为常见也是最简单的数据结构之一了。所以在内核中的定义和使用也不难，只是用法上可能和其他地方的实现略有不同。

单个的样子

这个样子很普通，一共两个成员，各自指向前后就行了。

    list_head
    +-----------------------+
    |prev                   |
    |next                   |
    |    (struct list_head*)|
    +-----------------------+

组合时的样子

组合起来样子也相对比较简单。

    list_head          
    +-----------+
    |prev   next|<-+
    +-----------+  |
       ^           |
       |           |
       |           |      Parent Data              Parent Data
       |           |      +-----------------+      +-----------------+
       |           +----->|list_head        |<---->|list_head        |<-----+
       |                  +-----------------+      +-----------------+      |
       |                                                                    |
       +--------------------------------------------------------------------+

这里想要强调的一点是，内核中通常把list_head结构嵌入到某个真实的数据结构中，然后由一个list_head结构作为链表头。

常用的API

常用的增删类API有：

• list_add()

• list_add_tail()

• list_del()

• list_move()

• list_move_tail()

常用的遍历类API有：

• list_for_each()

• list_for_each_prev()

• list_for_each_entry()

• list_for_each_entry_reverse()