1,407 views
4 votes
4 votes

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)$

2 Answers

Best answer
10 votes
10 votes
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)

Edited Answer :
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)
selected by
0 votes
0 votes

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).
Hence the answer.


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

Answer:

Related questions

4 votes
4 votes
1 answer
3
Arjun asked Oct 10, 2016
727 views
In a Network where bytes are continuously being transferred, it is required to identify the most frequently transferred byte. What would be an appropriate data structure ...