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

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）的地址而不是简单的前一个元素的地址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)的插入和删除，但只是前向遍历。要实现这一点，您只需要对先前的 next 指针的引用，这正是实现的内容。

Answer 2

让我试着解释一下。实际上，**le_prev*提供由 sys/queue.h 定义的列表到insert_before该转发列表的能力不能。与 相比insert_before，insert_after在 forward-list 或 list 中都可以很好地实现。所以列表更实用。

insert_before(entry* list_elem, entry* elem, type val)
{
    elem->next = list_elem;
    *(list->prev) = elem;
    elem->prev = *(list->prev);
    list_elem->prev = elem->next;
}
insert_after(entry* list_elem, entry* elem, type val)
{
    if( ((elem)->next= (list_elem)->next) != NULL ) {
        (elem_list)->next->prev = &(elem)->next;
    }
    (list_elem)->next =  elem;
    elem->prev =  &(list_elem)->next;
}