循环双向链表和尾指针双向链表

Question

使用循环指针和尾指针构建双向链表有什么优缺点？哪种方法更适合构建deque？

在我看来，无论是使用循环指针还是尾指针构建双向链表，在搜索、插入和删除节点方面都没有太大区别。唯一不同的是，在使用尾指针的双向链表中，你需要让尾指针指向最后一个节点，并且每次在尾部插入新节点时都需要更新它。此外，在循环链表中，第一个节点与最后一个节点互相链接，而在尾指针中，头部的prev指针和尾部指针都指向空指针。

我认为两种方法都适用于构建deque。这完全取决于你想要程序如何运行。如果你希望程序能够快速地在头部和尾部节点之间移动，那么使用循环方法会更好，否则，尾指针应该已经足够了。

这就是我的答案。由于我还没有构建过任何循环双向链表，所以我没有任何关于它在机器上运行的经验，但我认为它的速度应该和尾指针一样快。有什么建议吗？感谢大家的意见。

- Hoang Minh

Answer 1

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

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

当列表为空时，head.next和head.prev将都指向自身。

循环双向链表的逻辑比尾指针变体更简单，后者允许在空时'head'和'tail'都为null；这就要求在任何修改操作中都有可能更新'head'和'tail'指针，使逻辑更加复杂。

命名有点不清晰：我使用“head”来指代'list node'，但它也可以称为'list'或'node'。

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

如果列表为空：

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

如果列表只有一个项目：

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

- Thomas W

---

循环双向链表在头部前后插入节点的算法是什么？它们不是一样的吗？因为在循环链表中，实际上根本不需要跟踪尾部，最后一个节点可以连接到第一个节点，反之亦然。 - Hoang Minh

在任何位置插入节点的算法相同，您需要获取一个“prev”参数并在其后插入。要插入第一个节点，您需要传递“head”。要插入最后一个节点，您需要传递“head.prev”。插入函数必须更新前一个节点的“next”指针、下一个节点的“prev”指针，以及设置插入节点的“next/prev”指针。完成任务。 - Thomas W