双向链表是Linux中非常重要和基础的一个数据结构，它在Linux内核中是一个基本类型

Linux内核中的链表

一个常见的双向链表可以被定义为

struct my_list{void *mydata;struct my_list *next;Cstruct my_list *prev;
};

不同的使用方法会构造出不同的数据结构

先进先出是队列
只对后继操作是栈
两个节点指向子树就是二叉树
…

链表基本功能的实现

定义

Linux中的链表定义为:

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

在linux/list.h中有链表的声明和初始化的宏

#define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \struct list_head name = LIST_HEAD_INIT(name)

判空

/*** list_empty - tests whether a list is empty* @head: the list to test.*/
static inline int list_empty(const struct list_head *head)
{return head->next == head;
}

非常简单清晰，判断head的next是否指向head本身即可。

插入

/** Insert a new entry between two known consecutive entries.** This is only for internal list manipulation where we know* the prev/next entries already!*/
#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next);
#endif

这里主要是提供了一个默认的实现方式，或者通过extern实现也行。
默认的方式很简单清晰，就是分别将prev的后继指向new，next的前驱指向new，new的前驱和后继分别指向prev和next。

遍历

Linux中通过定义一个宏来实现遍历

/*** list_for_each	-	iterate over a list* @pos:	the &struct list_head to use as a loop cursor.* @head:	the head for your list.*/
#define list_for_each(pos, head) \for (pos = (head)->next; pos != (head); pos = pos->next)

定位

找到节点的位置如何定位到该节点呢？
linux提供了一个定位的宏

/*** list_entry - get the struct for this entry* @ptr:	the &struct list_head pointer.* @type:	the type of the struct this is embedded in.* @member:	the name of the list_struct within the struct.*/
#define list_entry(ptr, type, member) \container_of(ptr, type, member)

这里用container_of对宏进行了封装, 本体应该是这样的：

#define list_entry(ptr, tpye, member) \ ((type*)((char*)(ptr) - (unsigned long)(&((type*)0)->member)))

这个实现的功能就是，获得ptr的位置，然后减去member的偏移量，就可以得到该节点的起始地址了，就可以对节点进行操作，而不只单纯的对节点内部的某一成员进行操作。

删除

双向节点的删除操作

/** Delete a list entry by making the prev/next entries* point to each other.** This is only for internal list manipulation where we know* the prev/next entries already!*/
static inline void __list_del(struct list_head * prev, struct list_head * next)
{next->prev = prev;prev->next = next;
}/*** list_del - deletes entry from list.* @entry: the element to delete from the list.* Note: list_empty() on entry does not return true after this, the entry is* in an undefined state.*/
#ifndef CONFIG_DEBUG_LIST
static inline void __list_del_entry(struct list_head *entry)
{__list_del(entry->prev, entry->next);
}static inline void list_del(struct list_head *entry)
{__list_del(entry->prev, entry->next);entry->next = LIST_POISON1;entry->prev = LIST_POISON2;
}
#else
extern void __list_del_entry(struct list_head *entry);
extern void list_del(struct list_head *entry);
#endif

外部调用list_del函数，传入一个entry的指针，让该entry的前驱和后继相互指向，本身置空。

大道至简，linux中的双链表定义非常简单，无需畏难。之后的很多数据结构都需要基于双链表进行构造。