7.2.4　双向链表是如何实现的

本节将说明ngx_queue_t链表容器以及元素中prev成员、next成员的意义，整个链表就是通过这两个指针成员实现的。

下面先来看一下ngx_queue_t结构体作为容器时其prev成员、next成员的意义。当容器为空时，prev和next都将指向容器本身，如图7-2所示。

如图7-2所示，如果在某个结构体中定义了ngx_queue_t容器，其prev指针和next指针都会指向ngx_queue_t成员的地址。

图　7-2　空容器时ngx_queue_t结构体成员的值

当容器不为空时，ngx_queue_t容器的next指针会指向链表的第1个元素，而prev指针会指向链表的最后1个元素。如图7-3所示，这时链表中只有1个链表元素，容器的next指针和prev指针都将指向这个唯一的链表元素。

图　7-3　当仅含1个元素时，容器、元素中的ngx_queue_t结构体成员的值

对于每个链表元素来说，其prev成员都指向前一个元素（不存在时指向链表容器），而next成员则指向下一个元素（不存在时指向链表容器），这在图7-3中可以看到。

当容器中有两个元素时，prev和next的指向如图7-4所示。

图　7-4　当含有两个或多个元素时，容器、元素中的ngx_queue_t结构体中prev、next成员的值

图7-4很好地诠释了前面的定义，容器中的prev成员指向最后1个也就是第2个元素，next成员指向第1个元素。第1个元素的prev成员指向容器本身，而其next成员指向第2个元素。第2个元素的prev成员指向第1个元素，其next成员则指向容器本身。

ngx_queue_t的实现就是这么简单，但它的排序算法ngx_queue_sort使用的插入排序，并不适合为庞大的数据排序。