使用鏈接列表實現的堆棧ADT的時間複雜度

Question

使用LinkedList實現的Stack抽象數據類型的put（x）和get（）函數的時間複雜度是多少？

我首先想到的是他們都是O（1）。但是，如果get（）必須從頭節點遍歷到列表中的最後一個元素以找到要移除並返回的元素，則get（）函數將爲O（n）。

put（x）函數也必須遍歷整個列表才能找到最後一個節點，它將安裝一個新節點。所以這也是O（n）。

如果使用LinkedList的「專用」版本，它總是保持一個指向列表中最後一個節點的指針，這些都將成爲恆定時間操作。我正確理解LinkedList的標準實現不可用嗎？

Answer 1

您不必在列表末尾插入。如果您插入（單鏈接）列表的前面，它們都是O(1)。

堆棧包含1,2,3：

[1]->[2]->[3] 

按5：

[5]->[1]->[2]->[3] 

流行：

[1]->[2]->[3], returning 5 

Answer 2

對於雙向鏈表的堆棧操作push和pop應都是O（1）。

如果你堅持使用一個單獨的鏈表，假設你可以保持一個指向尾部和頭部的常量開銷，你可以有O（1）排隊和出隊列隊列操作。而且，由於利用分期不變的開銷，您可以在兩個隊列中創建一個堆棧，最終可以實現O（1）推送和彈出。