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

Question

我被要求实现一个双向链表队列，但是我知道使用单链表队列可以在大O符号为1的情况下轻松地运行其所有主要功能。 我基本上是在谈论FIFO实现（不包括像deque这样的特殊队列）。

我已经看到其他人使用双向链接实现队列，我知道这会消耗更多的存储空间，因为每个节点都需要2个指针（prev和next）。

是否有优势使用双向链表队列而不是单向链表队列？！

- Ellysherh Kingdom

---

你听说过双端队列吗？在这种情况下，用户可以从两端进行入队和出队操作。这是应用程序特定的。 - Lalit Verma

你可以通过此链接查看同样的内容：http://www.geeksforgeeks.org/doubly-linked-list/ - ankitkhandelwal185

我知道双端队列（deque），但我的关注点在FIFO的普通队列实现上。@LalitVerma - Ellysherh Kingdom

对于普通的列表结构，实现双向链表总是有优势的，但我的问题基于队列实现，因为该函数与列表不同。 - Ellysherh Kingdom

Answer 1

您不需要在双端链表中使用双向链表。双端链表（具有指向头和尾的指针）就足够了。

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

如果您需要一种既可以作为队列又可以作为堆栈操作的数据结构，则需要一个双向链表以获得O(1)操作。如果没有双向链表，则需要O(n)操作的主要操作是remove_from_end/pop。原因是您必须找到倒数第二个节点（以下示例中的node3），将其设置为尾部，然后删除其指向要删除的节点的指针。使用双向链表，只需tail.prev即可找到此节点；但是，使用双端链表，您必须进行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

- JaTo

---

为什么不使用双端链表的开头作为栈的开放端？使用双端链表，您可以在O(1)时间内在两端插入，也可以在O(1)时间内从开头删除。 - Stefan Octavian

Answer 2

优点在于您可以在双向链表上任意迭代。此外，如果数据对象具有相当大的大小，则额外的内存开销不会占用大量百分比。

- Dragonthoughts

---

如何在单向链队列中从任一端进行出队操作，而无需从开头迭代到结尾？ 您需要知道指向末尾的指针以将其变为新的末尾。 - Dragonthoughts

@Dragonthoughts 你想要对指针做什么？我不需要触碰中间的任何东西，我只需要指向第一个和最后一个元素的指针。当前的最后一个元素指向下一个元素，如果我从队列中取出它，我会从那里得到下一个“最后”指针。当我在前面插入时，我也有指向该项目的指针，以将其“下一个”属性更改为刚插入的元素。无需迭代或触摸中间的任何内容。 - Mörre

当您使用“最后指针”进行deque操作时，如何确定“最后指针”的新值？新的“最后指针”应该是返回项之前的项的指针，因此在单向链表中，您需要迭代到该元素以查找其地址，并执行必要的清理工作以防止它指向已出队的项。 - Dragonthoughts

@Dragonthoughts 如果从头部出队并从尾部入队，那么SLL会起作用吗？因为只删除了头部而没有删除尾部。 - user4779

不完全正确，@user4779，因为在SLL上，您不一定拥有指向最后一个元素的指针，尽管对于这种情况来说这是个好主意，但除非您自己编写代码，否则您将依赖于库的实现。 - Dragonthoughts