Programming

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.

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:

Code:

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.

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 ?