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

我正在学习从FreeBSD的sys/queue.h和我有一个问题：为什么sys/queue.h中的双链表保持上一个元素的地址？

在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？

来源

2013-05-08 Yanzhe Chen

，如果您已经阅读从一开始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.

所以列表，它提供了O（1）插入和删除，但只能向前遍历。为了达到这个目的，您只需要参考以前的下一个指针，这正是实现的。

来源

2013-05-08 12:47:37

您的意思是说这个实现是为了防止反向遍历以及获得O（1）的插入和删除吗？ – 2013-05-08 12:52:12

@YanzheChen（线性）列表操作的复杂性在使用单个指针时不会改变，并且双指针不会阻止向后遍历。我认为，重要的部分是“或一系列前锋指针”;当具有这样的（散列表）表格时，当先前指针的地址被存储时移除更便宜。 – ensc 2013-12-31 12:27:42

@ensc我读了这[post]（http://stackoverflow.com/questions/9362896/deleting-any-node-from-a-single-linked-list-when-only-pointer-to-that-node- is-gi），并且明白如果它不是尾节点，则可以在O（1）中实现单链表中的删除。但是，为什么双指针不**防止向后遍历？如何执行反向遍历？我不明白**你提到的重要部分**。你能详细解释一下吗？ – 2014-01-01 06:34:29

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

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

来源

2017-08-10 14:48:23 Ding

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

回答

相关问题