wrong way to free a data structure

Question

I had an exam in C programming in university, one of the question in that exam was how to free a linked list data structure.

My approach was freeing the data for each node, but for no good reason I didn't get the points of that exercise.

This was my code that has not been accepted:

#include <stdlib.h>

struct node {
  int value;
  struct node *next;
};

void free_list(struct node *head) {
  for (struct node *p = head; p != NULL; p = p->next) {
    free(p);
  }
}

Can someone explain what's wrong with it and what's the correct way to free linked list from memory?

Answer 1

The last part of the for loop is reading p->next after the body of the loop has called free(p);.

You need to buffer the pointer:

while (p != NULL)
{
  struct node * const next = p->next;
  free(p);
  p = next;
}

Answer 2

The comment from Sander de Dycker is awesome,

Take time and you will figure out that:

p is freed before p->next is executed, so that p->next reads memory that has already been freed.

If you are looking for a good way to free linked list using for loop try this :

#include <stdlib.h>

struct node {
  int value;
  struct node *next;
};

void free_list(struct node *head) {
  struct node *q;
  for (struct node *p = head; p != NULL; p = q) {
    q = p->next;
    free(p);
  }
}

This mistake is documented in C Bible by Dennis Ritchie

Answer 3

unwind hit the nail on the head. Using descriptive names makes it a bit more obvious. You want to ensure you save the pointer to be freed and then advance to the next node in your list before you call free on the saved pointer, e.g.

void free_list(struct node *head) 
{
    while (head) {
        struct node *victim = head;     /* save node to free */
        head = head->next;              /* advance to next before free */
        free (victim);                  /* free node */
    }
}

Answer 4

Can someone explain what's wrong with it

When you have called free on a node, you cannot access head->next. You have to free head->next before head.

and what's the correct way to free linked list from memory?

A pretty elegant solution is recursion. Recursion is good for making code understandable, but unless you are aware of the dangers, avoid it in production code. I often use it for prototyping. Here is an example.

void free_list(struct node *head) 
{
    if(head) {
        // Before freeing the first element, free the rest
        free_list(head->next)     
        // Now it's only one element left to free
        free(head);
    }
}

It works like this. Let's say that we have a list: [e0, e1, e2, ..., en]. We want to free all elements. We do that by first freeing the list [e1, e2, ..., en] and then free the element e0. Next step works the same way. We want to free [e1, e2, ... en], so we start with calling the same algorithm on the list [e2, e3, ..., en] and when that is finished, we free e1. The base case is when we get an empty list [] in which case we do nothing.

You can also do this non-recursively. It's not as pretty, but often more efficient and it eliminates the risk of stack overflow. This is how I would have written this in production code.

void free_list(struct node *head) 
{
    struct node *tmp;
    while(head) {
        tmp = head;
        head = head->next;
        free(tmp);
    }
}