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

if pointer to the node Q is given. then how would we go back, to get the node just before it?

and without it how will we delete this node?

copying the next node is a good method though.

---

https://gateoverflow.in/3654/gate2004-it_13

---

q->d = q->next->d; this operation may itself take more than O(1) time. In the given option O(n) is the worst.
 

---

How come this takes O(n) ?see the pic posted by pranay dutta there ,its O(1) only .

---

how come one assignment more than constant time?

---

Suppose node itself contains an array.

---

why are we considering the possibility of node x being the last node when it's given that it's an intermediate node?

---

A simple solution is to traverse the linked list until you find the node you want to delete. But this solution requires pointer to the head node which contradicts the problem statement. Fast solution is to copy the data from the next node to the node to be deleted and delete the next node. Something like following.

    // Find next node using next pointer
    struct node *temp  = node_ptr->next;

    // Copy data of next node to this node
    node_ptr->data  = temp->data;

    // Unlink next node
    node_ptr->next  = temp->next;

    // Delete next node
    free(temp);

Time complexity of this approach is O(1) Refer this for implementation. Note that this approach doesn't work when node to deleted is last node. Since the question says intermediate node, we can use this approach.

---

O(1) is possible iff the list contain a node who having data x and pointing by the pointer Q. and more over if this is not case then this question  will not give us better scence bcz as usual will take o(n) time to search that element and then perform delete operation that is not so much intresting.

---

fantastic :)

---

One can see this also:https://www.geeksforgeeks.org/gate-gate-it-2004-question-13/

---

deleting node x requires O(n) as worst case. Although we can get similar result in O(1) by coping next to node x's data & deleting the next node. but, question asked about deleting node so, O(n) should be correct.

---

Well it should be O(n), if we just delete element position by pointer the elements ahead will be lost so we need to start from head and traverse one node before X. Once we reach there all we have to do is prex->next = x->next and then delete X.

If it is doubly link list where we have previous and next pointers then it's O(1) as we can link our list by using previous and next pointers but singly link list is just one way

---

@Arjun sir

I am in dilemma that Best answer in the GO pdf is (D) but answer at the last of all the discussions is finally (A).

so, which one is correct?

https://www.geeksforgeeks.org/gate-gate-it-2004-question-13/ this link also says option (D) is correct. 

---

Ans would not be same if the q  is not intermediate node.. If its the last node in worst case so order of n time would be taken.

---

@itssandeepverma "Ans would not be same if the q  is not intermediate node"

I think it must be like "Ans would not be same if the q is intermediate node." Ans is same for q at last and q at start. Isn't it ? 

---

In question it is explicitly  mention that it is intermediate node..  So no need to worry about first and last node . Jst copy the content of the next and delete the next header. Ok

---

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

---

@Kiyoshi, but we need pointer to the previous node also eg: x -> y -> z, if we need to delete y, we need address of X so that it can point to z. In worst case this can be the second last node, so we need to travserse till that node, hence O(n) time.

---

Let's take a linked list like this:

1 -> 2 -> 7 -> 5 -> 3 -> 4

Now, say x points to 5, now 5 next need to be set null. But if 5 next is set to null then connection to 5 is lost.

If next is assigned to x then connection to 5 is lost.

How a single node is able to do this?

@Shaik Masthan sir how to solve this. What I am doing wrong here?

---

Is answer looks fine now ? @Tushar Rana

---

@Shaik Masthan

Hahaha, thanks a lot sir. Understood!

---

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 ?

My Approach: i have one observation in the given question :-
1) it is clearly mentioned it is intermediate node (so no last node scenario )
2) they didn't mention head node of singly linkedlist so  traversing from start to intermediate node is not possible without head node So, O(n) option is wrong  

But there is one more way:-

Algo:
Q→data=Q→next→data; // Copy the value of next node into Q.
del=Q→next; // take another pointer variable pointing to next node of Q.
Q→next=Q→next→next;
free(del);
 

 

So option D : O(1), Is right ( based on data given in question)

 

refer more about this approch :https://www.geeksforgeeks.org/given-only-a-pointer-to-a-node-to-be-deleted-in-a-singly-linked-list-how-do-you-delete-it/

---

but address remains same so not possible in O(1)
delete means u have to permanently delete -> free that node !!
u are thinking like u have been given to print some pattern then instead of writing nested for loops to print it , u are just printing that pattern using printf , similar case here too

---

it is not given what type of data is stored in linked list node so we cannot use the copy trick to delete node here, since the node can point to array of integers itself or some other datastructure, we need to traverse from head to get to the previous node pointed by Q to delete the node x.

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

Procedure for deleting node that contains $x$ (pointed by $Q$):

1. Identify the node whose next is pointing to $x$, note it as $' \text{prev}_x' \Rightarrow \text{This takes O(n)}$
2. Identify the node which is pointed by $Q.next$, note it as $' \text{next}_x' \Rightarrow \text{This takes O(1)}$
3. $\text{prev}_x -> next = \text{next}_x$
4. free(Q)

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

In the question it is clearly given that, the node we want to delete is an intermediate node which means it is not the last node)

---

I think the question simply means to delete the an intermediate node, which means if the initial list is 2->4>1>10 and if we are deleting  the node which has the value 1, then the final list should be 2->4->10.

---

Think about it this way, we have a singly linked list, and direct access to the node we want to delete, we can update the nodes next pointer to null sure, but we would also need to change the next pointer previous to the node X to the next node of X, so either way we will have to travel to X from the head.

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

This algo will not able to delete the last node as there’s no next node to copy data from.

That's why we can't use this algo in this question

For more detail you can see this solution - https://gateoverflow.in/399309/gate-cse-2023-question-3?show=487560#c487560

---

@Pradeep Pandey_1 It is mentioned that the node is neither last nor first. It is intermediate.

---

If it is given that Linked List node contains only Integer data then option D is correct.

Answer 3

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

Comments

just think for worst case if he will give the pointer to the last node the how will u done this task in o(1) time.

 

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.

Answer 5

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. 

Comments

Exactly!!

---

see,how we differentiate two nodes their data part may be diff or same but their add part are different, if the x node data and address part is changed then the x node is not present physically in the memory its deleted

---

this is the PERFECT explaination

people don't even know the correct answer but have the audacity to flag the answers as wrong ones, this is NOT WRONG answer, it is CORRECT

we have to delete the node x which will take O(n) time but if you are just copying the next node data to current and deleting next then its just a mimicry of deletion, this is not how real node deletion works, deleting node is different than deleting data

Answer 6

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!