Unexpected return value from main() function

Question

I am working with doubly linked list. Every function operates well but at the end of main(), it stalls few seconds and return an unexpected random value.

At first I thought it was caused by the report() function, thus I put one more add() function at the end but nothing got fixed. I doubt it is a memory deallocating problem, but I don't see where some object got pre-deallocated. (Compiled using Code::Blocks 17.12).

Here is my .cpp file (all in one):

#include <iostream>
using namespace std;

typedef struct element {
    element(){
        data = 0;
        next = 0;
        prev = 0;
    }
    ~element(){
        delete next;
        delete prev;
        cout << "element destructed" << endl;
    }
    int data;
    element* next;
    element* prev;
} elem;

typedef struct doublylinkedlist{
    doublylinkedlist(){
        head = 0; tail = 0;
    }
    ~doublylinkedlist(){
        while(head!=0) {
        head = head->next;
        delete head->prev;
    }
        delete tail;
        cout << "list destructed" << endl;
    }
    elem* head;
    elem* tail;
} doublyll;

doublyll ls;

void add(){
    elem* temp = new elem;
    cout << "Enter an integer: ";
    cin >> temp->data;

    if(ls.head == 0) {//empty
        ls.head = new elem;
        ls.head = temp;

    } else{
        if(ls.tail == 0){  //1-item list
            ls.tail = new elem;
            ls.tail = temp;
            ls.head->next = ls.tail;
            ls.tail->prev = ls.head;
        }
        else{
            temp->prev = ls.tail;
            ls.tail->next = temp;
            ls.tail = temp;
        }
    }
}

void report(){
    if(ls.head == 0) cout << "List is empty!" << endl;
    else{
        elem *temp = ls.head;
        do{
            cout << temp->data << endl;
            temp = temp->next;
        } while (temp != 0);
    }
}



int main(){
    report();
    add();
    add();
    add();
    report();
    add();
    return 0;
}

Could someone point out where the error comes from and how to fix it? I want the main() not to stall and return 0 as usual, not to the opposite. This is the program when executed, this is my build message

Answer 1

First point: The elements will be deallocated by the class doublylinkedlist, so deallocating elements in the class element will cause double-deallocation. Therefore, you should remove two delete statements from the destructior of the lass element.

    ~element(){
        /* remove them */
        //delete next;
        //delete prev;
        cout << "element destructed" << endl;
    }

Second point: In the destructor of doublylinkedlist, head->prev is read after head = head->next; without checking if head is NULL. head can be NULL by the assignment, so it should be checked.

    ~doublylinkedlist(){
        while(head!=0) {
            head = head->next;
            if (head!=0) /* add this */
                delete head->prev;
        }
        delete tail;
        cout << "list destructed" << endl;
    }

The last element will be deallocated by delete tail;, so this code looks tricky but should be OK.

Extra point: These code segments

        ls.head = new elem;
        ls.head = temp;

and

            ls.tail = new elem;
            ls.tail = temp;

are causing memory leaks by allocating elements and throwing them right away. You should remove the extra allocations.

        /* remove this */
        //ls.head = new elem;
        ls.head = temp;

and

            /* remove this */
            //ls.tail = new elem;
            ls.tail = temp;

Answer 2

Unless you are using std::shared_ptr or similar constructs each object needs to have one other object which is it's owner and is responsible for deallocating it. Your code needs to have clear semantics for transferring ownership (e.g. a function createNode() would expect its caller to destroy the node).

In your code nodes are both deleted by the list and by each element. This means everything gets deleted twice (or more). In your particular case this is the sequence of events on destruction of doublylinkedlist:

1. doublylinkedlist deletes its first element.
2. The destructor of the first element deletes its previous element, this is null so has no effect
3. The destructor of the first element deletes its next element (the second element).
4. The destructor of the second element deletes its previous element (the first element)
5. The destructor of the first element deletes its previous element, this is null so has no effect
6. The destructor of the first element deletes its next element (the second element).

This infinite loop eventually causes a stack overflow. Note that this isn't guaranteed to be the exact sequence of events as deleting an object twice is undefined behaviour so potentially anything could happen.

The simple fix is to remove the element destructor and have the list be responsible for the lifetime of all elements. You should also modify your doublylinkedlist destructor as it will attempt to dereference a null pointer on the last element, you also don't need to delete tail as it should have already been deleted. E.g:

~doublylinkedlist(){
    while(head!=0) {
        auto temp = head;
        head = head->next;
        delete temp;
    }
}

You shoudl also make sure you obey the rule of three/five). One way of doing this is to make use of smart pointers, for example using unique_ptrs your code could look like this:

#include <iostream>
#include <memory>
using namespace std;

typedef struct element {
    element() {
        data = 0;
        next = nullptr;
        prev = nullptr;
    }
    ~element() {
        cout << "element destructed" << endl;
    }
    int data;
    std::unique_ptr< element > next;
    element* prev;
} elem;

typedef struct doublylinkedlist {
    doublylinkedlist() {
        head = 0; tail = 0;
    }
    ~doublylinkedlist() {
        std::cout << "list destructed\n";
    }

    std::unique_ptr< elem > head;
    elem* tail;
} doublyll;

doublyll ls;

void add() {
    std::unique_ptr<elem> temp(new elem());
    cout << "Enter an integer: ";
    cin >> temp->data;

    if (ls.head == nullptr) {//empty
        ls.head = std::move(temp);
    }
    else {
        if (ls.tail == nullptr) {  //1-item list
            ls.head->next = std::move(temp);
            ls.tail = ls.head->next.get();
            ls.tail->prev = ls.head.get();
        }
        else {
            temp->prev = ls.tail;
            ls.tail->next = std::move(temp);
            ls.tail = ls.tail->next.get();
        }
    }
}

void report() {
    if (ls.head == 0) cout << "List is empty!" << endl;
    else {
        elem *temp = ls.head.get();
        do {
            cout << temp->data << endl;
            temp = temp->next.get();
        } while (temp != 0);
    }
}

int main() {
    report();
    add();
    add();
    add();
    report();
    add();
    return 0;
}

The ownership of elements is now explicit, the list owns head and head owns its next node which owns its next node etc. Destroying the list automatically destroys the first node which automatically destroys the second node etc. In this code you can actually omit the destructors completely. This should also help to prevent memory leaks, for example if you decide to add some error checking to add the unused temp element gets automatically deleted:

void add() {
    std::unique_ptr<elem> temp(new elem());
    cout << "Enter an integer: ";
    cin >> temp->data;
    if (!cin || temp->data > 100) {
       cout << "invalid input value\n";
       return; // temp is automatically deleted here
    }
    ...
}