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

Question

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

从我的观点来看，他们在做所有搜索，插入和删除节点方面基本相同。唯一不同的是，对于尾指针双链表，您需要将尾指针指向最后一个节点，并且每次在尾部之后插入新节点时都需要更新它。此外，在循环链表中，第一个节点链接到最后一个节点，反之亦然，而在尾指针中，head-> prev和tail->指向空指针。 我认为他们都是建立一个deque的greate。这一切都取决于你希望你的程序运行的方式。如果你希望你的程序能够快速地在头尾节点之间来回运行，使用循环方式，否则尾指针应该足够。

这是我对这个问题的回答。由于我还没有建立任何循环双向链表，我没有任何关于它在机器上运行的经验，但我怀疑它会像尾指针一样快。任何建议？并感谢大家的投入。

Answer 1

圆形双链表可能是首选，因为您可以有效地从开始或结束添加/删除，并且它使用简单的统一数据结构。

实现循环dbl链表的最简单方法是容纳与所有其他节点相同类型的'head'节点，但始终具有'null'项/值，并且仅用于容纳下一个/ prev指向实际的“项目节点”。

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

对于循环的dbl-linked列表，逻辑更简单，而不是尾指针变体，允许'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