爲什麼從鏈表中刪除一個節點帶有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)上談論鏈接列表刪除的人通常假設你有一個指向節點本身的指針，而不僅僅是它的值，因此你不需要遍歷列表。

Answer 2

嗯，我認爲你混淆了兩個不同的東西：按內容搜索節點並刪除節點。

您可以通過指針指向節點（您可以將它稱爲迭代器，句柄，鏈接...），並且可以通過將它的next鏈接及其數據設置爲來自下一個節點的鏈接來刪除它 - 在O（1）中完成。

只有當您沒有指向它的指針時，纔會搜索它 - 這是O（n）。