?
Solved

linked list deletion ?

Posted on 2003-03-06
8
Medium Priority
?
245 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
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

Introducing Priority Question

Increase expert visibility of your issues by participating in Priority Question, our latest feature for Premium and Team Account holders. Adjust the priority of your question to get emergent issues in front of subject-matter experts for help when you need it most.

Question has a verified solution.

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

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
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.
Suggested Courses

741 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