双链接队列比单链接队列有什么优势吗? [英] Is there any advantage of doubly linked queue over singly-linked queue?

问题描述

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

I have been asked to implement a doubly linked queue, but I know a singly-linked queue is straightforward with all of its major functions running in big-Theta 1. I am basically talking about FIFO implementation (not including special queues like deque).

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

I have seen other people implementing the queue using doubly-link implementation and I know this consumes more storage since each node requires 2 pointers (prev & next).

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

Is there any advantage of doubly linked queue over singly-linked queue?!

推荐答案

你不需要双端 LL 而不是双端 LL.双端 LL(具有指向头部和尾部的指针)就足够了.

You do not need a Doubly LL over a Double ended LL. A double ended LL (has pointer to head and tail) suffices.

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

For FIFO, the main operations are enqueue and dequeue. In linked list terms, this is add_to_end and remove_from_front. Both of these are O(1) operations with a double ended linked list.

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

If you needed a data structure that could operate both as a queue and a stack, then you would need a doubly linked list to get O(1) operations. The main operation that would take O(n) without a doubly linked list is remove_from_end/pop. The reason for this is that you would have to find the node one previous from the last (node3 in example below), set it to the tail and then remove its pointer to the node that you are removing. With a doubly LL, it is as simple as tail.prev to find this node; however, with a double ended LL, you would have to do a O(n) traversal to find that node.

前 1 - 2 - 3 - 4 最后

First 1 - 2 - 3 - 4 Last

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

这篇关于双链接队列比单链接队列有什么优势吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！