Is it possible to delete a middle node in the single linked list when the only information available we have is the pointer to the node to be deleted and not the pointer to the previous node?After deletion the previous node should point to the node next to deleted node.
-
-
Yes you can delete from the middle of the list.
The trick is to have a variable in your program that contains the address of the previous node. Usually, just as you advance to the next node you put the address of the current node inside this variable. When you are at the next node, that address will now be the previous node.
You then proceed as though this were a double-linked list. -
You say "the only information available ... is the pointer to the node to be deleted and not the pointer to the previous node". In that case, you can find the pointer to the previous node by traversing the list until you find a node whose next_pointer points to the node to be deleted.
There are cases where you might want to traverse the list even if you are given pointers to both the previous node and the one to be deleted. Deleting a node that isn't in the list could corrupt the list. The criticality of the list and the potential for malicious clients will affect how much extra effort is appropriate to make the list robust.Comment
Comment