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.