Link list

Question

Suppose we are deleting a node with data field as x. Which can be present anywhere in the list.

Consider following Scenarios :

S1 : You're only provided with pointer to the node which needs to be deleted.

S2 : You're only provided with the pointer to the starting node.

Which of following is correct ?

A. In both scenarios deletion is possible for all inputs, and deletion will be more efficient in S1  then in S2.

B. In both scenarios deletion is possible for all inputs, and deletion will be more efficient in S2  then in S1.

C. Deletion is not possible for certain cases in S1, but deletion is possible in all cases for S2.

D. Deletion is not possible for certain cases in S2, but deletion is possible in all cases for S1.

Ans. C

Comments

Why not B, because even though we are given the pointer to node we could write such code like:

temp = Head

while(temp->next == Given Pointer)

       temp = temp->next;

//Now at this pointer i am one node back to the node which need to be deleted.

struct node* P = temp->next;

temp->next = (temp->next)->next;

free(P)

Whats wrong with this code.

And obviously S2 will be better then S1

---

You're only provided with pointer to the node which needs to be deleted.

Your code assumes that HEAD is also given.

 

---

S1 can still be implemented like :

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

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

Ref: https://gateoverflow.in/3654/gate2004-it-13

But this would cause problem when we have to delete the last node. This is because we are copying the data of next node onto the current node(to which pointer is given). For last node there is no next node.

---

then in worst case wont the answer be O(n) ?

---

S1 : You're only provided with pointer to the node which needs to be deleted.

This could be the pointer to the last node.

---

Na462 Can you explain the method you are thinking..?

---

@Mini Panda, brother then how would i know that whether the answer is O(1) or O(n) as i may or maynot consider the last node to my consideration for deletion. Still the answer should be O(n) in worst case right ?

---

Suppose brother the only line weren't present in question then what wil be time complexity ? O(n) i suppose in worst case

---

If pointer to the last node is only given then you cannot delete the node without having the knowledge of HEAD value. No algo can do that. And you have to consider all the cases because it says

Deletion is not possible for certain cases in S1

If "only" weren't given then S1 would lose it's actual intention. It would become same as S2. I hope the question maker won't leave students with such word trick :P

---

I understood sorry i was earlier thinking without that only line :p. I totally agree.

Answer 1

We can only delete the next node in link list. There will be case when you are given a pointer to the node and asked to delete that then this can be possible provided that the node is not the last node.

How can we delete if You're only provided with pointer to the node which needs to be deleted?

We can copy the next node data into the current node and we can delete the next node.

Coming to options:

 

A. In both scenarios deletion is possible for all inputs

No, in S1 if pointer is given to last node then we can't delete that.

Same reason for option B

Option D is false because given pointer to first node we can delete any node of given link list.

Clearly we can see option C is Correct