数据结构之线性表

Author:Once Day Date:2023年5月27日

参考文档:

1.概述

  • 线性表(linear list)存在唯一的头部数据和尾部数据,而且中间的每个数据都有一个前驱元素和后驱元素。
  • 线性表是有限个元素的序列,如一维数组和链表。
  • 每个数据元素可由若干个数据项构成。

数学表达可如下:
( a 1 , a 2 , . . . . , a n − 1 , a n ) (a_1,a_2,....,a_{n-1},a_n) (a1,a2,....,an1,an)
**数据元素n即为线性表的长度。**也可以看到每个元素都有个确切的位置,并且长度也可根据需要增长和缩短。

本文介绍的线性表以linux自带的sys/queue.h为例子,该列表来自于FreeBSD中的一个头文件。一般由glibc中携带。源码查看链接如下:

头文件queue.h为C语言中的链表提供了更加标准规范的编程接口。如今的版本多为伯克利加州大学1994年8月的8.5版本。

1.1 不同队列的功能介绍

单链表(SLIST)的头是一个正向指针。元素是单链接的,以最小的空间和指针操作开销为代价,对任意元素进行O(n)移除。新元素可以添加到现有元素之后,也可以添加到列表的头部。从列表头部删除的元素应该使用显式宏来实现此目的,以获得最佳效率。单链表只能在正向上遍历。单链表适用于具有大数据集且很少或没有删除的应用程序,或实现后进先出队列。

单链尾队列(STAILQ)由一对指针引导,一个指向列表的头部,另一个指向列表的尾部。元素是单链接的,以最小的空间和指针操作开销为代价,对任意元素进行O(n)移除。可以将新元素添加到列表中,在现有元素之后,在列表的头部,或在列表的末尾。要从尾部队列的头部删除的元素应该为此目的使用显式宏,以获得最佳效率。单链尾队列只能在正向上遍历。单链接尾部队列非常适合具有大数据集和很少或没有删除或实现FIFO队列的应用程序。

一些bsd提供SIMPLEQ而不是STAILQ。它们是相同的,但由于历史原因,它们在不同的bsd上命名不同。STAILQ起源于FreeBSD,而SIMPLEQ起源于NetBSD。出于兼容性的考虑,有些系统提供两组宏。Glibc提供了STAILQ和SIMPLEQ,除了缺少一个相当于STAILQ_CONCAT()的SIMPLEQ之外,它们是相同的

列表(LIST)的头由单个前向指针(或哈希表头的前向指针数组)组成。元素是双向链接的,因此可以删除任意元素而无需遍历列表。新元素可以添加到列表中,在现有元素之前或之后,也可以添加到列表的头部。列表可以在任意一个方向上遍历。

尾队列(TAILQ)由一对指针引导,一个指向列表的头部,另一个指向列表的尾部。元素是双向链接的,因此可以删除任意元素而无需遍历列表。可以将新元素添加到列表中,在现有元素之前或之后,在列表的开头或结尾。尾队列可以在任何一个方向上遍历。

最后还有一个CIRCLEQ的循环队列,一般用不着,上述的四个队列已经足够使用了。

总共有五种类型的数据结构:单链表、列表、单链尾队列和尾队列。所有五个结构都支持以下功能:

  • 在列表的头部插入一个新条目。

  • 在列表中的任何元素之后插入一个新条目。

  • 从列表的头部删除一个条目。

  • 向前遍历列表。

所有双重链接类型的数据结构(列表和尾队列)还允许:

  • 在列表中的任何元素之前插入一个新条目。

  • 删除列表中的任何条目。

然而:

  • 每个元素需要两个指针而不是一个。

  • 操作的代码大小和执行时间(移除除外)大约是单链接数据结构的两倍。

  • 列表是最简单的双链数据结构,在单链表上只支持上述功能。

尾部队列增加了以下功能:

  • 可以在列表末尾添加条目。

  • 它们可以反向遍历,这是有代价的。

然而:

  • 所有的列表插入和删除都必须指定列表的头。

  • 每个头条目需要两个指针而不是一个。

  • 代码大小比单链表大15%,操作运行速度比单链表慢20%。

另一种类型的数据结构——循环队列——违反了C语言的混叠规则,导致编译错误。所有使用它们的代码都应转换为另一种结构;尾队列通常是最容易转换的。

1.2 功能对比表

下面是一些功能标记:

  • + 意味着这个宏是可用的。
  • - 意味着这个宏不可用。
  • s 意味着这个宏可用但是速率较低(o(n)复杂度)

2.具体说明

2.1 SLIST单向列表详细介绍

BSD queue.h中的SLIST是一种单向链表,它提供了一种简单而高效的数据结构,适用于许多常见的程序场景。下面是从效率、安全性和使用方式三个方面对SLIST的总结:

  1. 效率:SLIST的效率非常高,因为它是一个非常简单的数据结构,它的插入、删除和遍历操作都可以在常数时间内完成。这使得SLIST非常适合于需要高效率的程序场景,如操作系统内核、网络服务器等。
  2. 安全性:在多线程环境下,对于同一个SLIST链表的并发访问,通常需要进行同步和互斥,以确保数据的完整性和正确性。因此,在多线程环境下使用SLIST时,确实需要进行上锁保护。
  3. 使用方式:使用SLIST非常简单,只需要包含头文件<sys/queue.h>即可。SLIST提供了一系列宏,可以用来操作链表,例如SLIST_INIT、SLIST_INSERT_HEAD、SLIST_REMOVE等。这些宏可以在代码中直接使用,非常方便。此外,SLIST还提供了一些辅助宏,例如SLIST_EMPTY和SLIST_NEXT等,可以用来查询链表的状态和访问链表元素。

总的来说,BSD queue.h中的SLIST是一种非常高效、可靠、易用的数据结构,适用于许多常见的程序场景。在程序开发过程中,程序员可以使用SLIST来提高程序的效率和安全性,同时减少开发时间和代码复杂度。

单链表的头是由SLIST_HEAD()宏定义的结构。该结构包含一个指向列表第一个元素的指针。元素是单链接的,以最小的空间和指针操作开销为代价,对任意元素进行O(n)移除。新元素可以添加到现有元素之后,也可以添加到列表的头部。SLIST_HEAD结构体的声明如下:

#define SLIST_HEAD(name, type)                      \
    struct name {                                   \
        struct type *slh_first; /* first element */ \
    }

SLIST_HEAD(HEADNAME, TYPE) head;

其中HEADNAME是要定义的结构的名称,struct TYPE是要链接到列表中的元素的类型。指向列表头的指针稍后可以声明为:

struct HEADNAME *headp;

HEADNAME功能通常不使用,导致以下奇怪的代码(使用匿名结构体):

SLIST_HEAD(, TYPE) head, *headp;

下面是配套其他操作函数:

  • SLIST_ENTRY()宏声明了一个连接列表中的元素的结构。

  • SLIST_INIT()宏初始化由head引用的列表。

  • 列表也可以通过使用SLIST_HEAD_INITIALIZER()宏静态初始化,如下所示:

    SLIST_HEAD(HEADNAME, TYPE) head = SLIST_HEAD_INITIALIZER(head);
    
  • SLIST_INSERT_HEAD()宏将新元素elm插入到列表的头部。

  • SLIST_INSERT_AFTER()宏将新元素elm插入到元素listelm之后。

  • SLIST_REMOVE_HEAD()宏删除由head指向的列表的第一个元素。

  • SLIST_REMOVE_AFTER()宏删除elm之后的列表元素。

  • SLIST_REMOVE()宏删除由head指向的列表中的元素elm。

  • SLIST_FIRST()和SLIST_NEXT()宏可以用来遍历列表:

    for (np = SLIST_FIRST(&head); np != NULL; np = SLIST_NEXT(np, FIELDNAME))
    

或者,为了简单起见,可以使用SLIST_FOREACH()宏:

SLIST_FOREACH(np, head, FIELDNAME)

宏SLIST_FOREACH_SAFE()向前遍历由head引用的列表,将每个元素依次赋值给var。然而,与SLIST_FOREACH()不同的是,SLIST_FOREACH_SAFE()允许删除var并在循环中安全地释放它,而不会干扰遍历。

应该使用SLIST_EMPTY()宏来检查简单列表是否为空。

SLIST_FOREACH()不允许在循环中删除或释放var,因为它会干扰遍历。SLIST_FOREACH_SAFE()存在于bsd中,但不存在于glibc中,它通过允许var安全地从列表中删除并从循环中释放而不干扰遍历来修复此限制。

下面是具体的宏函数定义类型展示:

#include <sys/queue.h>

SLIST_ENTRY(TYPE);

SLIST_HEAD(HEADNAME, TYPE);
SLIST_HEAD SLIST_HEAD_INITIALIZER(SLIST_HEAD head);
void SLIST_INIT(SLIST_HEAD *head);

int SLIST_EMPTY(SLIST_HEAD *head);

void SLIST_INSERT_HEAD(SLIST_HEAD *head,
                       struct TYPE *elm, SLIST_ENTRY NAME);
void SLIST_INSERT_AFTER(struct TYPE *listelm,
                       struct TYPE *elm, SLIST_ENTRY NAME);

struct TYPE *SLIST_FIRST(SLIST_HEAD *head);
struct TYPE *SLIST_NEXT(struct TYPE *elm, SLIST_ENTRY NAME);

SLIST_FOREACH(struct TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);

void SLIST_REMOVE(SLIST_HEAD *head, struct TYPE *elm,
                       SLIST_ENTRY NAME);
void SLIST_REMOVE_HEAD(SLIST_HEAD *head,
                       SLIST_ENTRY NAME);
2.2 SLIST单向列表使用实例

BSD queue.h中的SLIST是一种单向链表的实现,用于在C语言中管理数据结构。使用SLIST需要进行以下步骤:

  1. 定义一个结构体,该结构体应该包含一个SLIST_ENTRY成员,以便将结构体连接到链表中。
  2. 使用SLIST_ENTRY宏定义一个结构体成员,以便将结构体链接到链表中。
  3. 使用SLIST_HEAD宏定义一个链表头,该链表头包含一个SLIST_ENTRY成员。
  4. 使用SLIST_INIT宏将链表头初始化为一个空链表。
  5. 使用SLIST_INSERT_HEAD、SLIST_INSERT_AFTER、SLIST_REMOVE等宏来操作链表中的元素。

SLIST与LIST的主要区别在于SLIST是单向链表,只能从头部插入和删除元素,而LIST是双向链表,可以从头部和尾部插入和删除元素。在使用BSD queue.h中的SLIST时,需要注意以下事项:

  1. 不支持双向遍历:SLIST是单向链表,只能从头部开始遍历,无法反向遍历。
  2. 不支持随机访问:SLIST只能从头部插入和删除元素,因此无法通过索引或指针直接访问链表中的元素。
  3. 不安全:SLIST没有进行越界检查,因此存在指针越界问题,需要注意安全性。
  4. 不支持动态内存分配:SLIST不支持在运行时动态地分配内存,因此需要在编译时确定链表的大小。
  5. 适用性限制:SLIST只适用于单向链表的数据结构,因此不适用于其他类型的数据结构。

总的来说,BSD queue.h中的SLIST是一种简单、高效的单向链表实现。在使用时需要注意其适用性限制和安全性问题。

下面是一个使用示例:

SLIST_HEAD(listhead, entry) head;
struct entry {
	...
	SLIST_ENTRY(entry) entries;	/* Simple list. */
	...
} *n1, *n2, *np;

SLIST_INIT(&head);			/* Initialize simple list. */

n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
SLIST_INSERT_HEAD(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* Insert after. */
SLIST_INSERT_AFTER(n1, n2, entries);

SLIST_FOREACH(np, &head, entries)	/* Forward traversal. */
	np-> ...

while (!SLIST_EMPTY(&head)) {	 	/* Delete. */
	n1 = SLIST_FIRST(&head);
	SLIST_REMOVE_HEAD(&head, entries);
	free(n1);
}
2.3 LIST双向列表详细介绍

列表的头是由LIST_HEAD()宏定义的结构。该结构包含一个指向列表第一个元素的指针。元素是双向链接的,因此可以在不遍历列表的情况下删除任意元素。可以将新元素添加到列表中,在现有元素之后,在现有元素之前,或者在列表的头部。LIST_HEAD结构体的声明如下:

LIST_HEAD(HEADNAME, TYPE) head;

其中HEADNAME是要定义的结构的名称,struct TYPE是要链接到列表中的元素的类型。指向列表头的指针稍后可以声明为:

struct HEADNAME *headp; # (名称head和headp是用户可选择的。)

HEADNAME功能通常不使用,导致以下奇怪的代码:

LIST_HEAD(, TYPE) head, *head;

具有下面的操作:

  • LIST_ENTRY()宏声明了一个连接列表中的元素的结构。

  • LIST_INIT()宏初始化由head引用的列表。

  • 列表也可以通过使用LIST_HEAD_INITIALIZER()宏静态初始化,如下所示:

    LIST_HEAD(HEADNAME, TYPE) head = LIST_HEAD_INITIALIZER(head);
    
  • LIST_INSERT_HEAD()宏将新元素elm插入到列表的头部。

  • LIST_INSERT_AFTER()宏将新元素elm插入到元素listelm之后。

  • LIST_INSERT_BEFORE()宏将新元素elm插入到元素listelm之前。

  • LIST_REMOVE()宏从列表中删除元素elm。

  • LIST_REPLACE()宏将列表元素elm替换为新元素elm2。

  • LIST_FIRST()和LIST_NEXT()宏可以用来遍历列表:

    for (np = LIST_FIRST(&head);np != NULL;np = LIST_NEXT(np, FIELDNAME))
    

或者,为了简单起见,可以使用LIST_FOREACH()宏:

LIST_FOREACH(np, head, FIELDNAME)

宏LIST_FOREACH_SAFE()向前遍历由head引用的列表,将每个元素依次赋值给var。然而,与LIST_FOREACH()不同的是,它允许删除var并将其安全地从循环中释放出来,而不会干扰遍历。

应该使用LIST_EMPTY()宏来检查列表是否为空。

双向列表的使用与单向列表没有多少区别,下面是宏函数定义原型:

#include <sys/queue.h>

LIST_ENTRY(TYPE);

LIST_HEAD(HEADNAME, TYPE);
LIST_HEAD LIST_HEAD_INITIALIZER(LIST_HEAD head);
void LIST_INIT(LIST_HEAD *head);

int LIST_EMPTY(LIST_HEAD *head);

void LIST_INSERT_HEAD(LIST_HEAD *head,
                       struct TYPE *elm, LIST_ENTRY NAME);
void LIST_INSERT_BEFORE(struct TYPE *listelm,
                       struct TYPE *elm, LIST_ENTRY NAME);
void LIST_INSERT_AFTER(struct TYPE *listelm,
                       struct TYPE *elm, LIST_ENTRY NAME);

struct TYPE *LIST_FIRST(LIST_HEAD *head);
struct TYPE *LIST_NEXT(struct TYPE *elm, LIST_ENTRY NAME);

LIST_FOREACH(struct TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME);

void LIST_REMOVE(struct TYPE *elm, LIST_ENTRY NAME);

下面是使用实例:

LIST_HEAD(listhead, entry) head;
struct entry {
	...
	LIST_ENTRY(entry) entries;	/* List. */
	...
} *n1, *n2, *np;

LIST_INIT(&head);			/* Initialize list. */

n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
LIST_INSERT_HEAD(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* Insert after. */
LIST_INSERT_AFTER(n1, n2, entries);

n2 = malloc(sizeof(struct entry));	/* Insert before. */
LIST_INSERT_BEFORE(n1, n2, entries);
					/* Forward traversal. */
LIST_FOREACH(np, &head, entries)
	np-> ...

while (!LIST_EMPTY(&head)) {		/* Delete. */
	n1 = LIST_FIRST(&head);
	LIST_REMOVE(n1, entries);
	free(n1);
}
2.4 STAILQ单向尾队列详细介绍

单链接的尾部队列由STAILQ_HEAD()宏定义的结构作为头部。该结构包含一对指针,一个指向尾队列中的第一个元素,另一个指向尾队列中的最后一个元素。元素是单链接的,以最小的空间和指针操作开销为代价,对任意元素进行O(n)移除。新元素可以添加到尾队列,在现有元素之后,在尾队列的头部或尾队列的末端。STAILQ_HEAD结构声明如下:

STAILQ_HEAD(HEADNAME, TYPE) head;

其中HEADNAME是要定义的结构的名称,struct TYPE是要链接到尾队列的元素的类型。指向尾部队列头部的指针稍后可以声明为:

struct HEADNAME *headp;		# (名称head和headp是用户可选择的。)

下面是一些常见的操作:

  • STAILQ_ENTRY()宏声明了一个连接尾队列中的元素的结构。

  • STAILQ_INIT()宏初始化由head引用的尾部队列。

  • 尾部队列也可以通过使用STAILQ_HEAD_INITIALIZER()宏静态初始化。

  • STAILQ_INSERT_AFTER()宏将新元素elm插入到元素listelm之后。

  • STAILQ_INSERT_HEAD()宏将新元素elm插入到尾部队列的头部。

  • STAILQ_INSERT_TAIL()宏将新元素elm插入到尾部队列的末尾。

  • STAILQ_REMOVE_AFTER()宏删除紧跟在elm后面的队列元素。与STAILQ_REMOVE不同,这个宏不会遍历整个尾部队列。

  • STAILQ_REMOVE_HEAD()宏从尾部队列中删除第一个元素。为了获得最佳效率,从尾部队列头部删除的元素应该显式地使用这个宏,而不是通用的STAILQ_REMOVE宏。

  • STAILQ_REMOVE()宏从尾部队列中删除元素elm。应该避免使用这个宏,因为它遍历整个列表。如果在高使用率的代码路径中需要这个宏,或者在长尾队列上操作,那么应该使用双链接的尾队列。

  • STAILQ_CONCAT()宏将由head2引用的尾部队列的所有元素连接到由head1引用的尾部队列的末尾,在进程中清空head2。这比删除和插入单个元素更有效,因为它实际上不遍历head2。

    STAILQ_FOREACH()宏用于队列遍历:

STAILQ_FOREACH()宏用于队列遍历,宏STAILQ_FOREACH_SAFE()向前遍历由head引用的队列,将每个元素依次赋值给var。然而,与STAILQ_FOREACH()不同的是,它允许删除var并在循环中安全地释放它,而不会干扰遍历。

可以使用STAILQ_FIRST()、STAILQ_NEXT()和STAILQ_LAST()宏手动遍历尾队列或尾队列的任意部分。应该使用STAILQ_EMPTY()宏来检查尾队列是否为空。

下面是这些函数的宏函数原型定义:

#include <sys/queue.h>

STAILQ_ENTRY(TYPE);

STAILQ_HEAD(HEADNAME, TYPE);
STAILQ_HEAD STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head);
void STAILQ_INIT(STAILQ_HEAD *head);

int STAILQ_EMPTY(STAILQ_HEAD *head);

void STAILQ_INSERT_HEAD(STAILQ_HEAD *head,
                        struct TYPE *elm, STAILQ_ENTRY NAME);
void STAILQ_INSERT_TAIL(STAILQ_HEAD *head,
                        struct TYPE *elm, STAILQ_ENTRY NAME);
void STAILQ_INSERT_AFTER(STAILQ_HEAD *head, struct TYPE *listelm,
                        struct TYPE *elm, STAILQ_ENTRY NAME);

struct TYPE *STAILQ_FIRST(STAILQ_HEAD *head);
struct TYPE *STAILQ_NEXT(struct TYPE *elm, STAILQ_ENTRY NAME);

STAILQ_FOREACH(struct TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);

void STAILQ_REMOVE(STAILQ_HEAD *head, struct TYPE *elm, TYPE,
                        STAILQ_ENTRY NAME);
void STAILQ_REMOVE_HEAD(STAILQ_HEAD *head,
                        STAILQ_ENTRY NAME);

void STAILQ_CONCAT(STAILQ_HEAD *head1, STAILQ_HEAD *head2);

下面是使用示例:

STAILQ_HEAD(listhead, entry) head = STAILQ_HEAD_INITIALIZER(head);
struct entry {
	...
	STAILQ_ENTRY(entry) entries;	/* Singly-linked tail queue. */
	...
} *n1, *n2, *np;

n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
STAILQ_INSERT_HEAD(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* Insert at the tail. */
STAILQ_INSERT_TAIL(&head, n2, entries);

n2 = malloc(sizeof(struct entry));	/* Insert after. */
STAILQ_INSERT_AFTER(&head, n1, n2, entries);

					/* Deletion. */
STAILQ_REMOVE(&head, n2, entry, entries);
free(n2);
					/* Deletion from the head. */
n3 = STAILQ_FIRST(&head);
STAILQ_REMOVE_HEAD(&head, entries);
free(n3);
					/* Forward traversal. */
STAILQ_FOREACH(np, &head, entries)
	np-> ...
					/* Safe forward traversal. */
STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
	np-> ...
	STAILQ_REMOVE(&head, np, entry, entries);
	free(np);
}
					/* Delete. */
while (!STAILQ_EMPTY(&head)) {
	n1 = STAILQ_FIRST(&head);
	STAILQ_REMOVE_HEAD(&head, entries);
	free(n1);
}
2.5 TAILQ双向尾队列详细介绍

尾队列的头部由TAILQ_HEAD()宏定义的结构组成。该结构包含一对指针,一个指向尾队列中的第一个元素,另一个指向尾队列中的最后一个元素。元素是双重链接的,因此可以在不遍历尾队列的情况下删除任意元素。新元素可以添加到队列中,在现有元素之后,在现有元素之前,在队列的头部,或在队列的末尾。一个TAILQ_HEAD结构体声明如下:

TAILQ_HEAD(HEADNAME, TYPE) head;

其中HEADNAME是要定义的结构的名称,struct TYPE是要链接到尾队列的元素的类型。指向尾部队列头部的指针稍后可以声明为:

struct HEADNAME *headp; // (名称head和headp是用户可选择的。)

下面是一些操作:

  • TAILQ_ENTRY()宏声明了一个连接尾队列中的元素的结构。

  • TAILQ_INIT()宏初始化由head引用的尾部队列。

  • 尾队列也可以通过使用TAILQ_HEAD_INITIALIZER()宏进行静态初始化。

  • TAILQ_INSERT_HEAD()宏将新元素elm插入到尾队列的头部。

  • TAILQ_INSERT_TAIL()宏将新元素elm插入到尾队列的末尾。

  • TAILQ_INSERT_AFTER()宏将新元素elm插入到元素listelm之后。

  • TAILQ_INSERT_BEFORE()宏将新元素elm插入到元素listelm之前。

  • TAILQ_REMOVE()宏从尾部队列中删除元素elm。

  • TAILQ_REPLACE()宏将列表元素elm替换为新元素elm2。

  • TAILQ_CONCAT()宏将由head2引用的尾部队列的所有元素连接到由head1引用的尾部队列的末尾,在进程中清空head2。这比删除和插入单个元素更有效,因为它实际上不遍历head2。

  • TAILQ_FOREACH()和TAILQ_FOREACH_REVERSE()用于遍历尾部队列。TAILQ_FOREACH()从第一个元素开始,一直到最后一个元素。TAILQ_FOREACH_REVERSE()从最后一个元素开始,向第一个元素前进。

宏TAILQ_FOREACH_SAFE()和TAILQ_FOREACH_REVERSE_SAFE()分别沿正向或反向遍历由head引用的列表,依次将每个元素赋值给var。然而,与它们不安全的对应项不同,它们既允许删除var,也允许在循环中安全地释放它,而不会干扰遍历。

可以使用TAILQ_FIRST()、TAILQ_NEXT()、TAILQ_LAST()和TAILQ_PREV()宏手动遍历尾队列或尾队列的任意部分。

应该使用TAILQ_EMPTY()宏来检查尾队列是否为空

下面是函数原型:

#include <sys/queue.h>

TAILQ_ENTRY(TYPE);

TAILQ_HEAD(HEADNAME, TYPE);
TAILQ_HEAD TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head);
void TAILQ_INIT(TAILQ_HEAD *head);

int TAILQ_EMPTY(TAILQ_HEAD *head);

void TAILQ_INSERT_HEAD(TAILQ_HEAD *head,
                        struct TYPE *elm, TAILQ_ENTRY NAME);
void TAILQ_INSERT_TAIL(TAILQ_HEAD *head,
                        struct TYPE *elm, TAILQ_ENTRY NAME);
void TAILQ_INSERT_BEFORE(struct TYPE *listelm,
                        struct TYPE *elm, TAILQ_ENTRY NAME);
void TAILQ_INSERT_AFTER(TAILQ_HEAD *head, struct TYPE *listelm,
                        struct TYPE *elm, TAILQ_ENTRY NAME);

struct TYPE *TAILQ_FIRST(TAILQ_HEAD *head);
struct TYPE *TAILQ_LAST(TAILQ_HEAD *head, HEADNAME);
struct TYPE *TAILQ_PREV(struct TYPE *elm, HEADNAME, TAILQ_ENTRY NAME);
struct TYPE *TAILQ_NEXT(struct TYPE *elm, TAILQ_ENTRY NAME);

TAILQ_FOREACH(struct TYPE *var, TAILQ_HEAD *head,
                        TAILQ_ENTRY NAME);
TAILQ_FOREACH_REVERSE(struct TYPE *var, TAILQ_HEAD *head, HEADNAME,
                        TAILQ_ENTRY NAME);

void TAILQ_REMOVE(TAILQ_HEAD *head, struct TYPE *elm,
                        TAILQ_ENTRY NAME);

void TAILQ_CONCAT(TAILQ_HEAD *head1, TAILQ_HEAD *head2,
                        TAILQ_ENTRY NAME);

下面是实际示例:

TAILQ_HEAD(tailhead, entry) head;
struct entry {
	...
	TAILQ_ENTRY(entry) entries;	/* Tail queue. */
	...
} *n1, *n2, *np;

TAILQ_INIT(&head);			/* Initialize queue. */

n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
TAILQ_INSERT_HEAD(&head, n1, entries);

n1 = malloc(sizeof(struct entry));	/* Insert at the tail. */
TAILQ_INSERT_TAIL(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* Insert after. */
TAILQ_INSERT_AFTER(&head, n1, n2, entries);

n2 = malloc(sizeof(struct entry));	/* Insert before. */
TAILQ_INSERT_BEFORE(n1, n2, entries);
					/* Forward traversal. */
TAILQ_FOREACH(np, &head, entries)
	np-> ...
					/* Manual forward traversal. */
for (np = n2; np != NULL; np = TAILQ_NEXT(np, entries))
	np-> ...
					/* Delete. */
while ((np = TAILQ_FIRST(&head))) {
	TAILQ_REMOVE(&head, np, entries);
	free(np);
}
05-28 18:13