c - 这两种不同的双链表实现方式有什么区别？

Question

我遇到过两种实现双链表的方法:

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

这种方式在FreeBsd queue.h中，我想知道为什么它使用指向指针le_prev的指针？

struct list_head {
    struct list_head *next, *prev;
};

这种方式在linux list.h中，它只是使用了两个简单的指针。

有什么区别？哪个更好，只使用一个简单的指针和一个指向指针的指针或两个简单的指针？

Answer 1

列表不是“双向链接”的，因为列表不能双向遍历。给出双指针，以便快速改变下一个指针。

此外，在 c 中，结构元素始终连续存储。所以给定下一个指针的地址，就可以计算出上一个节点的地址。但这只会增加代码的复杂性，并且需要您计算结构中所有元素的大小。这不值得麻烦。 (你不应该假设这个并说它是一个具有 2-side 遍历的链表)

Which is better?

用两个简单的指针实现通常更好。可能存在双指针实现可能更好的特殊情况。