Recursive Method C++

Question

I am practising linked list structure right now and I have written a program using that algorithm. In the program there is a recursive method to remove every element of the linked list. However, the program crashes in that method.

void exit()
{
    Person* person = phead;
    exterminateStartingFrom(person);
}

void exterminateStartingFrom(Person* person)
{
    Person* nextperson;
    nextperson = person->getNext();
    if(nextperson){
        exterminateStartingFrom(nextperson);
    }
    delete person;
}

This method is run when the user wanna exit. "phead" stands for the first element of the person list. The problem showed is : double free or corruption (fasttop)

Here is the class Person :

class Person {
private:
    std::string firstname;
    std::string lastname;
    int age;
    Person* next;

public:
    Person(std::string, std::string, int);
    void printDescription();
    void printFirstname();
    void printLastname();
    void printAge();
    void setNext(Person*);
    Person* getNext();


};

Thanks.

Answer 1

The following is the approach that I took. Naturally this is somewhat contrived as I do not know your actual functionality. I also am representing pHead with an initial global variable and am using age with an out of range value to indicate the head of the list.

For the head of the list I use a special constructor.

There are better ways to do this however in this quick and dirty implementation I needed something to indicate that when backing out during the recursion that I knew when I had backed all the way to the head of the list.

#include <string>

class Person {
private:
    std::string firstname;
    std::string lastname;
    int age;
    Person* next;

public:
    Person (void);                           // constructor for the pHead
    ~Person (void);
    Person(std::string, std::string, int);   // standard constructor used
    std::string getFirstname(void) { return firstname; };
    std::string getLastname(void) { return lastname; }
    void setNext(Person *newNext) { next = newNext; }
    Person* getNext() { return next; }
    Person *addToListAt (Person *personList);
    void addToListAtEnd (Person *personList);
    void Person::insertListAfter (Person *personList);
    bool isHeadOfList (void);
};

Person pHead = Person();

// special constructor used to create the head to a linked list
Person::Person ()
{
    age = -1;
    next = 0;
}

// standard constructor used to create a list item.
Person::Person (std::string sFirstName, std::string sLastName, int myAge)
{
    if (myAge < 0) myAge = 0;
    firstname = sFirstName;
    lastname = sLastName;
    age = myAge;
    next = 0;
}

Person::~Person ()
{
    next = 0;
    age = 0;
}

void exterminateStartingFrom(Person* person)
{
    Person* nextPerson;
    nextPerson = person->getNext();
    if(nextPerson){
        exterminateStartingFrom(nextPerson);
    }

    if (! person->isHeadOfList())
        delete person;
}

Person *Person::addToListAt (Person *personList)
{
    Person* nextPerson;
    nextPerson = personList->getNext();
    personList->setNext (this);
    return nextPerson;
}

void Person::insertListAfter (Person *personList)
{
    Person* nextPerson;
    nextPerson = personList->getNext();
    personList->setNext (this);
    next = nextPerson;
}

void Person::addToListAtEnd (Person *personList)
{
    Person* nextperson;
    nextperson = personList->getNext();
    if(nextperson){
        addToListAtEnd (nextperson);
    } else {
        personList->setNext (this);
    }
}

bool Person::isHeadOfList (void)
{
    // we use a special age to represent the head of the list
    // the head does not contain any data except for point to first item
    // in the list.
    return (age < 0);
}

int main(int argc, char * argv[])
{
    Person *newPerson = new Person("first_1", "last_1", 11);
    newPerson->addToListAtEnd (&pHead);
    newPerson = new Person("first_2", "last_2", 22);
    newPerson->addToListAtEnd (&pHead);
    newPerson = new Person("first_3", "last_3", 33);
    newPerson->addToListAtEnd (&pHead);

    Person *itemPerson = pHead.getNext();
    newPerson = new Person("first_11", "last_11", 12);

    newPerson->insertListAfter (itemPerson);

    exterminateStartingFrom(&pHead);
    return 0;
}

Answer 2

It is hard to tell without knowing how you are constructing or deleting your Person object. Your error message mean that you are deleting the same entity twice or you are deleting something that wasn't allocated. May be try to print the address you are trying to delete so you can check if there is a same address that is deleted more than once?

Also handle the case where the pointer you are passing to your recursive method is nill.

Answer 3

Is your list one-way linked or two-way? If you have a two-way list (you store the pointer not only to the next element but also to the previous one) and you call destructor it is possible that you delete also elements indicated by previous and next fields. When the recursion returns one level up and you want to delete the next to last element you get the error.