709 views

For a singly linked list where each node has a pointer to a data array as well as a next pointer, what would be the worst case time complexity to delete an intermediate node $x$ (given a pointer to it)?

1. $O(n)$
2. $O(1)$
3. $\Omega(n)$
4. $O(\log n)$

At first, O(n) came to mind but if we observe carefully it is O(1). HOW ?

REASON 1:

…...[y] → [x] → [z]…….

Now we just want to remove x right !!

for that we do this :

x → data = x → next → data: O(1)

x → next = x → next → next: O(1)

free(z): O(1).

BUT IF YOU WANT TO REMOVE XTH NODE, THEN IT WILL TAKE O(n).

So, I think the question is a little bit ambiguous in language.

For a signly linked list where each node has a pointer to a data array as well as a next pointer, what would be the worst case time complexity to delete an intermediate node x?

"Worst case time complexity to delete an intermediate node x ?"
Does this means ANY intermediate node ?
if NO,

Then we have to search for that particular node x and then delete.
Searching in linked list takes O(n) time and deletion takes constant.
Total Time = O(n) + O(1) = O(n)

For a signly linked list where each node has a pointer to a data array as well as a next pointer, what would be the worst case time complexity to delete an intermediate node x (given a pointer to it)?

Let node x has to be deleted. Pointer is also given so O(1)for searching.
Now apply this algo :

x.data = x-->Next.data
t = x-->Next
x--->Next = x--->Next ---> Next
Free(t)

@sushmita, It is O(1). We are given a pointer to the intermediate node. To delete that node we will copy the data of the next node to that node and delete the next node.

@Arjun sir,

The time complexity for removal is only O(1) for a doubly-linked list if you already have a reference to the node you want to remove. Removal for a singly-linked list is only O(1) if you already have references to the node you want to remove and the one before.

Answer ti both this question and this https://gateoverflow.in/3654/gate2004-it_13

should be O(1) ??

This is a bit tricky.

Deleting an intermediate node in a linked list involves finding it, then deleting it. So, O(n) + O(1) = O(n).

Deleting an intermediate node in a linked list for which we have a pointer to:-

1. Use the pointer and reach that node.
2. Copy the data from the next node to this node.
3. Delete next node.

This is O(1).

Here, we're given:-

where each node has a pointer to a data array

If we had the whole array itself in each node, then to copy the data from next node, we'd have to copy the whole array, which is O(n)

Lose more brain cells here: https://gateoverflow.in/3654/gate2004-it-13