双链队列与单链队列相比有什么优势吗？

Question

我被要求实现一个双链接队列，但我知道单链接队列很简单，它的所有主要功能都运行在big-Theta 1中。我基本上是在谈论FIFO实现(不包括像deque这样的特殊队列)。

我见过其他人使用双链接实现队列，我知道这会消耗更多的存储空间，因为每个节点需要2个指针(prev & next)。

双链队列比单链队列有什么优势吗？！

Answer 1

您不需要在双端LL上使用双LL。双端LL (具有指向头部和尾部的指针)就足够了。

对于FIFO，主要操作是入队和出队。在链表术语中，这是add_to_end和remove_from_front。这两个操作都是具有双端链表的O(1)操作。

如果您需要一个既可以作为队列又可以作为堆栈操作的数据结构，那么您将需要一个双向链表来获得O(1)操作。没有双向链表需要O(n)的主要操作是remove_from_end/pop。这样做的原因是，您必须从最后一个节点(在下面的示例中为node3)中找到前一个节点，将其设置为尾部，然后移除指向要删除的节点的指针。使用双LL，查找该节点就像tail.prev一样简单；但是，使用双端LL，您必须执行O(n)次遍历才能找到该节点。

前1-2-3-4末尾

def remove_from_end():
# get node4 and remove node4 from being the tail. O(1) time as you have a pointer to the tail in a double ended LL.
# set tail node3 and remove the .next from node3 to node4. If you don't have .prev on node4, then it would take O(n) to find node3

Answer 2

优点是，您可以在双向链表的任一方向上进行迭代。此外，如果数据对象很大，那么额外的内存开销不是很大的百分比。