为什么Linux使用这个"指针指针"列表？

Question

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

我发现上面的代码使用指针指针,这不是唯一的.我想知道为什么这样做？指针本身无法处理它？

Answer 1

我想这里的重点是删除元素.考虑您有一个单链表,这意味着您可以在其整个节点中转发导航.

现在考虑N_j要删除的通用列表节点(例如).删除它之后,你想轻松地链接前一个节点(比如N_{j-1})到下一个(说N_{j+1}).因此,你需要修改字段tqe_next:前一节点N_{j-1}需要一个指向它,即在指针的指针 tqe_prev在N_j.

换句话说,在伪代码术语中,以下内容成立

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

要么

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

.