pointers - 使用链表实现的 Stack 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]  // inserted 5 at the front/top

流行:

[1]->[2]->[3]  // removed 5 from the front/top