在开始写linux内核双向循环链表之前，我一直在想我要不要用长篇大论的文字来描述linux内核双向循环链表呢？经过认真的思考之后，我否决了用枯燥的文字向读者描述linux内核双向循环链表的想法，因为对于编程语言来说我相信大多数的读者都应该不喜欢面对枯燥的文字，更喜欢看到代码，同时那也是读者阅读文字后想要实现的东西，所以我决定在这里采用代码加上适当的文字描述的方法来进行讲解，这就使得我不可能用一篇的篇幅来讲解完，所以会写两篇文章来讲解这个知识点。希望读者能够坚持看完，学会以后在应用程序中写双向循环链表时，不用再自己去编写那些麻烦的操作函数，充分利用linux内核里已经提供的遍历链表的操作函数。

特此说明：我会把我在文章中编写代码时候用到的头文件list.h上传到我的空间，免积分下载，有需要的读者可以自己去下载，当然也可以自己上网下载或者从自己安装的linux系统中得到。下载地址：http://download.csdn.net/user/bigloomy

懂了linux内核里双向循环链表的实现方式之后我们不得不惊叹它的实现是如此的巧妙，为了读者能够顺利的和我一起走完这次linux内核双向循环链表之旅，在此之前我特地为之写了一篇《C语言的那些小秘密之字节对齐》的文章，如果你发现在本篇文章中有些地方不懂的时候，你可以回过去看看《C语言的那些小秘密之字节对齐》再来接着继续往下继续全文的阅读。

由于我们在linux内核中有大量的数据结构都需要用到双向循环链表。若再采用以往那种传统双向循环链表的实现方式，我们不得不为这些数据结构维护各自的链表，并且为每个链表都要设计插入、查找、删除等操作函数。这是因为我们在常规链表中用来维持链表的next和prev指针都是指向对应类型的对象，因此一种数据结构的链表操作函数不能用于操作其它数据结构的链表。为了解决这个问题，在Linux内核中采用了一种与类型无关的双向循环链表实现方式，它的实现使得我们不用再为每个链表都要设计插入、查找、删除等相关的操作函数。其实现方法就是将结构体中的指针prev和next从具体的数据结构中提取出来，构成一种通用的双向循环链表数据结构list_head。如果需要构造某类对象的特定链表，则只需要在其结构体中定义一个类型为list_head类型的成员，通过这个定义的list_head类型的成员将这类对象连接起来，形成所需的双向循环链表，进而通过通用链表函数对其进行操作。显而易见是我们只需编写通用链表函数，就可构造和操作不同对象的链表，而无需为每个创建的双向循环链表编写专用函数，从而大大的实现了代码的重用。

下面我们就真正的开始我们的linux内核双向循环链表之旅。读者可以从网上下载一个linux内核双向循环链表的list.h的头文件，值得注意的就是因为内核版本的不同可能下载的头文件有些差异，但是这个并不影响我们对于它的讲解。读者可以先看完全文后再动手也不迟，用list.h头文件来实现我们的双向循环链表。为了便于讲解，我们就按照list.h头文件中代码的先后顺序进行讲解。

补充一点：（注：如果读者看不懂下面这段代码，可以继续往下看，不会影响接下来的学习，在接下来的部分还会有讲解，这部分代码是我写完全文后添加的，因为一开始我使用的是#define list_entry(ptr, type, member) ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))而不是#define list_entry(ptr, type, member) container_of(ptr, type, member)）

#define container_of(ptr, type, member) ( { \

const typeof( ((type *)0)->member ) *__mptr = (ptr); \

(type *)( (char *)__mptr - offsetof(type,member) ); } )

通过typeof( ((type *)0)->member )得到member成员的类型，将指向member的指针ptr赋值给__mptr，__mptr指针的类型为member数据成员的类型。通过(char *)__mptr将__mptr强制转换为char指针，之后再减去offsetof(type,member)，即可得到宿主结构体的指针。如果有对offsetof(type,member)不懂的可以参考我之前写的一篇《C语言的那些小秘密之字节对齐》。

首先看看list_head结构的实现。

struct list_head {

struct list_head *next, *prev;

};

在linux内核双向循环链表中我们用以上list_head类型定义一个变量，将其作为一个成员嵌入到宿主结构内。什么是宿主结构体呢？就是我们创建的双向循环链表的结构体。可以将链表结构放在宿主结构内的任何地方，当然也可以为链表结构取任何名字，从而我们就可以用list_head中的成员和相对应的处理函数来对链表进行遍历操作，如果想得到宿主结构的指针，使用我们可以使用list_entry计算出来，先别急着想知道list_entry什么，我们会在下面讲解，接着往下看。

在宿主结构体中定义了list_head之后接下来当然是要对我们定义的头结点进行初始化工作，初始化的实现方法可以有以下两种方式。

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \

struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \

(ptr)->next = (ptr); (ptr)->prev = (ptr); \

} while (0)

分析上面的代码可知，我们在代码中使用list_head定义了一个头结点之后，就要对定义的头结点进行初始化工作，可以使用INIT_LIST_HEAD(ptr)宏进行初始化，或者我们无需自己定义直接使用LIST_HEAD(name)宏即可完成定义和初始化的工作。头结点的初始化工作完成了之后接下来的工作当然是要添加节点了。

static inline void __list_add(struct list_head *new,

struct list_head *prev,

struct list_head *next)

{

next->prev = new;

new->next = next;

new->prev = prev;

prev->next = new;

}