使用链接列表实现的堆栈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）推送和弹出。