Sign in to follow this  

Linked list destructor

This topic is 4526 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey guys, creating myself a linked list here, and hoping to be able to make it generic and enable it to be used anywhere :) ANYWAY, i'm just looking at the list destructor. If the list contains nodes, with pointers to other nodes etc, do i need to delete all of the nodes separately to deallocate all of the memory correctly, or can i simply delete the list and the nodes should all go with it?

Share this post


Link to post
Share on other sites
Are you working in C++? If so, you need a delete for every new. If you're working in Java, it'll be GCed automatically when all the references to it are gone. If you're working in C -- again, a free() for every malloc().

P.S. -- I highly recommend creating your own linked list and using it somewhere, at least once. But once you have done that, move over to a standard list implementation; they're usually much more robust.

Share this post


Link to post
Share on other sites
I'm using C++. Alright, now to go make an algorithm to delete all nodes :P

Yeah i saw a linked list in a couple of books i've read/flicked through, so i thought it'd be a good challenge to create my own, and it has been very educational, especially in using pointers, 'new's and 'delete's

Anyway, cheers mate

Share this post


Link to post
Share on other sites
Quote:
Original post by Welshy
I'm using C++. Alright, now to go make an algorithm to delete all nodes :P

Yeah i saw a linked list in a couple of books i've read/flicked through, so i thought it'd be a good challenge to create my own, and it has been very educational, especially in using pointers, 'new's and 'delete's

Anyway, cheers mate


Awesome. That's how I all of a sudden came to understand memory managament in C++ -- creating a linked list. I like you, so I'd give you the delete algorithm, but you'll learn more implementing it yourself.

Ciao,
Twilight Dragon

Share this post


Link to post
Share on other sites
Quote:
Original post by TDragon
Quote:
Original post by Welshy
I'm using C++. Alright, now to go make an algorithm to delete all nodes :P

Yeah i saw a linked list in a couple of books i've read/flicked through, so i thought it'd be a good challenge to create my own, and it has been very educational, especially in using pointers, 'new's and 'delete's

Anyway, cheers mate


Awesome. That's how I all of a sudden came to understand memory managament in C++ -- creating a linked list. I like you, so I'd give you the delete algorithm, but you'll learn more implementing it yourself.

Ciao,
Twilight Dragon

lol, thanks. Well i'll be at it all evening (i hope it doesnt take that long, though it probably will), i'll post it up once i've got it working and you can criticise it :P

Share this post


Link to post
Share on other sites
CList::~CList() // destructor
{
CNode *pPointer;

pPointer = pRoot; // sets the pointer to start at the beginning of the list

do
{
CNode *pPointerDel; // the delete pointer

pPointerDel = pPointer;
delete pPointerDel;

if(pPointer->pNext != 0)
{
pPointer = pPointer->pNext; // sets pointer to the next node in the list
}
} while(pPointer != pHead);

}

Here's what i've got, and it should work (i think).

But it doesnt run, so for pPointerDel to delete the node it's pointing to do i need to overload the assignment operator or something? i remember reading about it. Im thinking this could be the problem because when i set a breakpoint at the node destructor (which doesnt contain any code, yet) and it cannot resolve the values of the member variables, which im guessing means that the pointer doesnt contain all of the node information?

Share this post


Link to post
Share on other sites
It's not so much where you are that you'll want to keep track of - once you've deleted the current node, you couldn't care less about that. What you really want to know is where you need to be next...


Also, you'll need to make sure that your destructor works correctly when the list is empty. Edge cases like that can get tricky.

Share this post


Link to post
Share on other sites
Another hint: pNext is being lost when you call delete on the node. So instead of saving the same address (in pPointerDel)...

Also note that if, for some reason, pNext is already 0, you will end up trying to delete the same memory twice, and it will throw an error. This wouldn't normally happen, but you should redesign it nonetheless.

Lastly, the node pHead is never deleted using that method.

Other than that, it's looks about the way it should. :)

P.S. - Don't do recursive deletes. That just tosses a bunch of things on the stack that don't need to be. Rule 1 in Data Structures class: don't use recursion when iteration is easier. (Because iteration is nearly always faster, and nearly always uses less memory.)

Edit: Beaten to it...haha

Share this post


Link to post
Share on other sites
Ah thanks for the hints guys ;) I rather you did this than give me code examples, at least then i can try and work it out for myself. ANYWAY i've got to go out now im afraid, damn girlfriends, hehe.

Expect to see this thread back up the top tomorrow night as i struggle with it yet again, cheers for all your help though guys

Share this post


Link to post
Share on other sites
Thought i'd carry on posting in this thread, so people know where i am, hehe.

I was just wondering is it easier to delete from the root to the head, or the head to the root? If it's the later, wouldnt i need a pPrevious data member?

Share this post


Link to post
Share on other sites
If your design is right, either way should be equally easy. And if it's a singly-linked list, you only have one option, as you said. Doubly-linked lists are more popular, mainly because deleting a single node is quite easy: pPrevious->pNext = pNext, pNext->pPrevious = pPrevious. (Not accounting for edge cases, obviously.)

Share this post


Link to post
Share on other sites
deciding on keeping it a single list for the time being, a double list could be my next project :)

Anyway, an update on where i am, and i think it works now, but not sure about the pPointer->pNext as indicated:
CList::~CList() // destructor
{
do
{
CNode *pPointer;

pPointer = pRoot; // sets the pointer to start at the beginning of the list

if(pRoot->pNext == 0) // if there are no elements in the list
{
delete pRoot->pNext;
delete pRoot;
delete pPointer;
}
else
{
pRoot = pRoot->pNext;
delete pPointer; // not sure about pPointer->pNext
}
} while(pRoot);
}

Share this post


Link to post
Share on other sites
That should work except for one thing: in

if(pRoot->pNext == 0) // if there are no elements in the list
{
delete pRoot->pNext;
delete pRoot;
delete pPointer;
}

you're calling delete pRoot AND delete pPointer. Remember that when you set pPointer = pRoot, you didn't copy the data, but only made them both point to the same place in memory. So the delete pRoot frees up that memory. In most cases the delete pPointer immediately after would cause a runtime error. Secondly, this all takes place inside [ if (pRoot->pNext == 0) ]. If it is equal to zero, that means that the pointer is not pointing at anything that needs to be freed, so calling delete pRoot->pNext; accomplishes nothing. So in fact you don't need this part at all, and can go with:

CList::~CList() // destructor
{
do
{
CNode *pPointer;
pPointer = pRoot; // sets the pointer to start at the beginning of the list
pRoot = pRoot->pNext;
delete pPointer;
} while(pRoot);
}



This will work fine as long as you make sure that pNext for the last node is 0. In other words, every time you delete the last node, make sure to set the previous node's (the one pointing to it) pNext to 0 explicitly.

EDIT: Oops, actually it won't work fine, if the list is empty (i.e. pRoot will be 0 as well). So just change it to while (pRoot) { ... } instead of do { ... } while (pRoot).

Share this post


Link to post
Share on other sites
just some comments:
if you already know pRoot->pNext == 0, you don't need to delete this pointer, but it will do you no harm

The name pRoot is not good choosen, as you use this variable as iterator about your list, and for pRoot I think of the start pointer of your list

one big problem can you get from this:
pPointer = pRoot

and than deleting pPointer and pRoot
especially as you delete two times the same pointer, this can crash your program.

When will while(pRoot) no longer be true?

You never change pRoot to NULL (delete doesn't do this)

Share this post


Link to post
Share on other sites
Thanks TDragon, have some rating++ for your helpfulness :P

I'll have a look at deleting from the end of the list now, which shouldnt be a problem at all now that we've had this practise!

Thanks anyway Sparhawk42, a couple of comments on your post though
Quote:
When will while(pRoot) no longer be true?
This will no longer be true when pRoot no longer exists, i'm no expert in C++ but that's what i thought anyway
Quote:
You never change pRoot to NULL (delete doesn't do this)
Does this matter? i'm not deleting one element, im deleting them all, as it's the destructor

Share this post


Link to post
Share on other sites
@Sparhawk: pRoot can become null if one of the nodes' pNext is null, at the assignment "pRoot = pRoot->pNext;".

EDIT: Okay, the original OP answered this. Yep, Welshy, correct on both counts :)

Share this post


Link to post
Share on other sites

This topic is 4526 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this