linked-list - 循环双向链表和尾指针双向链表

Question

使用循环指针和尾指针构建双向链表的优点/缺点是什么？哪个更适合构建双端队列？

在我看来，它们在执行所有搜索、插入和删除节点方面几乎相同。唯一不同的是，对于尾指针双向链表，你需要有一个尾指针指向最后一个节点，并且每次在尾后插入一个新节点时都需要更新它。此外，在循环链表中，第一个节点链接到最后一个节点，反之亦然，而在尾指针中，head->prev 和 tail-> 都指向空指针。我认为它们都非常适合构建双端队列。这一切都取决于您希望程序如何运行。如果你想让你的程序在头节点和尾节点之间快速来回运行，使用循环方式，否则，尾指针就足够了。

这就是我对这个问题的回答。由于我还没有构建任何循环双向链表，所以我对它在机器上的运行方式没有任何经验，但我怀疑它会和尾指针一样快。有什么建议吗？感谢大家的投入。

Answer 1

循环双链表可能是首选，因为您可以从开头或结尾高效地添加/删除，并且它使用简单统一的数据结构。

实现循环 dbl 链表的最简单方法是持有一个与所有其他节点类型相同的“头”节点，但始终具有“空”项/值并且仅用于保存下一个/上一个指向实际“项目节点”的指针。

当链表为空时，head.next & head.prev 都会指向它自己。

与允许“head”和“tail”为空时为 null 的尾指针变体相比，循环 dbl 链表的逻辑更简单；这需要在任何修改操作中都可能更新“头”和“尾”指针，从而使逻辑更加复杂。

此处的命名有点不清楚:我使用 head 来引用“列表节点”，但它可以称为“列表”或“节点”。

head.next -> first -> second -> ...
head.last -> last -> second-last -> ...

如果列表为空:

head.next -> head
head.last -> head

如果列表只有一项:

head.next -> item -> head
head.last -> item -> head