195 views

You're entrusted with the task of deleting a node in a singly linkedlist, whose data field is 'x'. Note that, the node which is to be deleted can be at any arbitrary position in the linked list. Consider the following scenarios.

S1.  You're only provided with a pointer to the node which is to be deleted in the linked list.

S2. You're only provided with a pointer to the starling node of the linked list.

Which of the following options is correct?

How deletion possible with S2?

in DS
edited | 195 views
0
Both statement is true.
0
S1 is false because in order to delete a node, we need a pointer pointing to its previous node.Since we just have the pointer to the node to be deleted, deletion is not possible only with this pointer.

S2 is true since we have the pointer of the starting node, we can traverse forward upto the node whose next node is containing element x.This way we can get a pointer pointing to the previous node of the node to be deleted and hence deletion is possible.
0
I'm not able to understand the question itself but if we are provided with the pointer which is pointing to the node itself then after deleting that node we will lose the prior elements on the linked list because we don't know which element was pointing to the element that is deleted.

Am i thinking the right way?
+1
I think you missed a part ie a node will need a previous pointer in order to delete x.
0

but check the explanation given

0
We need a pointer to the previous node of x whether x is in the middle or at the end or else x has to be the first element(if x is  fisrt element then deletion possible).Isnt that the same thing as the explanation? Or have I missed something?
0

@Bhagyashree Mukherje

So, with only one pointer pointing to the starting node we can delete any node then why there is a need to traverse till its previous node ?

0
No we can't do it with a single pointer.we will need auxiliary pointers.but in the 2nd case we cannot reach the previous node as we don't know the starting node.This is what I interpreted from the question.Correct me if I am wrong
+1

Yes the given answer is correct for statement I missed case when a pointer is pointing to last element.

@Bhagyashree Mukherje The explanation provided by you differed for the case S1 as What they are doing is copying the data of next element to the node which the pointer is pointing to currently and deleting the next node.But when the pointer points to last node then we don't have any next element whose value we can copy and delete that node.

@Ashish Roy 1 When you have the head pointer then you can traverse till the previous of node whose value is x by checking  while(node->next->value!=x) node=node->next and then can delete the node with x as data part.

0

Yes you are right.got it.Thanks @Soumya Tiwari