Read access violation while deleting multiple nodes from a linked list-CodePudding

I need to implement a doubly linked list in c for a small animation running on console. The linkedlist stores clouds and then they move through the console and as each cloud hits the end of screen, it needs to be deleted from linked list. As the cloud hits the end, it has a variable called alive which is set to false so it can be deleted.

I can't upload the full game code, but I have recreated the problem in dummy code by creating sample clouds where some of them have alive = true and alive = false. I have also updated the previous and next nodes of the cloud to be deleted but I still get an error:

Exception thrown: read access violation. temp was 0xFFFFFFFFFFFFFFFF.

Code below (include statements removed for simplicity)

Test.cpp

int main() {

    Cloud* a = new Cloud('a');
    a->alive = false;
    Node* a1 = new Node(a);
    Cloud* b = new Cloud('b');
    b->alive = false;
    Node* b1 = new Node(b);

    LinkedList list;
    list.Insert(a);
    list.Insert(b);

    Node* temp = list.head;
    while (temp != nullptr) {
        if (temp->data->alive == false) list.Delete(temp); // throws exception after deleting a single node.
        temp = temp->next;
    }
    return 0;
}

LinkedList.cpp delete function

void LinkedList::Delete(Node* del) {

    if (del == head) {
        OutputDebugStringA("Cloud in head");
        Node* temp = head;
        head = head->next;
        head->prev = nullptr;
        delete temp;
        return;
    }
    else {
        Node* temp = head;
        while (temp != tail->next) {

            if (temp == del) {
                if (temp->next != nullptr) {
                    OutputDebugStringA("Cloud in mid");
                    temp->prev->next = temp->next;
                    temp->next->prev = temp->prev;
                    break;
                }
                else {
                    OutputDebugStringA("cloud at tail");
                    tail = temp->prev;
                    tail->next = nullptr;
                    break;  
                }
            }
            temp = temp->next;
        }
        delete temp;
        temp = nullptr;
    }
}

Node.cpp

#include "Node.h"
#include <iostream>
using namespace std;


Node::Node() {
    this->data = nullptr;
}

Node::Node(Cloud* data) {
    this->data = data;
}

Someone please point out where am I going wrong. Thanks

CodePudding user response：

        if (temp->data->alive == false) list.Delete(temp); // throws exception after deleting a single node.
        temp = temp->next;

Here, temp gets passed into the Delete() method. Afterwards temp gets set to temp->next.

In Delete():

        delete temp;
        temp = nullptr;

The object referenced by the passed-in temp pointer (here, this temp, by the virtue of the preceding logic, is the same pointer that gets passed in) gets deleted.

After returning, temp->next references a deleted object.

This is at least one confirmed instance of undefined behavior in the shown code. This may or may not be the only bug.

As it's been pointed out to you in comments, this overall Delete() logic is fundamentally flawed. It should not involve any kind of iteration, for a doubly-linked list. You will end up fixing this bug while rewriting Delete() from scratch (which includes rethinking how Delete() itself gets called, because after it returns temp is no longer usable for anything).

CodePudding user response：

As @John Zwinck and @Sam Varshavchik pointed out that the implementation of delete method was flawed and temp became useless after the Delete function returned.

I fixed it by using another temp pointer and fixing the delete method to be O(1).

Delete Method

void LinkedList::Delete(Node* del) {
    if (del == head) {
        head = head->next;
        head->prev = nullptr;
    }
    else if (del == tail) {
        tail = del->prev;
        tail->next = nullptr;
    }
    else {
        del->prev->next = del->next;
        del->next->prev = del->prev;
    }
    delete del;
}

Node deletion

Node* temp = cloud_list.head;
        Node* next;
        while (temp != nullptr) {
            next = temp->next;
            if (temp->data->alive == false) {
                cloud_list.Delete(temp);
            }
            temp = next;
        }

The deletion now works fine.