Deleting Pointed node in Singly Linked List

[vissure]

How to delete a node in a Singly Linked List using a pointer that points to the node? (Assume that you cannot traverse the list to find the previous node)

--
With Regards
Vishnu

[Narue]

This is a common test question. Have you tried to solve it yourself? Here's a hint: you can move data as well as change links.

[vissure]

Ya, I know u can shift up the links following the one pointed to. Or u can swap with the last node and delete the last node(If sorted order is not a criteria). But this is an optimisation problem. Consider this as an infinitely long link list. Both the above methods are not practical in such a scenario as both are computational intensive.
Is there any other way??

[Rashakil Fol]

You only need to copy one data element and change one link.

[Drowzee]

[Edit: Post removed due to misinterpretation of the question. Assumed pre-check was possible]

[Narue]

>Ya, I know u can shift up the links following the one pointed to.
Shift? It sounds like you're confused, but we'll proceed.

>Or u can swap with the last node and delete the last node(If
>sorted order is not a criteria).
Sorted order is irrelevant since you're unlinking the node causing disorder anyway. And you don't need to swap unless you're returning the deleted node and need the data in the calling function.

>Both the above methods are not practical in such a scenario
>as both are computational intensive.
Constant time performance with two operations is computationally intensive? The only way to improve that performance is to drop down to inline assembly and optimize the data movement with low level register tricks. Even then you won't see much of an improvement.

You say you understand the solution I was suggesting, but you obviously don't if you think it's "computationally intensive".

[SpS]

Narue...your replyies seems to me like you are a very aggressive person.

[Clinton Portis]

i like agressive

RrrRRraawwrrrrr.....

[jwenting]

Narue is not so much agressive as frustrated with the lack of effort by many (especially younger) people in this world to even attempt to solve their own problems, an attitude I can very much relate to.

But then we're both professionally employed in this profession and have to work with the end result of an educational cycle in which such lack of effort gets people degrees and diplomas which in turn get them hired to be our colleagues, saddling us with the burden of doing their work to get projects completed.

Narue is not so much agressive as frustrated with the lack of effort by many (especially younger) people in this world to even attempt to solve their own problems, an attitude I can very much relate to.

But then we're both professionally employed in this profession and have to work with the end result of an educational cycle in which such lack of effort gets people degrees and diplomas which in turn get them hired to be our colleagues, saddling us with the burden of doing their work to get projects completed.

In my school, we have an IT technician, we call him Mr. Grumpy because everytime we ask him to fix this or do that he is always grumpy, probably due to the reasons outlined above.

Whilst it is entirely possible that these people can lead socially rewarding lives outside of work I find it difficult to imagine. A happy IT associated person, - are you kidding me? The constraints of life make this unlikely. :lol:

[venugopal.somu]

The better method as per me is,
consider a linked list as bellow:

head-> a|100 -> b|110 -> c|120 -> d|130 -> e|140 -> f|150

If my Known node is c having address 110(as per the list above).
now we need to delete a node having content c(deleting a node in the sense deleting the data in the list).

step1: copy next node data into current node (i.e replace 'd' with 'c')
step2: now delete the next node (Replace current node next address with next node next address) (think and do u can easily understand)

step3: now free the deleted node (if u want)

Its one of my thought. if u have more idea plz post here

[Narue]

>The better method as per me is
You do realize that the same solution was suggested in this thread three years ago, yes? :icon_rolleyes:

[stevenprabu]

if it is last node, how you will do. If you simply delete, then the previous node link will not have NULL. bad idea.

[Narue]

>If you simply delete, then the previous node link will not have NULL. bad idea.
This statement suggests that you don't understand how nodes are deleted in a singly linked list. To unlink a node, you link the previous node with the next node before releasing memory:

Original:
A->B->~

Unlink B:
  +-->-+
  |    |
A-+ B->+->~

Delete B:
  +-->-+
  |    |
A-+    +->~

Done:
A->~

[Sandeep Shetty]

if(!node)
;
if(node->next)
{
temp=node->next;
memcpy(node, temp, sizeof(node));
node->next = temp->next;
free(temp);
printf("\ndone...but all the pointers pointers pointing to the nodes might be invalid now...well...some of them");
}
else
printf("\n :D :D dam...we have a problem ...if Windows ... show the dreaded blue screen ... Linux users can just reboot :D :D!\n");