链表栈结构大O
LinkedList Stack Structure Big O
以下问题的答案是弹出 O(n) 和推送 O(1)。但我不太明白为什么 pop 不能是 O(1)。我们确实有指向链表末尾的尾指针，我们应该在 O(1) 时间内访问它，对吗？我错过了什么吗？
如果栈底必须在链接内存结构的头部？其中 n 是结构中的节点数。
想想你的堆栈的不变量：tail 指向最后一个元素。
pop操作删除了最后一个元素——这意味着我们需要重新调整tail。我们如何做到这一点？使用双向链表，我们可以只跟随指针返回到前一个节点 - 但是正如您的插图清楚地显示的那样，在单链表中没有这样的箭头返回到前一个节点。
所以我们需要从 head（我们持有指针的唯一其他节点）开始，一直迭代直到我们到达倒数第二个节点，然后设置tail 指向那个节点。
以下问题的答案是弹出 O(n) 和推送 O(1)。但我不太明白为什么 pop 不能是 O(1)。我们确实有指向链表末尾的尾指针，我们应该在 O(1) 时间内访问它，对吗？我错过了什么吗？
如果栈底必须在链接内存结构的头部？其中 n 是结构中的节点数。
想想你的堆栈的不变量：tail 指向最后一个元素。
pop操作删除了最后一个元素——这意味着我们需要重新调整tail。我们如何做到这一点？使用双向链表，我们可以只跟随指针返回到前一个节点 - 但是正如您的插图清楚地显示的那样，在单链表中没有这样的箭头返回到前一个节点。
所以我们需要从 head（我们持有指针的唯一其他节点）开始，一直迭代直到我们到达倒数第二个节点，然后设置tail 指向那个节点。