?
Solved

linked list deletion ?

Posted on 2003-03-06
8
Medium Priority
?
246 Views
Last Modified: 2010-04-01
I have seen a few different ways that people free up the memory for nodes in a linked list.  There is one way that I have seen that is confusing to me and I would appreciate an explanation of how it works:

Having a dummy head node that points to the next node and so on:

Node * pHead = new Node;
pHead->next  = new Node;
pHead->next->next = new Node;

//then calling...

delete pHead;

 // ....to free up the memory for all of the Nodes in the whole list

It seems to me that saying "delete pHead;" should just deallocate memory for the Node pHead points to, not get rid of the memory for the rest of them.  How does this work?  
I have seen people call this a recursive solution, so it might not be good for a big list because of memory issues?

Thanks for your help
0
Comment
Question by:kevin_in_va
8 Comments
 

Expert Comment

by:Shlagbaum
ID: 8082536
It's possible if Node's destructor is defined like this:
Node::~Node()
{
   delete next;
}

You are right, this will recursively call a destructor for all nodes in a list and may be not appropriate for a big list. Why not using standard std::list?
0
 
LVL 1

Expert Comment

by:helmet275
ID: 8083200
If you doubly link your list and add a tail node, you could start at the tail and delete from the bottom of the list towards the top.  The way you're describing has to start at the beginning of the list and then repeatedly call the destructor until it hits the end in which case it would then delete from the bottom up.
0
 

Expert Comment

by:designedmind
ID: 8085899
Shlaqbaum is correct. I, too want to know why not using standard::list?

If you have Other Considerations that prevent you from using the standard list, you should not impliment this solution unless you create new nodes in the same way, that is that a node is the one responsible for adding on additional nodes. like this

template<v_t, ...> class node{
...
void addData(const v_t & i);
...
~Node()
{
  delete next;
}
...
}


and in your addData, you similarily recursively add the node onto the end

node::addData(v_t i){
   if (next) next->addData(i) ;
   else
   {
     next = new node(i);
   }

}

the reason for this is that a node should not have the "right" to delete data it did not create. also, if your nodes act like that, you have to keep this behavior in mind when you are deleting a single node.basicly, it is bad, non-OO design.
0
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
LVL 9

Accepted Solution

by:
Joeisanerd earned 160 total points
ID: 8085911
To elaborate further think of the destructor for the Node as the following:

~Node()
{
  if( this->next != NULL )
      delete this->next;
  return;
}

The above will call the destructor the next node which will in turn call the next node destructor then since that is the last one it will return to the previous destructor that called it and then it will return to the one that called it.

Being recursive means that the function will call itself over and over again until some condition is met and then it will return and return and return and return until it is back to where it started.

For a big list it might now be a good idea to do it this way since using recursion on a lot of data will fill up the stack, thus using more memory. The trade off is less code, more memory.
0
 

Expert Comment

by:designedmind
ID: 8085961
the reason why the previously posted destructor works is because when you call delete on a pointer pointing to null, nothing happens. yet another way to look at it is

~Node()
{
 if( this->next != NULL )
     this->next->~Node();
 return;
}


i argue that the memory thing is a non-issue because you shuldnt be doing it anyway because it violates the OO paradigm..

=)
0
 
LVL 1

Expert Comment

by:manirup
ID: 8086209
Hi
I think it will be better if u do it like this.
I assume that FirstNode is a pointer to the first node in the linked list.
Then in the destructor, or whereever u feel like destroying the linked list u can do the following:

while(FirstNode!=NULL)
{
  temp=FirstNode->Next;
  delete FirstNode;
  FirstNode=temp;
}
0
 
LVL 1

Expert Comment

by:manirup
ID: 8086220
Hi
I think it will be better if u do it like this.
I assume that FirstNode is a pointer to the first node in the linked list. Then in the destructor, or wherever u feel like destroying the linked list u can do the following:

while(FirstNode!=NULL)
{
  temp=FirstNode->Next;
  delete FirstNode;
  FirstNode=temp;
}
Hope this helps u
Bye
Manirup
0
 

Author Comment

by:kevin_in_va
ID: 8088881
Thanks to everyone for their help!  The joeisanerd answer helped me the most so I gave him the points.   I forgot that delete calls the destructor as well as deallocating the memory.  The reason I am not using the stl list is that I am trying to learn how to make some data structures from scratch as a learning exercise even though they are implemented in the stl and that would be easier for a real project.   Thanks again


 
0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

601 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question