edited by
24,570 views
65 votes
65 votes

Let $P$ be a singly linked list. Let $Q$ be the pointer to an intermediate node $x$ in the list. What is the worst-case time complexity of the best-known algorithm to delete the node $x$ from the list ?

  1. $O(n)$
  2. $O(\log^2 n)$
  3. $O(\log n)$
  4. $O(1)$
edited by

9 Answers

6 votes
6 votes

Answer is A , O(n) for sure. 
I feel the person who has given answer as O(1) has thought too much and have changed the meaning of the question, the question asks for deleting the Node X ,  which is pointed by the pointer , they never asked anything about the data , the O(1) algorithm is manipulating the data but that node still anyway exist.  
if the question was about deleting the data/element then of course it would be O(1) but here the question is different. 

5 votes
5 votes
The answer is O(1).

Although worst case time complexity is asked but we have been given that Q is an internal node so it cannot be the first or last node and thus we can simply copy data.

struct node* t=q;

q->data=q->next->data;

q->next=q->next->next;

free(t);

these operations could be done in O(1) time.

Please let me know in the comments if there is something wrong with my answer.

Thanks forasking this question!
3 votes
3 votes

Deleting the tail element(Worst Case) would, however, be a O(n) operation because even though you might have a tail pointer, you would still need the penultimate node that would be setup as the new tail node ( by updating the tail pointer and setting the node’s next member to NULL). For this, you need to traverse through the whole linked list.

2 votes
2 votes
This could be done in O(1) if the question would have demanded deletions X's data.

We have been asked to delete the node X itself.

Now, X can be the first, intermediate or last node of SLL.

For SLL, when we are deleting a node, we need to change the reference of the node that was pointing to X, i.e. the node previous to X (say W). We do not have any reference to W. Finding previous node to X would need a list traversal, which takes the worst case time of n.
W found, we can do deletion of X in O(1) now.

Net T(deletion of X) = T(finding_W + removing X) = O(n+1) = O(n).

Answer : A

 

 

Note : The pointer Q to X is nothing but giving us the address of the node to be deleted.
Answer:

Related questions

51 votes
51 votes
4 answers
1
24 votes
24 votes
1 answer
2
23 votes
23 votes
4 answers
3
Ishrat Jahan asked Nov 2, 2014
4,868 views
Which one of the following binary trees has its inorder and preorder traversals as $BCAD$ and $ABCD$, respectively?
62 votes
62 votes
4 answers
4