Why does Linux use this "pointer to pointer" for list?

Question

#define TAILQ_ENTRY(type)                       \
struct {                                \
    struct type *tqe_next;  /* next element */          \
    struct type **tqe_prev; /* address of previous next element */  \
}

I find above code which uses pointer to pointer, and this is not the only one. I want to know why do so? Pointer itself cannot handle it?

Answer 1

I guess the point here is deleting elements. Consider that you have a singly linked list, which means that you are able to forward navigating throughout its nodes.

Now consider a generic list node (say N_j) which you want to delete. After deleting it you want to easily link the previous node (say N_{j-1}) to the next (say N_{j+1}). Thus, you need to modify the field tqe_next of the previous node N_{j-1} which requires a pointer to it, i.e. the pointer to pointer tqe_prev in N_j.

In other words, in pseudo-code terms, the following holds true

 *(N_j.tqe_prev) ==  (N_{j-1}).tqe_next

or

 N_j.tqe_prev ==  &(N_{j-1}).tqe_next

.