CODEWITHSUNDEEP
c++list
VVG
VVG

Reputation: 141

recursive deletion of linked list c++

Could you tell, why the implementation of the next code leads to the error:

void del (num*&head) {
    num*temp = 0;
    if (head!=0) {
        temp = head;
        delete temp;
        del (head->next);
    }
    else return;
}

The error: 

Access violation reading location 0xcdcdcdc1.

Whereas next code works properly:

void del (num*&head) {
    if (head!=0) {
        del (head->next);
        delete head;
    }
    else return;
}

Upvotes: 1

Views: 95

Answers (5)

OldSchool
OldSchool

Reputation: 2183

Think of it in this way:-

when you have done 

 temp = head;// it means temp and head are talking about the same person,i.e, the same memory location.
 delete temp; //the person(memory location) to which the both of them are pointing is dead;
 del (head->next); //Now you trying to kill the "ghost" of the person means you are trying to delete already deleted node.

But in your second case the recursive call is just above

delete head;

so the recursive call first progresses towards the end and then nodes are deleted from the end towards the start, as follows:-

if you have n nodes, the summary of recursive call can be viewed as:-

 del (list); // call from main.
 del (list->head); //recursive call.
 del (list->head->head);//recursive call.
 del (list->head->head->head);//recursive call.

so on..................

so when last node appears its next is NULL so recursion stops and the nodes are deleted from the last call to the first call fashion in other words from the last node towards the first node. So no harm is done here as in your first case.

Upvotes: 1

Yury Schkatula
Yury Schkatula

Reputation: 5369

    temp = head;
    delete temp; // head is dead too!
    del (head->next); // dereferencing disposed pointer

As far as you operate with pointers pointing to the same memory, deleting any of that pointers would make the memory deleted. So, even if you don't delete that other pointers they point to a piece of trash (or even to memory owned by another person)

Upvotes: 1

alain
alain

Reputation: 12047

In the first version,

    temp = head;
    delete temp;
    del (head->next);

temp and head point to the same node, then the node is deleted and becomes invalid. But it is accessed in the last line with

    del (head->next);

The second version does not have this problem.

Upvotes: 1

Ruben
Ruben

Reputation: 540

You're accessing head->next while actually you already deleted head the line before.

Another way to go about this would be:

void del (num*&head) {
    if (head!=0) {
        num* temp = head->next;
        delete head;
        del (temp);
    }
    else return;
}

Upvotes: 1

Mike Seymour
Mike Seymour

Reputation: 254471

Deleting temp invalidates head, since they both point to the same object. head->next tries to access the deleted object, giving undefined behaviour. You should instead store head->next, so you don't have to access the deleted object:

if (head) {
    num * temp = head->next;
    delete head;
    del (temp);
}

You're running a debug build, so the deleted memory was helpfully set to garbage, rather than left with its old contents. This means that trying to use values read from it as pointers will quickly trigger an access violation, helping you find the source of the problem.

The second version waits until you've finished with the object before deleting it, so there's no undefined behaviour.

However, recursion is a bad idea since it could cause a stack overflow if the list is too long. Iteration would be safer:

while (head) {
    num * temp = head->next;
    delete head;
    head = temp;
}

Upvotes: 1

Related Questions