Why does the doubly linked list in sys/queue.h maintain the address of previous next element?

Question

I'm studying sys/queue.h from FreeBSD and I have one question:

In sys/queue.h, LIST_ENTRY is defined as follows:

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

Why does it maintain the address of previous next element (struct type **le_prev) rather than simply previous elment like struct type *le_prev?

Answer 1

If you would have read the queue.h file from the beginning, you may have got following comment:

 * 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, which provides O(1) insertion and deletion, but only forward traversal. To achieve this, you only need the reference to the previously next pointer, which is exactly what is implemented.

Answer 2

Let me try to explain. Actually the **le_prev* affords ablity to list defined by sys/queue.h to insert_before that forward-list can not. Compared with insert_before, the insert_after can both be implemented well in forward-list or list. So list is more functional.

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