retagged by
2,844 views
1 votes
1 votes

Consider a singly linked list. What is the worst case time complexity of the best-known algorithm to delete the node $a$, pointer to this node is $q$, from the list?

  1. $O(n \lg \: n)$
  2. $O(n)$
  3. $O(\lg \: n)$
  4. $O(1)$
retagged by

2 Answers

2 votes
2 votes

Let X is representing Which has to be delete Node

in a single linked list, We have only next pointer but not a previous pointer.

But we have find the previous node to X ==> which takes O(n) in worst case, After finding it,

Prev -> next = q-> next ;

free(q) ;

which takes O(1) time only.

TC = O(n) + O(1) = O(n).

Note that, Algorithm should work in all cases

1 votes
1 votes

O(n).

If it is the Last node of the linked list it will take  O(n) time. Despite node pointer is given but we don't know the address of the previous node. From head, we need to traverse the linked list to get the add of the previous node.

If we have address of prevoius node then only we can store the address of the next node that has to be deleted.

 

Previous -> next = Current -> next;

edited by
Answer:

Related questions

0 votes
0 votes
1 answer
1
Arjun asked Jan 2, 2019
1,741 views
Match $\text{List I}$ with $\text{List II}$ and choose the correct answer from the code given below.$\begin{array} {clcl} & \textbf{List I} & & \textbf{List II} \\ & \...
0 votes
0 votes
1 answer
3
Arjun asked Jan 2, 2019
17,067 views
Consider the following postfix expression with single digit operands :$6 \; 2 \: 3 \: ^* \: / \: 4 \: 2 \: ^* \; + \: 6 \: 8 \: ^* \: -$The top two elements of the stack...
0 votes
0 votes
2 answers
4
Arjun asked Jan 2, 2019
5,795 views
A binary search tree is constructed by inserting the following numbers in order :$60, 25, 72, 15, 30, 68, 101, 13, 18, 47, 70, 34$The number of nodes in the left subtree ...