c-为什么BSD在链表条目中使用双指针

Question

这是双链表中一个条目的BSD实现吗？

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

他们为什么使用双指针？为什么不只是

#define LIST_ENTRY(type)                        
struct {                                
struct type *le_next, *le_prev;     
}

我看不出有什么问题，而且在我看来它看起来更简单，所以为什么不使用它呢？我是不是错过了什么？

Answer 1

为什么要使用双指针？

源文件包含相当好的解释性注释。适用于这种特定类型的数据结构的有：

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

有几个关键的事情需要注意，其中包括：

1. 即使节点有可以访问前一个节点的指针，这种列表也仅用于前向遍历。

2. 列表由一个指针引导。这意味着，并且可以在源代码的其他地方验证，单个指针不是列表节点对象的成员。

3. 双连杆机构的原因称为"；从而可以在不需要遍历列表的情况下移除任意元素"；。只要读一下行与行之间的一点，我们就可以认为这意味着，如果我有一个指向节点的指针，那么我可以在列表遍历的上下文之外，从它所属的列表中删除该节点，并且即使它是列表中的第一个节点。

   在这方面要注意，这样的列表中的第一个节点不具有struct type *可以指向的前置节点(参见上面的(2((，但是对于要在这样的列表内的节点，无论是在另一个节点中还是在列表对象中，都必须有指向它的struct type *。给定指向该指针的struct type **，我们可以通过直接修改该指针而不是通过包含该指针的结构来实现删除

4. 可以在任何节点之前或之后添加新元素。与双指针有助于删除第一个节点的原因大致相同，它也有助于在第一个节点之前插入新节点——同样，无需遍历列表，也无需知道节点实际上是第一个，甚至不知道它属于哪个列表

为什么不只使用

#define LIST_ENTRY(type)                        
struct {                                
struct type *le_next, *le_prev;     
}

我看不出有什么问题，而且在我看来它看起来更简单，那么为什么不使用它呢？我是不是错过了什么？

这将是双链表中节点的常规形式。它可以提供与上面(3(和(4(中描述的相同的移除和插入语义，前提是列表是用伪头节点构造的。然而，BSD在实践中如何使用这个LIST_ENTRY宏来定义列表的细节对我来说有点模糊，所以可能有一个原因导致了伪头节点不可行。或者，这种选择只是为了提高一点空间效率。

无论如何，这不是列表的结构(请参见(2((。给定列表头的所选结构，需要用于先前节点的双指针结构来服务于该列表及其节点((3(和可能(4((的所述目的。因为列表只在向前的方向上遍历，所以双指针结构不是一个障碍。