Linux内核中的双链表

关键词Key words：双链表、头结点、遍历 

摘  要Abstract：Linux内核中内存管理、进程管理、文件系统、存储管理等都使用队列和双链表，其使用频率和范围都相当广，理解双链表就变得非常必要。本文介绍Linux 2.4内核中的双链表结构及其使用。

1  概述 

Linux内核中大量使用着队列和队列操作，而它又不是专门属于哪一个方面的内容（如进程管理、文件系统、存储管理等）。

如果我们有一种数据结构foo，并且需要维持一个这种数据结构的双链表队列，最简单的，也是最常用的办法就是在这个数据结构的类型定义中加入两个指针，例如：

然后为这种数据结构写一套用于各种队列操作的子程序。由于用来维持队列的这两个指针的类型是固定的（都指向foo数据结构），这些子程序不能用于其他数据结构的队列操作。换言之，需要维持多少中数据结构的队列，就得有多少套的队列操作子程序。对于使用队列较少的应用程序或许不是个大问题，但对于使用大量队列的内核就成问题了。所以，Linux内核采用了一套通用的、一般的、可以用到各种不同数据结构的队列操作。为此，代码的作者们把指针prev和next从具体的“宿主”数据结构抽象出来称为一种数据结构list_head，这种数据结构既以“寄宿”在具体的宿主数据结构内部，称为该数据结构的一个“连接件”；也可以独立存在称为一个队列的头。这个数据结构的定义在文件<include/linux/list.h>中。

2  双链表及C语言指针 

2.1  双链表基础知识

在这里我们简单回顾一下数据结构中双链表基础知识及操作，简单的双链表如图1所示。

图1  简单双链表结构

2.1.1  插入结点

假设我们在B和C两个结点之间插入一个结点X，如图2所示。

图2 双链表中插入一个结点

操作步骤及指针变化如下： 

X->prev = B; 

X->next = C; 

C->prev = X; 

B->next = X; 

2.1.2  删除结点

假设我们需要把B结点删除，如图3所示。

图3 双链表中删除一个结点

操作步骤及指针变化如下： 

A->next = C; 

C->prev = A; 

注：这里我们不关心结点B的内存空间释放，而仅仅是关注指针的变化；删除结点的内存空间释放，由其他函数处理。

2.2  C语言指针 

在这里我们不对C语言指针做详细的介绍，相关内容请参考C语言书籍。

2.2.1  结构体指针成员变量间关系

先给出一段示例代码：