使用循环指针和尾指针构建双向链表的优点/缺点是什么?哪个更适合构建双端队列?
在我看来,它们在执行所有搜索、插入和删除节点方面几乎相同。唯一不同的是,对于尾指针双向链表,你需要有一个尾指针指向最后一个节点,并且每次在尾后插入一个新节点时都需要更新它。此外,在循环链表中,第一个节点链接到最后一个节点,反之亦然,而在尾指针中,head->prev 和 tail-> 都指向空指针。 我认为它们都非常适合构建双端队列。这一切都取决于您希望程序如何运行。如果你想让你的程序在头节点和尾节点之间快速来回运行,使用循环方式,否则,尾指针就足够了。
这就是我对这个问题的回答。由于我还没有构建任何循环双向链表,所以我对它在机器上的运行方式没有任何经验,但我怀疑它会和尾指针一样快。有什么建议吗?感谢大家的投入。
最佳答案
循环双链表可能是首选,因为您可以从开头或结尾高效地添加/删除,并且它使用简单统一的数据结构。
实现循环 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
关于linked-list - 循环双向链表和尾指针双向链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19781288/