Recursion Destroy Singly linked List, memory leak?

Question

I'm working through some personal test code to make sure I understand how to work withs singly linked lists.

I'm basically going through the Week 5 Section video on singly linked lists and putting code together for each action outlined in the video.

I'm stuck putting the code together that will "destroy" a singly linked list. The idea illustrated in the Section video makes sense (recursion to free each node in the list, from end to beginning).

the initial function call in main is

removeall (Team);

where Team is a pointer to the head of the list.

my current code for the function is below

void removeall(REBEL* Team)
{
  if (Team->next == NULL)
  {
    free(Team);
  }
  else
  {

  removeall (Team->next); 
  }
}

The code runs but when I run Valgrind, it says:

HEAP SUMMARY: ==4951== in use at exit: 72 bytes in 3 blocks ==4951==
total heap usage: 4 allocs, 1 frees, 96 bytes allocated

I don't understand why it is only 1 free? Was hoping for 4 frees.

Any thoughts would be appreciated. Thank you

Answer 1

You have only implemented part of your goal. This code will walk down a linked list to the last element, but will only free memory when it finds that the next element is null, i.e., it is at the end of the list.

To free memory as you go (beginning to end), you should create a temp pointer to hold the address of the next element, and then free the current element, and only then do the recursive call using the temp pointer.

However, if you want to free from end to beginning, (you would in a trie, not necessary in a linked list), you'd need to go to the end, free the last node, and return back through the recursion.

The next problem is returning, with or without a result. Your code would, once fixed, free all the elements in the linked list, but it does nothing to return a result. Since you created it with a void return type, I guess you don't intend to return a result. If you do wish to return a result, the following will be helpful: Pset3 Binary Search problems

[EDIT: response to comment] Yes, you can implement free from end to beginning.

void removeall(REBEL* Team)
{
  if (Team->next != NULL)
  {
      removeall (Team->next); 
  }
    free(Team);
}

The trick is to drill down to the bottom/end of the list first. Once you get to the null pointer, the code will then execute the free() call at the last recursive call to removeall. Then, it will return to the next level up, come out of the if() code block and execute that free() call, and so on, until it gets all the way back to the first call. In this way, the nodes will be freed from the end first. Note that I removed the else clause. The either/or nature of the else clause meant that it would either drill down or free a node, but not both. It needs to execute the recursive calls on the way down and the free calls on the way back up.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)