Given an in-between(any node not at the start and end of the linked list) node within a singly linear linked list, how to delete that node, when head pointer of list is not given?
If the list is doubly-linked, you can seek backwards to find it if necessary. If not, it may not always be possible to find the node you want.
1 Like
thanks coronaa for the reply.
actually this was an interview question
In theory, if you have a pointer to node N, you can save the pointer to the next node (node N+1), then just copy the contents of node N+1 into the memory space occupied by node N. Then free the original node N+1. Like this, for a simple C structure:
void deleteNode( struct data *node )
{
struct data *next = node->next;
*node = *next;
free( next );
return;
}
That ignores any complications that could be caused by copying data, references to node N+1 from outside the list, and any side effects of freeing the original node N+1.
So, in practice, in all but trivial cases you'd never do that.
Ah, vague and impractical. A perfect interview question. :rolleyes:
1 Like
If you are in the Nth node and you want to delete it, just copy the (N+1)th node contents to N, link N to node N+2 and delete N+1.
I'm thinking about what if when node numbered (N + 1) == NULL
??
i.e. when the current node itself is the last node of the chain and the list is a singly linked; does the same algorithm hold true ?
Its going to produce dangling pointers at (N - 1) th location, isn't it ?
Of course; that's the impractical bit of the question. The vague part is that they don't tell us whether it's doubly linked. Even in a doubly-linked list you'll hit a similar problem when n's the only node in the list though.
True.
Its failling with even doubly linked when N == 1, making the list-pointer itself a dangling one.
Always check whether N+1 node is Null before doing any logic.
Even though you know that N+1 == NULL; what you can do in the same algorithm to protect node pointer at (N - 1) from becoming a dangling pointer ?
Apart how would your function written besed on that algorithm would ever know that N == 1; and how you would protect the list-pointer pointing to the first node from becoming dangling?
A similar algorithm holds trure in binary tree node deletion; wherein the data is copied from the leaf node which is located on the branch one move either left or right of the node to be deleted logically and the actual deletion happens at the leaf node whose data is copied. This alters the data organisation but preserves the properties of the tree.
But moreover this worked there because of the deletion always happen at the leaf node and is travelled (this travel is missing in your algorithm) to be found via the entire branch and while the travel you pass through the second last node whose pointer you get and this node doesn't become a dangling one.
The TRAVEL is important.
But the question was how to delete the node you are currently in.
So there is no point in thinking of other consequences, because you cant do anything to node N-1 when you are in Nth node.
This interview question just tests your logical thinking not the algorithm efficiency.
There's plenty of reason to think about consequences, but we've already been over most of those.
If consequences are not to be thought, a deletion of a node is as simple as free(node_ptr).