CODEWITHSUNDEEP
algorithm
beatrice
beatrice

Reputation: 4401

Why removing a node from a linkedlist comes with O(1)?

I am reading a book and it says that the normal deletion with traversal is O(n). Ok it's easy. But then it says that if you just copy the data from the next node to our node it will make it O(1).

Here on Stackoverflow I read another explanation for that, but I still don't understand it. Don't we still have to locate the nodes?

Here are the nodes, the data stored is in parentheses:

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

How is deleting the node (or moving the data from the next node) with "soldier" done in O(1)? How is it possible to just point on it and say it is the soldier node?

Upvotes: 1

Views: 77

Answers (2)

Ohad Eytan
Ohad Eytan

Reputation: 8464

Usually who talks about linked list deletion on O(1) assume that you got a pointer to node itself and not just the value of it, hence you don't need to traverse the list.

Upvotes: 5

Franko Leon Tokalić
Franko Leon Tokalić

Reputation: 1508

Well I think you are confusing two different things: searching for the node by content and removing the node.

You refer to a node by a pointer (you can call it an iterator, handle, link, ...), and you can remove it by setting its next link and its data to the ones from the next node - done in O(1).

Only if you don't have a pointer to it, you search for it - which is O(n).

Upvotes: 3

Related Questions