CODEWITHSUNDEEP
c++nodesdoubly-linked-listdelete-operatorfunction-definition
Inexpli
Inexpli

Reputation: 90

Can't delete node from node list

I have a little problem which occurs after trying to execute function delete_all(). Any idea why Visual Studio is throwing me an error:

Invalid address specified to RtlValidateHeap, instruction __debugbreak() or something similar

Everything works perfect until I want to execute this function.

#include <iostream>

using namespace std;

struct node {
    string name = "n1";
    node* prev = NULL;
    node* next = NULL;
};

node* add(node* first, string name) {
    if (first == NULL) {
        return NULL;
    }

    node* nowy = new node;

    if (first->next == NULL) {
        nowy->prev = first;
        first->next = nowy;
    }
    else {
        while (first->next != NULL) {
            first = first->next;
        }
        nowy->prev = first;
        first->next = nowy;
    }

    nowy->name = name;

    return nowy;
}

void writeout(node* first) {
    if (first == NULL) cout << "first = NULL";

    while (first->next != NULL) {
        cout << first->name;
        cout << "\n";
        first = first->next;
    }

    if (first->next == NULL) {
        cout << first->name;
        cout << "\n";
    }
}

void delete_all(node* first) {
    node* temp;
    while (first != NULL) {
        temp = first->next;
        delete first;
        first = temp;
    }
}

int main()
{   
    node n1;

    add(&n1, "n2");
    add(&n1, "n3");

    writeout(&n1);

    delete_all(&n1);
}

Upvotes: 0

Views: 80

Answers (2)

Remy Lebeau
Remy Lebeau

Reputation: 596407

Your implementation of delete_all() is fine, but you are passing it a pointer to a node instance that was not created with new, so delete'ing that node is undefined behavior. ALL of your node instances should be created dynamically, including the 1st node.

As such, your add() function should be updated to not blindly return without creating a new node instance if first is initially NULL. You should instead update the caller's node* pointer to point at the new node that was created.

Also, writout() has undefined behavior if first is NULL, because you are unconditionally accessing first->next whether first is NULL or not.

With that said, try something more like this instead:

#include <iostream>

using namespace std;

struct node {
    string name = "n1";
    node* prev = nullptr;
    node* next = nullptr;
};

node* add(node* &first, string name) {
    if (!first) {
        first = new node{name};
        return first;
    }
    else {
        node *prev = first;
        while (prev->next) {
            prev = prev->next;
        }
        prev->next = new node{name, prev};
        return prev->next;
    }
}

/* alternatively:

node* add(node* &first, string name) {
    node **nowy = &first, *prev = nullptr;
    while (*nowy) {
        prev = *nowy;
        nowy = &(prev->next);
    }
    *nowy = new node{name, prev};
    return *nowy;
}

*/

void writeout(node* first) {
    if (!first) {
        cout << "first = NULL";
    }
    else {
        do {
            cout << first->name;
            first = first->next;
            if (first) cout << '\n';
        }
        while (first);
    }
}

void delete_all(node* first) {
    node* temp;
    while (first) {
        temp = first->next;
        delete first;
        first = temp;
    }
}

int main()
{   
    node* n1 = nullptr;

    add(n1, "n2");
    add(n1, "n3");

    writeout(n1);

    delete_all(n1);
}

Alternatively:

...

node* add(node* first, string name) {
    if (!first) {
        return new node{name};
    }
    else {
        while (first->next) {
            first = first->next;
        }
        first->next = new node{name, first};
        return first->next;
    }
}

/* alternatively

node* add(node* first, string name) {
    // same as node** further above ...
}

*/

...

int main()
{   
    node* n1 = add(nullptr, "n2");
    add(n1, "n3");

    ...

    delete_all(n1);
}

Upvotes: 2

Vlad from Moscow
Vlad from Moscow

Reputation: 310980

You declared an object in main() with automatic storage duration as the first node of the list:

node n1;

You may not destroy it using the delete operator.

Using your approach of the list implementation, you could define the function delete_all() the following way:

void delete_all(node* first) 
{
    if ( first != nullptr )
    {
        while ( first->next != nullptr ) 
        {
            node *temp = first->next;
            first->next = temp->next;
            delete temp;
        }
    }
}

But, it will be much better if initially in main(), you declared a pointer to a node. In this case, you will need to update the functions.

Upvotes: 2

Related Questions