引言
链表是最常用的数据结构，而且具有多种变种，比较常见的包括：单链表，双向链表，双向循环俩表，队列。在使用 C 语言编程的时候，一般会使用第三方的函数库提供的链表实现，而使用 C++ 和 Java 等语言的时候则使用标准的函数库提供的链表。
单向与双向链表之间的最大差别是删除元素操作的性能，在单向链表中删除一个元素需要遍历链表，复杂度为 O(n)，而在双向链表中则只需要直接删除，复杂度为 O(1)。但是，这只是理论上的结果，实际使用中能否达到 O(1) 性能依赖于链表的实现方法以及使用链表的方法。例如，在 GLib 的双向链表实现中，就提供了两种从链表中删除一个元素的方法：
typedef struct {
gpointer data;
GList *next;
GList *prev;
} GList;
GList* g_list_remove (GList *list,
gconstpointer data);
GList* g_list_remove_link (GList *list,
GList *llink);
第一个函数从链表中删除包含 data 这个指针的链表元素，这个操作需要首先遍历链表，找到包含这个指针的元素，然后删除，因此依然需要 O(n) 时间；第二个函数直接删除一个链表元素，因此只需要 O(1) 时间。在多数情况下，链表的用户只会保存 data 指针，而不保存链表元素指针，所以多数情况下第一个函数会被使用，这样就降低了删除的效率。
其实操作系统已经为我们提供了优化的链表实现，它避免了上述的性能问题，不过使用起来稍微复杂一点，这些数据结构是作为宏是现在 sys/queue.h 头文件的。
sys/queue.h 的实现与应用
由于 sys/queue.h 提供的链表实现与一般课本上的不同，所以先了解它的实现会更容易理解如何去使用它。这个头文件提供了单链表，双向链表，单向队列，双向队列和双向循环队列，下面只以双向链表为例，其他的从原理上讲都是一样的。
双向链表的实现如下：
/*
* List definitions.
*/
#define LIST_HEAD(name, type) \
struct name { \
struct type *lh_first; /* first element */ \
}
#define LIST_HEAD_INITIALIZER(head) \
{ NULL }
#define LIST_ENTRY(type) \
struct { \
struct type *le_next; /* next element */ \
struct type **le_prev; /* address of previous next element */ \
}
/*
* List functions.
*/
#define LIST_INIT(head) do { \
(head)->lh_first = NULL; \
} while (/*CONSTCOND*/0)
#define LIST_INSERT_AFTER(listelm, elm, field) do { \
if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
(listelm)->field.le_next->field.le_prev = \
&(elm)->field.le_next; \
(listelm)->field.le_next = (elm); \
(elm)->field.le_prev = &(listelm)->field.le_next; \
} while (/*CONSTCOND*/0)
#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
(elm)->field.le_prev = (listelm)->field.le_prev; \
(elm)->field.le_next = (listelm); \
*(listelm)->field.le_prev = (elm); \
(listelm)->field.le_prev = &(elm)->field.le_next; \
} while (/*CONSTCOND*/0)
#define LIST_INSERT_HEAD(head, elm, field) do { \
if (((elm)->field.le_next = (head)->lh_first) != NULL) \
(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
(head)->lh_first = (elm); \
(elm)->field.le_prev = &(head)->lh_first; \
} while (/*CONSTCOND*/0)
#define LIST_REMOVE(elm, field) do { \
if ((elm)->field.le_next != NULL) \
(elm)->field.le_next->field.le_prev = \
(elm)->field.le_prev; \
*(elm)->field.le_prev = (elm)->field.le_next; \
} while (/*CONSTCOND*/0)
#define LIST_FOREACH(var, head, field) \
for ((var) = ((head)->lh_first); \
(var); \
(var) = ((var)->field.le_next))
/*
* List access methods.
*/
#define LIST_EMPTY(head) ((head)->lh_first == NULL)
#define LIST_FIRST(head) ((head)->lh_first)
#define LIST_NEXT(elm, field) ((elm)->field.le_next)
这种链表实现与上面 GList 的实现的根本区别在于，queue.h 的链表是用户数据结构里面包含链表元素，而 GList 是链表元素包含用户数据结构。也就是说，为了使用 queue.h 提供的链表，用户数据结构 data 必须定义成
struct data {
LIST_ENTRY (data) list_entry;
};
经过宏展开之后，就变成
struct data {
struct {
struct data *le_next; /* next element */
struct data **le_prev; /* address of previous next element */
} list_entry;
};
通过仔细分析 queue.h 中的源代码，可以发现链表中相邻的两个用户数据之间形成了右图所示的关系。需要特别注意的是，le_prev 指针指向的是前一个元素的 le_next 指针，而不是前一个元素，所以链表各种操作的实现与我们在课本上学到的也有所不同。
下面简要说明一下各个宏的含义：
- LIST_HEAD 宏定义一个链表头结构，里面包含一个指向第一个链表元素的指针，name 是头结构的名字，type 是用户数据结构的类型名。在使用这个链表之前，需要 LIST_INIT 宏初始化链表头，注意参数是到链表头结构的指针。
- 各种链表操作都以到用户数据的指针为参数，还需要提供用户数据结构中链表元素域的名字，例如在上面的例子中，data 结构里面链表元素域为 list_entry。
正是因为链表元素是包含在用户数据结构中的，所以用户只需要提供用户数据的指针就能以 O(1) 的复杂度删除一个元素了，如果一个用户数据结构同时在多个链表中，就需要在用户数据结构里面定义多个链表元素域。事实上，Linux 内核中的链表就是用类似的方法定义的。
下面是一个使用 sys/queue.h 中双向链表的简单例子（修改自 man 文档）
LIST_HEAD(listhead, data) head;
struct data {
LIST_ENTRY(data) list_entry; /* List. */
} *n1, *n2, *np;
LIST_INIT(&head); /* Initialize the list. */
n1 = malloc(sizeof(struct data)); /* Insert at the head. */
LIST_INSERT_HEAD(&head, n1, list_entry);
n2 = malloc(sizeof(struct data)); /* Insert after. */
LIST_INSERT_AFTER(n1, n2, list_entry);
/* Forward traversal. */
LIST_FOREACH(np, &head, list_entry)
np->
while (head.lh_first != NULL) /* Delete. */
LIST_REMOVE(head.lh_first, list_entry);