c - 为什么sys/queue.h中的双向链表会维护previous next元素的地址？

Question

我在学习sys/queue.h来自 FreeBSD，我有一个问题:

在sys/queue.h , LIST_ENTRY 定义如下:

#define LIST_ENTRY(type)                        \
struct {                                \
    struct type *le_next;   /* next element */          \
    struct type **le_prev;  /* address of previous next element */  \
}

为什么它维护上一个下一个元素的地址(struct type **le_prev)而不是像那样简单地保持上一个元素结构类型 *le_prev?

Answer 1

如果您从头开始阅读 queue.h 文件，您可能有以下评论:

 * A list is headed by a single forward pointer (or an array of forward
 * pointers for a hash table header). The elements are doubly linked
 * so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before
 * or after an existing element or at the head of the list. A list
 * may only be traversed in the forward direction.

so列表，提供了O(1)的插入和删除，但只能向前遍历。为此，您只需要引用先前的下一个指针，这正是实现。