用于各种数据结构的最差情况

Question

我正在编译不同数据结构上操作效率的列表。 到目前为止，我有这样的：

我不敢肯定我在这里得到了队列的链表和堆栈的链表。任何人都可以借此深入了解这个问题吗？

Answer 1

唯一的错误是Pop对于Queue as Linked List with pointer to front应该是O(1)。

为了完整起见，它可能是值得的，列出的操作的复杂性，如搜索任何元件，除去任何元件，由索引得到的，由索引中删除等

Queue作为链表（指针到前）：

推送：您需要在末尾插入一个元素，但你只有一个指针开始，所以你需要通过所有元素来重复，以到达终点。

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

流行：您需要删除的元素在开始的时候，所以你应该这样做，只需重新分配的指针开​​始到第二个元素。

removedItem = head 
head = head.next 

队列为链表（指针正面和背面）：

推送：您需要在末尾插入一个元素，并有一个指针到结束，所以你可以在不变的时间添加它。

tail.next = newItem 
tail = newItem 

流行：同流行的单链表。

removedItem = head 
head = head.next 

堆栈作为链表：

推送：在开头插入一个项目，容易在固定时间做。

newItem.next = head 
head = newItem 

流行：删除的第一个项目，容易在固定时间做。

removedItem = head 
head = head.next 

堆栈作为数组：

推送：在最后一个索引插入项目，容易在固定时间做。

last = last+1 
array[last] = newItem 

流行：去年指数删除项目，容易在固定时间做。

removedItem = array[last] 
last = last-1