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

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

sys/queue.hLIST_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那样的前一个元素

如果你从一开始就读过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)插入和删除,但只提供正向遍历。 要实现这一点,您只需要引用前一个下一个指针,这正是实现的指针。

让我试着解释一下。 实际上, **le_prev*提供了由sys / queue.h定义的列表到insert_before ,而forward-list不能。 与insert_before相比, insert_after可以在前向列表或列表中很好地实现。 因此列表更具function性。

 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; }