Delete node from singly linked list when header is not known

[Raj]

Is there any way to delete a particular node from a singly linked list
where the header of the list is unknown.Only pointer available is the
one which points to the node to be deleted

 

[Tosha]

Is there any way to delete a particular node from a singly linked list
where the header of the list is unknown.Only pointer available is the
one which points to the node to be deleted

type *temp = ptr;
ptr = ptr->next;
free(temp);

 

[Raj]

But I want to retain the list. I would be losing the link with the
previous node if I do wats mentioned

 

[Tosha]

But I want to retain the list. I would be losing the link with the
previous node if I do wats mentioned

No you would not, because the the pointer you have has the adress of the
node you want to delete and value of previous_node->next at the same time
(that's is the same thing), and when you say "ptr = ptr->next" you change
the value of previous_node->next to point to previous_node->next->next or
ptr->next.
I don't know if you have double indirection connection with list or single,
because if you have single, than it's only possible to delete node in front
of pointed node, like "ptr->next = ptr->next->next".

 

[Jaspreet]

Is there any way to delete a particular node from a singly linked list
where the header of the list is unknown.Only pointer available is the
one which points to the node to be deleted

This one's a popular interview question. Just copy the value of the
next node to the current node and delete the next node. So, it would
be something like :

node *tmp = NULL;
tmp = ptr->next;
ptr->value = tmp->value;
ptr->next=tmp->next;
delete tmp;

 

[Howard]

No you would not, because the the pointer you have has the adress of the
node you want to delete and value of previous_node->next at the same time
(that's is the same thing), and when you say "ptr = ptr->next" you change
the value of previous_node->next to point to previous_node->next->next or
ptr->next.

What? When you change the pointer variable ptr, which currently points to
the node to be deleted, in what way does that change the value of the
previous node's "next" member? Just because the current values of those
pointers are the same, does not mean they're the same pointers! After
assigning a new value to ptr, ptr now points to the next node, but the
previous node's next pointer is unchanged! After deleting the current node,
it becomes an invalid pointer.

The correct method is given by Jaspreet (although the first two lines of
that example might as well be combined into one.)

-Howard

I don't know if you have double indirection connection with list or
single, because if you have single, than it's only possible to delete node
in front of pointed node, like "ptr->next = ptr->next->next".

I don't know what "double indirection" means in this context, but the
requirement was for a "singly linked list". To me, "double indirection"
means a pointer-to-a-pointer, as in node**.

-Howard

 

[Tosha]

What? When you change the pointer variable ptr, which currently points to
the node to be deleted, in what way does that change the value of the
previous node's "next" member? Just because the current values of those
pointers are the same, does not mean they're the same pointers! After
assigning a new value to ptr, ptr now points to the next node, but the
previous node's next pointer is unchanged! After deleting the current
node, it becomes an invalid pointer.

I meant if you have adress of previous->next or to say adress of original
ptr value holder.

 

[Howard]

I meant if you have adress of previous->next or to say adress of original
ptr value holder.

The original post said that the ONLY thing we had was a pointer to the node
to be deleted. Nothing in the original post suggested that the address of
the previous node's next pointer was known,or even if there IS a previous
node. (The node to be deleted might be the head of the list, after all.)

The only way your code would affect the previous node's next pointer would
be if you were given the pointer to the current node as a [non-const]
reference to the previous node's next pointer, or if you were operating
directly on that pointer, neither of which is suggested by the original
post.

-Howard

 

[Howard]

This one's a popular interview question. Just copy the value of the
next node to the current node and delete the next node. So, it would
be something like :

node *tmp = NULL;
tmp = ptr->next;
ptr->value = tmp->value;
ptr->next=tmp->next;
delete tmp;

[re-posting, because previous try doesn't seem to have gone through...]

Two things to note in your example:

1) (minor point): Might as well combine the frist two lines. No point in
assigning NULL to the pointer and then assigning a value to it. Just
declare and initialize in one statement.
2) (major point): Before using tmp to assign the next and value members, you
need to test that tmp is not NULL. Dereferencing a NULL pointer constitutes
"undefined behavior". And if the current node is at the end of the list
(assuming it's not circular), then its "next" pointer would be NULL (and so
tmp would also be NULL).

-Howard

 

[Michiel.Salters]

This one's a popular interview question. Just copy the value of the
next node to the current node and delete the next node. So, it would
be something like :

And if there's no next node? How do you delete the last node?

node *tmp = NULL;
tmp = ptr->next;
ptr->value = tmp->value;
ptr->next=tmp->next;
delete tmp;

You're writing to tmp twice. First you set it to 0, then to ptr->next.
The first statement is obviously useless.
Worse, you don't check for ptr->next==0.

HTH,
Michiel Salters

 

[Raj]

Thanks all of u for the replies....
The suggestion is working out....But as Howard said the logic does not
work if the node to be deleted is the last one.
Any solutions??

 

[Ben Pope]

Thanks all of u for the replies....
The suggestion is working out....But as Howard said the logic does not
work if the node to be deleted is the last one.
Any solutions??

Perhaps the tail must be a special case. Some kind of "null" node which
is copyable and always points to null.

Ben Pope

 

[Howard]

Thanks all of u for the replies....
The suggestion is working out....But as Howard said the logic does not
work if the node to be deleted is the last one.
Any solutions??

Nope. If the node to be deleted is the last one, then you're stuck. You
should not delete it, because then you may at some point access it illegally
through the next pointer of the previous node. In this case, I'd report an
error.

Another problem would be if the node were the first node in the list. Then,
deleting it would invalidate the actual pointer to the head of the list.
(Which you say you don't have... but I'm assuming this is just for the sake
of this "puzzle", since any "real" program would certainly have to retain
the pointer to the head of the list!)

There is _no_way_, using a singly-linked list, and not having a pointer to
the head of that list, to "properly" delete the given node from that list.
You _can_ do like the example, making sure to check for NULL, of course, but
you'd need to throw an error in that case. And, you'd need to tell whoever
was supposedly using this method (your teacher? job interviewer?) that if
this _were_ by chance the head node, then any existing pointers to the head
node would no longer be valid.

By the way, when given questions in interviews (if that's the kind of
question this is), it's not always required that you come up with a perfect
solution. Sometimes, what the interviewer wants is to hear your analysis of
the problem. These kind of problems with the proposed solution are exactly
the kind of things you need to be able to consider for yourself when
designing real-world solutions. The more you're able to demonstrate your
analytical abilities, the more likely you'll get the job.

Of course, if this is just a puzzle posited by a friend or something, then
the answer is that it's simply not possible to do correctly in all cases.
Some, but not all.

-Howard

 

[Raj]

Ok..fine
Deleting header wont be a probelm bcos if we knew it was header
the qusetion itself would have been irrelevant

Thanks a lot Howard...