algorithm - 为什么从链表中删除节点的复杂度为 O(1)？

Question

我在看一本书，上面说带遍历的正常删除是O(n)。好的，这很容易。但随后它说，如果您只是将数据从下一个节点复制到我们的节点，它将使其成为 O(1)。

我在 Stackoverflow 上阅读了另一个解释，但我仍然不明白。难道我们还需要定位节点吗？

这里是节点，存储的数据在括号中:

N("cop")->N("cat")->N("dog")->N("snake")->N("soldier")->N("camel")->N("ghost")->N("rock")

如何在 O(1) 中完成带有“士兵”的删除节点(或从下一个节点移动数据)？怎么可能指着它就说它是士兵节点呢？

Answer 1

通常谁在O(1) 上讨论链表删除，假设您得到了一个指向节点本身的指针，而不仅仅是它的值，因此您不需要遍历列表。