我被要求实现一个双向链表队列,但是我知道使用单链表队列可以在大O符号为1的情况下轻松地运行其所有主要功能。 我基本上是在谈论FIFO实现(不包括像deque这样的特殊队列)。
我已经看到其他人使用双向链接实现队列,我知道这会消耗更多的存储空间,因为每个节点都需要2个指针(prev和next)。
是否有优势使用双向链表队列而不是单向链表队列?!
我被要求实现一个双向链表队列,但是我知道使用单链表队列可以在大O符号为1的情况下轻松地运行其所有主要功能。 我基本上是在谈论FIFO实现(不包括像deque这样的特殊队列)。
我已经看到其他人使用双向链接实现队列,我知道这会消耗更多的存储空间,因为每个节点都需要2个指针(prev和next)。
是否有优势使用双向链表队列而不是单向链表队列?!
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
优点在于您可以在双向链表上任意迭代。此外,如果数据对象具有相当大的大小,则额外的内存开销不会占用大量百分比。