CODEWITHSUNDEEP
c++linked-listdestructordynamic-memory-allocation
Ender_The_Xenocide
Ender_The_Xenocide

Reputation: 350

Why does destructor run into unallocated memory?

I have a singly-linked, circular linked list and am writing a destructor to delete all the nodes. The destructor first severs the head from the rest of the lest to prevent infinite circulation and then I loop through the list and delete all the nodes, eventually, the loop comes back to the head and deletes it as well. In the program I check to make sure that the pointer to the nodes is not NULL and I ran the debugger and it shows that it is NULL at a point which should end the loop, but instead the loop continues and runs into un-allocated memory. Here is my code:

    node<T> *cur = head;
    node<T> *nxt = head->next;
    if (nxt) cur->next = nullptr;
    cur = nxt;

    // walk through the list and delete nodes
    while (cur) {
        cur = cur->next;
        delete cur;
    }

EDIT: Changed code to 

  node<T> *cur = head;
    node<T> *nxt = head->next;
    if (nxt) cur->next = nullptr;
    cur = nxt;

    // walk through the list and delete nodes
    while (cur) {
        nxt = cur->next;
        delete cur;
        cur = nxt;
    }

EDIT 2: Changed code once more to handle edge cases, same problem still occurs.

if (head ==  NULL) return;
    else if (head->next == head) delete head;
    else {
        node<T> *cur = head;
        node<T> *nxt = head->next;
        cur->next = nullptr;
        cur = nxt;
        while(cur) {
            nxt = cur -> next;
            delete cur;
            cur = nxt;
        }
    }

Upvotes: 0

Views: 101

Answers (1)

paxdiablo
paxdiablo

Reputation: 881543

It has nothing to do with the severing, your code to walk the list while deleting elements would be just as faulty in a non-circular list. You advance the pointer then delete what it points to (the next item).

You need to delete the current item (but, of course, you also need to have extracted its next field before that point because, once deleted, all content becomes undefined), something like:

while (cur != nullptr) {
    node<T> *toDelete = cur;
    cur = cur->next;
    delete toDelete;
}

In terms of a full solution to what you need, the algorithm should be:

def delCircList(head):
    # Ignore empty list.

    if head == null:
        return

    # Special for one-element list.

    if head.next == head:
        free head
        return

    # Sever link and set start point.

    curr = head.next
    head.next = null

    # Use normal deletion algorithm.

    while curr != null:
        toDelete = curr
        curr = curr.next
        free toDelete

Upvotes: 2

Related Questions