# Linked list destructor

## Recommended Posts

Welshy    223
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 on other sites
TDragon    679
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 on other sites
Welshy    223
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 on other sites
TDragon    679
Quote:
 Original post by WelshyI'm using C++. Alright, now to go make an algorithm to delete all nodes :PYeah 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'sAnyway, 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 on other sites
Welshy    223
Quote:
Original post by TDragon
Quote:
 Original post by WelshyI'm using C++. Alright, now to go make an algorithm to delete all nodes :PYeah 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'sAnyway, 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 on other sites
Rattrap    3385
Recommendation: Recursive deletes.

##### Share on other sites
Welshy    223
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 on other sites
Telastyn    3777
Remember, if pointer a and pointer b point at the same thing, and either is deleted, both are then invalid [since the memory they point to is free'd/delete'd]

##### Share on other sites
Welshy    223
Then how would you keep track of where you are in the deletion process?

##### Share on other sites
Telastyn    3777
Quote:
 Original post by WelshyThen how would you keep track of where you are in the deletion process?

That's part of the fun!

There's probably 3-4 ways to do it.

##### Share on other sites
Fruny    1658
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 on other sites
TDragon    679
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 on other sites
Welshy    223
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 on other sites
Welshy    223
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 on other sites
TDragon    679
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 on other sites
Welshy    223
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 on other sites
TDragon    679
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 on other sites
Sparhawk42    138
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 on other sites
Welshy    223
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 on other sites
TDragon    679
@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 :)

## 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