Archived

This topic is now archived and is closed to further replies.

TravisWells

deleting a Linked List?

Recommended Posts

I''ve got a custom linked list (I should have used std::list, but this is older code, and it wouldn''t be simple to rewrite it) and I''m wondering if this is alright, or if it will blow up in unexpected ways later: When I''m done with the list (single linked) I call delete ListBegin; and the List''s deconstructor is something like:
List::~List(){
   if(next){
      delete next;
      next=0;
   }
}
 
Which, if my reasoning is correct, cause the entire list to delete itself. Will this (continue) to work? or should I walk the list, and delete the elements one by one in reverse order? (not that easy since it''s single linked)

Share this post


Link to post
Share on other sites
If it is indeed a linked list structure then all you should have to do is pop the head node and all subsequent nodes will be nullified

Share this post


Link to post
Share on other sites
All removing the head node does it leave the rest of the list hanging in memory with no way to access it.

You have to go through each element and delete it individually. Depending on how it''s defined you can start from the end and work back or start from the front and work forward.

Win2K makes it real easy to check for memory leaks. Open up the system monitor and run your app to create and delete lists a whole bunch of times. If the memory usage for your program only goes up, you''ve done something wrong.

Ben


IcarusIndie.com [ The Labyrinth | DevZone | Indie Mail | Hosting | Tiberian Merchandise | GameShot | Fun With Cutouts ]

Share this post


Link to post
Share on other sites
But shouldn't deleting the head element call the head deconstructor?
Which calls delete this->next , who's deconstructor calls delete this->next, and so on?

[edited by - TravisWells on January 30, 2003 5:53:44 PM]

Share this post


Link to post
Share on other sites
I went looking through some old code of mine on linked lists, and here''s what I found for my destructor . . .

while(head != NULL) {
fence = head;
head = head->next;
delete fence;
}

Where head is the start of the list, and fence is the arbitrary additional pointer for traversing the list. Hopefully this method makes sense.

Your method doesn''t take into account how to delete the actual node itself, and it doesn''t work for the tail node (which won''t have a next, will fail the if statement, and end the function).

Share this post


Link to post
Share on other sites
The tail node should be deleted by the element that has tail as it''s next, i.e. the node before the tail.

It seems that every element gets delete called on it, so shouldn''t they all be deleted?

Share this post


Link to post
Share on other sites
the tail node will have delete called for it by the node before it yes, but all the "delete next" statement does is recall the same destructor function on the node that next points to. So, when you call delete next on the node right before the tail, the destructor will be called on the tail. the code below for your destructor will fall out of the if statement since the tail doesn''t have a next. When it falls out of the if statement, nothing else happens, and the code falls out of the function, having done nothing to the tail itself. At least that''s how I''m reading the code; I could be wrong.

Share this post


Link to post
Share on other sites
There''s nothing else the deconstructor needs to do to the node, I don''t do any other memory allocation that needs to be cleaned up.
Just deleting the node should be enough.

Share this post


Link to post
Share on other sites
The problem with the OP approach is that if you want to only delete one node, you can''t. Deleting a node will delete every node after it. Basically, you can never delete any nodes until you want to delete all of them. Kind of defeats the purpose of a linked list.

However, if that''s ok with you, then it should work.

Share this post


Link to post
Share on other sites