LinkedList堆栈结构大O

Question

以下问题的答案是：对于弹出，为O（n）；对于推送，为O（1）。但是我不太明白为什么pop不能是O（1）。我们确实有指向链表末尾的尾指针，我们应该在O（1）时间访问它吗？我在这里想念什么吗？

如果堆栈的底部必须位于链接的内存结构的开头，push和pop操作的运行时间是多少？其中n是结构中节点的数量。

Answer 1

考虑堆栈的不变量：tail指向最后一个元素。

pop操作将删除最后一个元素-这意味着我们需要重新调整tail。我们如何做到这一点？使用双向链接列表，我们可以将指针跟随返回上一个节点-但正如您的插图清楚显示的那样，在单链接列表中没有这样的箭头可以返回到上一个节点。

因此，我们需要从head（持有指针的唯一其他节点）开始，并一直进行迭代，直到到达倒数第二个节点，然后将tail设置为指向到该节点。