为什么从链表中删除节点附带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) 假设你有一个指向节点本身的指针,而不仅仅是它的值,因此你不需要遍历列表.