如果一个Queue有一个链表，但是链表只有head的引用，那么入队和出队的运行时间是多少？

Question

如果一个队列是用链表实现的，但是链表只有一个参考头，入队的运行时间是多少？运行出队时间？

Answer 1

让我们从 Wikipedia's article on Queue 的引述开始：

There are several efficient implementations of FIFO queues. An efficient implementation is one that can perform the operations—en-queuing and de-queuing—in O(1) time.

Linked list

[...]

A regular singly linked list only has efficient insertion and deletion at one end. [...]

这才是精髓。由于入队和出队操作影响列表两端的列表，而我们只有这两端之一的引用，我们将不得不“走到”另一端才能在那里进行其他操作。

我们可以选择 linked 列表的哪一端作为项目入队（添加）的一端，而另一端作为项目出队（提取）的地方。 linked 列表的 head 可以是 -- 这是一个设计选择。

假设 enqueue 将在 linked 列表的末尾添加一个条目 （在当前尾部之后列表的），并且 dequeue 将 return 头部条目，并从列表中删除该节点。那么代码将是这样的——我使用 Python 作为示例：

class Node: def __init__(self, value): self.value = value self.next = None class Queue: def __init__(self): self.head = None def enqueue(self, value): if self.head is None: self.head = Node(value) else: node = self.head while node.next is not None: node = node.next node.next = Node(value) def dequeue(self): if self.head is None: raise ValueError("Queue is empty") else: value = self.head.value self.head = self.head.next return value

所以对于enqueue，我们需要遍历链表，从head节点开始，找到链表的尾部在哪里。然后我们为给定值创建一个节点，并在该尾节点之后 link 它，使列表的一个条目更长。由于我们需要遍历整个列表才能执行加法，因此时间复杂度为 O(n)。

对于dequeue，我们马上就有了我们需要获取值的节点：它是head节点。所以这里不需要遍历list。我们只需要更改 head 引用，使其指向列表中的下一个节点，从中删除第一个节点。此操作的时间复杂度为 O(1)。

现在，我们还可以采用替代设计决策，其中 linked 列表将向另一个方向增长，并且 enqueue 将在当前 head 之前添加一个新节点节点。然后 dequeue 方法必须获取尾节点中的值并从列表中删除该尾节点。如您所见，现在 enqueue 操作的时间复杂度为 O(1)，而 dequeue 的时间复杂度为 O(n)。

因此无论哪种方式，都会有两者之一的时间复杂度为 O(n)，而另一个的时间复杂度为 O(1)。

Answer 2

实际上可以构建一个由链表支持的队列，该链表仅存储指向链表头部的指针，但入队和出队都需要时间 O(1)。这个想法是使用一个循环链接的双向链表，这样列表的第一个元素向后指向最后一个元素，列表的最后一个元素向前指向第一个元素。例如：

head
 |    +---+     +---+     +---+     +---+
 +--> | 1 | <-> | 2 | <-> | 3 | <-> | 4 |
      +---+     +---+     +---+     +---+
        ^                             ^
        |                             |
        +-----------------------------+

要在时间 O(1) 中执行出列，我们只需删除并 return 第一个链表单元格。正如我们所做的那样，我们在它之前和之后重新连接单元格以指向另一个单元格，如下所示：

head -------------+
                  |
                  v
                +---+     +---+     +---+
                | 2 | <-> | 3 | <-> | 4 |
                +---+     +---+     +---+
                  ^                   ^
                  |                   |
                  +-------------------+

要在时间 O(1) 中执行入队，请在第一个元素和最后一个元素之间插入一个新值，如下所示：

head -------------+
                  |
                  v
                +---+     +---+     +---+
                | 2 | <-> | 3 | <-> | 4 |
                +---+     +---+     +---+
                  ^                   ^
                  |       +---+       |
                  +-----> | 5 | <-----+   
                          +---+

我会将实际的指针杂耍细节留给您来解决，但它们非常简单，可以说比常规链表队列更容易，因为要检查的边界条件更少。

如果一个Queue有一个链表，但是链表只有head的引用，那么入队和出队的运行时间是多少？

If a Queue had a linked list, but the linked list only had a reference to head, what would be the running time of enqueue and dequeue?

queue

linked-list

data-structures