Warum behält die doppelt verknüpfte Liste in sys/queue.h die Adresse des vorherigen nächsten Elements?

Question

Ich sys/queue.h von FreeBSD zu studieren, und ich habe eine Frage:

In sys/queue.h wird LIST_ENTRY wie folgt definiert:

#define LIST_ENTRY(type)      \ 
struct {        \ 
    struct type *le_next; /* next element */   \ 
    struct type **le_prev; /* address of previous next element */ \ 
} 

Warum es die Adresse des vorherigen nächsten Elements wird beibehalten (struct type **le_prev) anstatt einfach vorherige elment wie struct type *le_prev?

Answer 1

Wenn Sie die Queue.h Datei von Anfang an gelesen haben würden, können Sie haben folgenden Kommentar:

* 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 Liste, die O (1) Einfügen und Löschen bietet, aber nur nach vorne Durchquerung. Um dies zu erreichen, benötigen Sie nur den Verweis auf den zuvor nächsten Zeiger, der genau implementiert ist.

Answer 2

Lassen Sie mich versuchen zu erklären. Tatsächlich bietet die **le_prev* Fähigkeit, Liste, die von sys/queue.h bis insert_before definiert ist, dass Forward-Liste nicht kann. Im Vergleich zu insert_before kann die insert_after sowohl in Vorwärts-Liste als auch in Liste gut implementiert werden. Die Liste ist also funktionaler.

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