CODEWITHSUNDEEP
data-structureslinked-list
Garrick
Garrick

Reputation: 689

Is deleting an intermediate node in single linked list done in O(1)?

Suppose, we need to delete an intermediate node in LL and pointer to that node is given, which is to be deleted.

But, i can delete that node in O(1) as pointer is given to that node, but in order to make entry of node before deleted node to the node which is after the deleted node, i need to traverse upto that element which is O(N).

So, How can this complexity be made O(1) overall. Can this be done always or only in some conditions ?

Upvotes: 0

Views: 105

Answers (3)

Nikhil
Nikhil

Reputation: 1039

Well, I remember one "solution" where you don't actually delete that particular node (Let's call It "B Node") to which you have pointer, but what you do is copy the data of "next" node (lets Call it "C Node") into the "B Node" and then delete the "C" node in this way you have O(1) Complexity.

A->B->C

  copy data from C to B . Delete C.

Upvotes: 0

0xffcourse
0xffcourse

Reputation: 379

Lets say we have this linked list:

A->B->C->D->E

As we know A has the pointer to B and B has that to C and so on. Lets say, you know the pointer to C and intend to delete it. The new list should be:

A->B->D->E

Here, B and D are to be linked. Obviously You can obtain address of D from C's next pointer. Yes we have the address of C , but that does not mean that you necessarily know the pointer of B. So, you need to traverse from the head upto the node (B) which will have the pointer to C. This accounts for the O(n) complexity as it is dependent on the number of nodes 'n' in the linked list. Once you have spotted B, you can assign D's address to its next pointer. And thus, C is deleted from the linked list.

The complexity can be made O(1) if you know the address of the node prior to the node that is to be deleted (In above case node B).

Upvotes: 0

infiniteRefactor
infiniteRefactor

Reputation: 2120

When using a linked list, if this scenario is often encountered then a different deletion algorithm is used. Instead of adjusting pointers for deletion, you can insert a flag to the link list element and mark them deleted. Then you ignore the records with deleted flag. Such a deletion is O(1).

Other kinds of implementations might also provide better deletion costs. But your analysis on the general case is correct. If you have only a single link for each node and there is no other improvement, then deletion is O(n).

Upvotes: 2

Related Questions