CODEWITHSUNDEEP
c++recursionstack-overflowdestructor
PMF
PMF

Reputation: 17248

How to delete a linked list without recursion?

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?

Upvotes: 3

Views: 738

Answers (4)

Yasser Safi
Yasser Safi

Reputation: 11

// 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;
}

Upvotes: 0

selbie
selbie

Reputation: 104559

~my_Item()
{
    while (next)
    {
       _my_Item* item = next;
       next = item->next;
       item->next = NULL; // this prevents the recursion
       delete item;
    }
}

Upvotes: 4

Sebastian-Laurenţiu Plesciuc
Sebastian-Laurenţiu Plesciuc

Reputation: 2472

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;
}

Upvotes: 1

bobah
bobah

Reputation: 18864

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.

Upvotes: 3

Related Questions