为什么sys/queue.h中的双向链表保持前一个下一个元素的地址？

Question

我正在sys/queue.h从FreeBSD 学习,我有一个问题:

In 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),而不是简单地以前elment样struct type *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 list,提供O(1)插入和删除,但只提供正向遍历.要实现这一点,您只需要引用前面的下一个指针,这正是实现的指针.