Free a doubly linked list in C

Question

I have a doubly linked list in C and I'm confused as to how I should go about freeing it. I understand that I have to traverse the list freeing each node. Where the confusion lies is that each of my nodes has a pointer to some other data and I'm unsure how I should free that.

My doubly linked list looks like this:

typedef struct Node_ Node;
typedef struct List_ List;

struct Node_ {
    void *data;
    Node *next;
    Node *prev;
};

struct List_ {
    Node *firstNode;
    Node *lastNode;
};

To free the list I've created a function called List_free() which traverses the list freeing each node with Node_free(). These functions look like this:

void *List_free(List *list)
{
    Node *next = list->firstNode;

    while(next)
    {
        Node *node = next;
        next = node->next;
        Node_free(node);
    }

    free(list);
}

void Node_free(Node *node)
{
    free(node->data);
    free(node);
}

Where this is going to fall down is where node->data is pointer to another struct that itself contains pointers. In my case I use the same list code to store two different structs.

The way I see it I have the following options:

1. Create lists where nodes hold specific data. Not very reusable.
2. Find another way to keep track of the pointers within the node data.

Am I thinking along the right lines or have I missed something obvious? This is my first attempt at C so I wouldn't be surprised if this is all completely wrong.

Answer 1

One solution is to supply a function pointer responsible for freeing the node properly.

typedef void(*NodeDataFreeFn)(void*);

List_free is modified like this:

void *List_free(List *list, NodeDataFreeFn data_free)
{
    Node *next = list->firstNode;

    while(next)
    {
        Node *node = next;
        next = node->next;
        (*data_free)(node->data);
        free(node);
    }
    free(list);
}

Example data_free:

void data_free_fn(void* data_ptr) {
    // Add your custom stuff here.
    free(data_ptr);
}

Example call to List_free:

List_free(my_list, data_free_fn);

If you don't want to pass the data free function pointer by argument, you could store it into the List structure like this instead:

struct List_ {
   Node *firstNode;
   Node *lastNode;
   NodeDataFreeFn data_free;
};

Disclaimer: I didn't test this code, it may be buggy...

Answer 2

You're not wrong, that's one of the problems 'solved' by OOP and in particular C++.

You could add a pointer to function member in your struct that would be used to free its data. Basically adding a C++ destructor by hand. That would keep genericity without too much duplication.