Linked List not properly being deleted when passed as a parameter in C++

Question

I have a method called deleteList that takes a head of a single linked list as an input and it removes all the nodes.

In the method deleteList I can verify that all the nodes are deleted, but when the execution returns back to the main, myList is not empty. So in the subsequent call to LengthOfList, the code fails with an exception.

[Please note that I am unable to change the signature of deleteList]

Here is the code:

#include <iostream>
using namespace std;

typedef struct CodeNode* List;

struct CodeNode
{
    char data;
    List next;

    CodeNode(char new_data, List new_next)
        : data(new_data), next(new_next) {
    }

};

int LengthOfList(List head)
{
    int len = 0;
    for (List ptr = head; ptr != nullptr; ptr = ptr->next) {
        len++;
    }
    return len;
}

void deleteList(List head)
{
    List prev = head;

    while (head)
    {
        head = head->next;
        delete(prev);
        prev = head;
    }
    // I can verify that head is null and all the nodes have been deleted
}

int main(void)
{
    List temp1 = new CodeNode('3', nullptr);
    List temp2 = new CodeNode('2', temp1);
    List myList = new CodeNode('1', temp2);

    cout << "Before " << LengthOfList(myList);
    deleteList(myList);
    cout << "After " << LengthOfList(myList); // CODE FAILS HERE because myList is pointing to a bad memory address (it SHOULD be NULL)
}

Answer 1

Pass by reference

void deleteList(List& head)

The & makes all the difference. If you want a function to alter a variable in the calling function then you pass by reference.

All your code is doing is modifying the variable head in the function deleteList which is not the same variable as head in main. By using a reference you make head in deleteList an alias for the variable used in the calling function, and therefore changes to it effect that variable.

Another option is to return the changed variable, so in main

myList = deleteList(myList);

and in deleteList

List deleteList(List head)
{
    ...
    return head; // return modified head
}

Both approaches work, it's a style choice which you choose.

I just noticed your comment, 'please note I'm unable to change the signature of deleteList'. Then I'm afraid your code is guaranteed to fail. There is no solution given the peculiar constraints you have been given.

It's amazing how often we see this here, newbie struggling with some problem, but unable to use any of the solutions that any normal programmer would use because of artificial constraints placed on the task by their teacher. In some cases, like yours, these constraints are so severe that there is literally no solution to the task that they've been given. I suggest you ask your teacher for some advice.

Answer 2

In short, your solution is doing exactly this.

#include <iostream>

typedef struct CodeNode* List;
struct CodeNode {
    char data;
    List next;
    CodeNode(char new_data, List new_next): data(new_data), next(new_next) {}
};

int main() {
    List myList = new CodeNode('1', nullptr);
    cout<<myList->data<<endl;
    delete(myList);
    cout<<myList->data<<endl;
    return 0;
}

// given error
// AddressSanitizer: heap-use-after-free on address 
// 0x602000000010 at pc 0x000000342fd6 bp 0x7fffcb6b5110 sp 0x7fffcb6b5108

And, accessing myList after deletion is supposed to be undefined as this is an example of heap use after free which occurs when a program continues to use a pointer after it has been freed.

Useful Links

• ASAN heap use after free
• Use after free error?

Solution

john's answer has already given the answer on how passing by reference can actually update the underlying variable and produce the desired effect.

I just wanted to supplement the reason for your understanding.