kevin_in_va
asked on
linked list deletion ?
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
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
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.
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.
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.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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..
=)
~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..
=)
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;
}
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;
}
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
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
ASKER
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
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?