data-structures - 各种数据结构的最坏情况

Question

我正在编译一个列表，以提高对不同数据结构的操作效率。到目前为止，我有这个：

我不太确定我在这里为作为链表的队列和作为链表的堆栈提供了什么。任何人都可以对这个问题有任何见解吗？

score 1 · Accepted Answer

唯一的错误是PopforQueue as Linked List with pointer to front应该是O(1).

为了完整起见，列出操作的复杂性可能是值得的，例如搜索任何元素、删除任何元素、按索引获取、按索引删除等。

队列为链表（指向前面的指针）：

Push：你需要在末尾插入一个元素，但是你只有一个指向开头的指针，所以你需要遍历所有元素才能到达末尾。

current = head
while (current.next != null)
  current = current.next
current.next = newItem

Pop：您需要删除开头的元素，因此您只需将指向开头的指针重新分配给第二个元素即可。

removedItem = head
head = head.next

队列为链表（指向前后的指针）：

Push：你需要在末尾插入一个元素，并且你有一个指向末尾的指针，所以你可以在恒定时间内添加它。

tail.next = newItem
tail = newItem

Pop：与单链表的 pop 相同。

removedItem = head
head = head.next

堆栈为链表：

Push：在开头插入一个项目，很容易在恒定时间内完成。

newItem.next = head
head = newItem

弹出：删除第一项，容易在恒定时间内完成。

removedItem = head
head = head.next

堆栈为数组：

Push：在最后一个索引处插入item，很容易在恒定时间内完成。

last = last+1
array[last] = newItem

弹出：删除最后一个索引的项目，容易在恒定时间内完成。

removedItem = array[last]
last = last-1

1 回答 1