GATE IT 2004 | Question: 13

Question

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 ?

• A. $O(n)$
• B. $O(\log^2 n)$
• C. $O(\log n)$
• D. $O(1)$

Comments

Question : “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 ?”

Any node in the linked list have two things first is value and second is address. Question specifically mentions about Q be a pointer that means it contain address. So, node x must represent a node with value x and finally  O(1) is the answer for sure.

 

 

---

i think the answer should be option C. the question says Q pointer points to intermediate node which means middle node right? so to delete that node we will have to traverse till one node before Q so Q → next can be stored in the next of previous node of Q. So shouldn’t it be O(logn)? Please help @Arjun

---

@Shatakshi_1 first thing  here intermediate node doesn’t necessarily means only middle node . It can be anything except the first and last node ig . and second thing to Find the middle node of the Linked list still takes $O(n/2)$ time where we use slow Fast Pointer in which we increase fast pointer by $2$ and slow pointer by one node then fast pointer points to the last node or null (depends on the number of nodes in the linked list ) slow points to the middle of the list so using iterative method still it will take $O(n/2)$ time i hope it will clear ur doubt :)

Answer 1

In the worst case $x$ could be last or second last node, In that case full traversal of the list is required. Therefore answer is (A).

PS: We can simulate the deletion by moving the $x's$ next node data to $x$ and then delete $x's$ next node. But this is technically not the same as DELETING NODE $x$ as mentioned in the question though effect is the same as long as there are a constant number of elements to be moved from $x's$ next node.

Comments

@Arjun sir,

As the question is ambiguous and the answer could be A or D depending on the interpenetration. But gate overflow site gives the answer as A, due to this some other government exams which are taking questions from gate and thinking that gate overflow key is perfect, :-) they are accepting answer as A only. Kindly update the answer as A or D (or question is ambiguous )

---

I don't think there's an ambiguity here though people can misinterpret the question. If you can get confirmation from any IIT/IISc professor I can change :)

---

@Sunnidhya Roy We can simply do struct node *temp= Q->next and then after copying the value from node pointed by temp(i.e Q->data=temp->data) we can do Q->next=temp->next and then free(temp) ,so we don’t need to traverse the complete LL to delete the node next to node pointed by Q, we just need to create a new pointer temp. 

But since the question is asking that we need to delete the node x itself completely from the list(not just removing its value but complete node i.e data,next pointer both ),to do so we need address of the node before node pointed by Q ,which will require O(n) time in worst case .

Answer 2

Since $Q$ is pointing to node $X$, it can de done in $O(1)$ time..

Algo:

$Q \rightarrow data = Q \rightarrow next \rightarrow data$; // Copy the value of next node into $Q$.

$del = Q \rightarrow  next$; // take another pointer variable pointing to next node of $Q$.

$Q \rightarrow next = Q \rightarrow next \rightarrow next$;

$free (del)$;

Correct Answer: $D$

Comments

what if it is especially mentioned that linked list contains integers or characters?

---

correct option is O(1) so the option is D not A.check if i am wrong

---

Deleting a node doesn’t mean that deleting data only. The address pointed by the pointer must have to free also.

Answer 3

Its O(1) only. Just copy next element's data to x ,and delete next.

Answer 4

Let us say assume ,question it means node with data X: Now we first need to search node with data X in O(n) and then delete.

Let us assume that by X ,it means Node with address X,but the 0(1) method does not delete node with address X.It just modifies node with address X and delete some of its neighbor.

I will go with $ O(n) $ with the above reasoning.