3

最近，我看到了这个：

struct node {
    node*  pNext;
    node** pPrevNext;
};

void insert_before(node** pNext, node* toInsert) {
    toInsert->pNext = *pNext;
    toInsert->pPrevNext = pNext;
    if (*pNext) (*pNext)->pPrevNext = &toInsert->pNext;
    *pNext = toInsert;
};

// node *a, *b;
// insert_before(a->pPrevNext, b);

它看起来像一个单链表，但包含指向前一个节点的下一个指针的指针。我的问题很简单：这叫什么？没有它的“真名”，在 StackOverflow 和整个互联网上搜索有关此数据结构的信息都是空的。

请注意，它不是一个双向链表，如下所示：

struct node {
    node* pNext;
    node* pPrev;
};
4

4 回答 4

6

它被称为双向链表，因为它有两个指针。您可以从宏中获取前一个节点，container_of(*node.pPrevNext, node, pNext)因此它在逻辑上也等同于标准的双向链表。

注意：有趣的问题是异或列表被认为是单链接还是双链接？见XOR 双链表

于 2012-08-04T02:32:36.973 回答
1

我认为没有任何标准名称。它是双向链表的一种受限版本，因为您可以在完整的双向链表中遍历指针以获取此处可用的所有信息。

于 2012-08-04T01:47:24.613 回答
1

它是一个单链表，允许在 O(1) 时间内删除一个节点，或者在其前面插入一个节点。它没有名字，因为没有理由使用它……双向链表更好。

于 2012-08-04T04:41:06.733 回答
0

它是一个单链表，旨在表现得像一个双链表。您可以通过以下方式删除元素

*pPrevNext = pNext;

唯一阻止它成为双向链表的是作者对这个概念的理解不足。

于 2012-08-04T02:35:54.040 回答