爲什麼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中的雙鏈表保持上一個元素的地址？

回答

相關問題