When implementing a linked list in C who is responsible for freeing the value?

Question

I am implementing a linked list in C and I am running into the issue where C does not implement any specific scheme for memory management other than just giving you the ability to allocate and free memory by passing a pointer. There is no concept of whether the value might be needed later on in the program.

The typical implementation I find online for a linked list basically deallocs the deleted node but does not dealloc the node's value.

Whose responsibility should it be to release the memory taken up by the value when deleted from the list ? The linked list's or the normal flow of the program ?

example:

// allocate 10 bytes
char *text = malloc(sizeof(char) * 10);

// create the linked list
LinkedList *list = list_create();

// add the text pointer to the linked list
list_append(list, text);
// remove the pointer from the linked list
list_remove_last(list);

In this case text would end up not getting deallocated as list_remove_last just frees the memory that the new node takes up. What would be the proper way to release the memory taken up by text ?

Answer 1

that is a very common way of container implementation in C. basically you dynamically allocate the contents of the list and pass the pointer to the container, now the container is responsible for freeing it.

You can also pass in a function pointer to list_create() so it knows how to do list_remove_last() properly, this is especially useful for using a generic container that does not know what type of elements it will contain (it will just hold void * pointers). think of the case where the data itself is a struct that contains other pointers. in this case list_remove() can not do a simple free() on its data field, instead it should use the function pointer that was passed in to free the data.

your approach has a small problem:

if you have list* as the return type of list_create(), then you will have to do a free(list) in your main function. alternatively, you can have list_create() return a list, as opposed to a list*, this is a logical choice because a list has its bulk of information dynamically allocated and accessible through a pointer anyway.

in the second case you would need a function list_destroy(list) that would destroy any element your list holds.

Answer 2

C does not implement any specific scheme for memory management other than just giving you the ability to allocate and free memory by passing a pointer

Yes, C lacks any kind of automatic memory management, so you have to be careful to deallocate any memory blocks that you instantiate.

Whose responsibility should it be to release the memory taken up by the value when deleted from the list? The linked list's or the normal flow of the program?

It's your responsibility. You can do it however you like. You can write a general purpose linked list where the caller has to be responsible for allocating and deallocating space for each value in the list because the list management functions don't know how much space each value might require, or whether the values might be needed beyond the lifetime of the node. Or, you can write a list implementation that manages every aspect of the node, including space for the value stored in the node. In some cases, a list node includes the value in the node definition, like:

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

and other times the node has a pointer to some other block that has the actual value:

struct Node {
    struct Node *next;
    void *value;
};

Another approach is to define a structure with just the part needed for the list operation (i.e. the next pointer), and then piggyback data onto that structure:

struct Node {
    struct Node *next;
};

struct MyNode {
    struct Node node;
    int price;
    int quantity;
};

So, there are lots of ways to do it, and none of them are wrong. You should choose the style that makes sense for your needs. Do you have big, complex values that you don't want to duplicate, that you want to store in a linked list, but which you want to continue to use even after they're removed from the list? Go with the first style above. Do you want to manage everything related to the linked list in one place? Then go with the second style.

The point is: C dictates a lot less than other languages do, and while that means that you have to think harder about program correctness, you also get the freedom to do things very directly and in a style of your choosing. Embrace that.