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

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