Thread: quick question on deleting a node from a linked list

I just started learning linked list and nodes and I'm stil getting use to the syntax.

http://i1330.photobucket.com/albums/...ps61afd59b.jpg

I made this to help me visualize my list.

do I set the code to skip to get to the next node

like this

Code:

p=p->next=p->next

And I'm guessing that the node I have to delete has to be deallocated because it still exist somewhere in memory.

So does that mean I will have to traverse through the list first and make p point to the one I want to delete and make another pointer let's say node * d and then have d point to where p is pointing.

Then traverse again and when p gets to the node before the one I want to delete and have p->next point to the node after the one I want to delete and then delete d.

Code:

delete d;

Originally Posted by c++noob145

And I'm guessing that the node I have to delete has to be deallocated because it still exist somewhere in memory.

Yes, though I would rather say "destroyed" rather than "deallocated" since "deallocated" generally refers to memory, whereas there may (or may not) be other things that should (also) happen when you remove the node.

Originally Posted by c++noob145

So does that mean I will have to traverse through the list first and make p point to the one I want to delete and make another pointer let's say node * d and then have d point to where p is pointing.

Then traverse again and when p gets to the node before the one I want to delete and have p->next point to the node after the one I want to delete and then delete d.

No, you only need to traverse once: find the node before the one that you want to delete. From there, you only need to make its next pointer point to the node after the one you want to delete, then you destroy the node that you want to delete.

Note that this contains redundancy:

Code:

p=p->next=p->next

It could be simplified to:

Code:

p = p->next;

If you've found the node to destroy, and the node before it, why would you need to traverse it twice? No human would need so, so why would a computer?