Perché la lista doppiamente collegata in sys/queue.h mantiene l'indirizzo del precedente elemento successivo?

Question

Sto studiando sys/queue.h da FreeBSD e ho una domanda:

In sys/queue.h, LIST_ENTRY è definito come segue:

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

Perché si mantiene l'indirizzo della precedente prossimo elemento (struct type **le_prev) piuttosto che semplicemente precedente elemento come struct type *le_prev?

Answer 1

Se avete letto il file queue.h fin dall'inizio, si può hai seguente commento:

* 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. 

così lista, che fornisce O (1) l'inserimento e cancellazione, ma solo in avanti attraversamento. Per ottenere ciò, è sufficiente il riferimento al puntatore precedente, che è esattamente quello che è implementato in .

Answer 2

Lasciami provare a spiegare. In realtà il **le_prev* offre ablity l'elenco definito da sys/queue.h a insert_before che l'elenco di inoltro non può. Rispetto allo insert_before, lo insert_after può essere implementato bene in forward-list o in elenco. Quindi la lista è più funzionale.

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