~my_Item()
{
while (next)
{
_my_Item* item = next;
next = item->next;
item->next = NULL; // this prevents the recursion
delete item;
}
}
How to delete a linked list without recursion?
-
07-10-2022 - |
Question
I'm trying to find a way of deleting a linked list without recursion, because a stack overflow isn't really something nice.
I have a struct as follows:
typedef struct _my_Item
{
_my_Item(const std::string& name)
{
m_name = name;
}
~my_Item()
{
delete next; // this recursively deletes the "tail" of the list
next = NULL;
}
struct _my_Item *next;
std::string m_name;
// ... More members here...
}
In some piece of code (not relevant here) I'm constructing a list from a data file using the above structure. I keep the pointer to the head of the list in a variable and can work with it. All fine.
When I finally call the destructor on the head of the list, the destructor gets called and the delete next;
causes a recursion to delete the "tail" of the list (which is the entire list without the first element). Now since the list is quite long, I see a stack overflow sometimes.
Is there a nice way to get around this problem?
Solution
OTHER TIPS
Create a class representing the list itself that will encapsulate nodes deletion in its destructor via a for/while
loop. Doing it the way you do leaves the possibility to delete part of the list and leave dangling pointer.
One suggestion would be to remove the delete code from the destructor and use a pointer to delete the list.
struct _my_Item * nodeToDelete = NULL;
while(firstNode != NULL)
{
nodeToDelete = firstNode;
firstNode = firstNode->next;
delete nodeToDelete;
}
// I wrote this java code to delete a node from BST
// I only used one recursion call to remove successor
public Boolean delete(int data){
if(isEmpty() || !search(data))
return false;
return delete(null,root,data);
}
public Boolean delete(Node parent,Node temp,int data) {
while(true){
if(data == temp.getData()) {
break;
} else if(data < temp.getData()) {
parent = temp;
temp = temp.getLeft();
} else {
parent = temp;
temp = temp.getRight();
}
}
if(parent == null && (temp.getLeft() == null || temp.getRight() == null)){
if(temp.getLeft() == null)
root = temp.getRight();
else
root = temp.getLeft();
} else if(temp.getLeft() == null || temp.getRight() == null) {
if (parent.getLeft() == temp) {
if (temp.getLeft() == null)
parent.setLeft(temp.getRight());
else
parent.setLeft(temp.getLeft());
} else if (parent.getRight() == temp) {
if (temp.getLeft() == null)
parent.setRight(temp.getRight());
else
parent.setRight(temp.getLeft());
}
}else{
int min = findMin(temp.getRight());
temp.setData(min);
delete(temp,temp.getRight(),min);
}
return true;
}