Memory allocation for linked list in C

Question

I am new to C and am writing a basic program to calculate the arithmetic sum of two numbers stored in a linked list.

My main question is idiomatic memory management in C. The program below allocates a new linked list node, but does not deallocate it. What is a good way to do so?

#include <stdio.h>
#include <stdlib.h>
typedef struct SinglyLinkedListInt {
 int value;
 struct SinglyLinkedListInt *next;
} SinglyLinkedListInt;
SinglyLinkedListInt *add_two_numbers(SinglyLinkedListInt *l1, SinglyLinkedListInt *l2) {
 SinglyLinkedListInt root = { .value = 0, .next = NULL };
 SinglyLinkedListInt *current = &root;
 int carry = 0;
 while (l1 || l2 || carry) {
 int a = l1 ? l1->value : 0;
 int b = l2 ? l2->value : 0;
 int value = carry + a + b;
 SinglyLinkedListInt *next = malloc(sizeof(SinglyLinkedListInt));
 next->value = value % 10;
 next->next = NULL;
 current->next = next;
 carry = value / 10;
 l1 = l1 ? l1->next : NULL;
 l2 = l2 ? l2->next : NULL;
 current = current->next;
 }
 return root.next;
}
int main() {
 SinglyLinkedListInt l13 = { .value = 3, .next = NULL };
 SinglyLinkedListInt l12 = { .value = 4, .next = &l13 };
 SinglyLinkedListInt l11 = { .value = 2, .next = &l12 };
 SinglyLinkedListInt l23 = { .value = 4, .next = NULL };
 SinglyLinkedListInt l22 = { .value = 6, .next = &l23 };
 SinglyLinkedListInt l21 = { .value = 5, .next = &l22 };
 SinglyLinkedListInt *result = add_two_numbers(&l11, &l21);
 while (result) {
 printf("%d ", result->value);
 result = result->next;
 }
 printf("\n");
 return 0;
}

Answer 1

I think you're on the right track with this, but that there are some improvements you could make.

A Better Abstraction

The way you have it now, a user of this linked list type has to do a bunch of work to create and maintain the list. You could make it a lot easier on a user to define a list type separate from the node type. Something like this:

typedef struct IntNode {
 int value;
 struct IntNode *next;
} IntNode;

and

typedef struct IntList {
 IntNode *head;
 IntNode *tail;
} IntList;

What this allows you to do is quickly insert at the head and tail, which are 2 common operations. It also means that a user of this type doesn't have to make all the links between the nodes manually.

You could add a function to create a new empty list, a function to insert an int into the list at the tail, and another to remove an int from the list. Once you have the creation and insertion functions, you don't need to put memory allocation code into the add() function. You would simply create the list at the start of the add() function, then as you go through the 2 input lists, generate the new int containing the sum, and insert it into the list. It might look something like this:

SinglyLinkedListInt *add_two_numbers(SinglyLinkedListInt *l1, SinglyLinkedListInt *l2) {
 SinglyLinkedListInt *result = create_new_list();
 if (result == NULL)
 {
 return NULL;
 }
 int carry = 0;
 while (l1 || l2 || carry) {
 int a = l1 ? l1->value : 0;
 int b = l2 ? l2->value : 0;
 int value = carry + a + b;
 append(result, value % 10);
 carry = value / 10;
 l1 = l1 ? l1->next : NULL;
 l2 = l2 ? l2->next : NULL;
 }
 return result;
}

Here you'd write the create_new_list() function and the append() function that would add the new value to the end of the list. Now you don't have allocation code in a math function, and you don't need to keep track of the current node and keep incrementing it. (As pointed out by @chux, you will need some way to tell whether append() successfully allocated memory or not. I would probably have it return a boolean indicating success or failure and make sure to check it after calling.)

Memory Management

You are correct that not calling free() on something that you've created with malloc() is a problem. In the code you currently have, you should be freeing result and every node in the list after you're done using them. Note that that's one more thing a user of this code has to keep track of: some lists are created on the stack and some are created on the heap, and it's even possible that some nodes in the same list could be created in different places and need to be handled differently for freeing them.

If they were always created on the heap, it would simplify using the type by having a free_list() function that did it for you. If you used my above suggestion about creating a separate IntList type, it might look something like this:

void free_list(IntList *list)
{
 if (list == NULL)
 {
 return;
 }
 
 IntNode* current_node = list->head;
 IntNode* next_node = NULL;
 while (current_node != NULL)
 {
 next_node = current_node->next;
 free(current_node);
 current_node = next_node;
 }
 list->head = NULL;
 list->tail = NULL;
 free(list);
}

Then your call sequence becomes:

IntList* list = create_new_list();
// ... Add some nodes
list->append(...);
list->append(...);
//... do whatever else with the list
free_list(list);

• chux: A 2 member struct like typedef struct IntList { IntNode *head; IntNode *tail; } IntList; is not necessary to add to the head and tail of a LL. A pointer to the tail (whose next member points to the head) is sufficient.
• chux: void free_list(IntList *list) should set its members to NULL before returning. list->head = NULL; (and list->tail = NULL; if implemented.) Otherwise, free(list) may be needed here.
• chux: This code checks for allocation error with if (result == NULL), that is good. Yet does not look for allocation error due to append(result, value % 10);, that is inconsistent. OP's use of root allows for a single check (presently missing) right after the malloc() an advantage to OP's header-less LL.
• user1118321: Regarding only keeping a pointer to tail - that seems like the type of thing that will lead to subtle bugs because it's non-obvious, and it only saves 4-8 bytes typically, so not worth it in my opinion. The struct with both head and tail is much clearer. But good points otherwise. I'll make an update shortly.
• chux: An applications may have millions of linked-lists with the majority of them empty - LL are a core building block for many applications. Having an efficient empty size of 4 vs. 8 is significant. Concerning bug-ness this answer's first header & LL approach failed to free memory properly and did not check for out-of-memory in the LL allocation path. Various approaches have their value.

Answer 2

Code design has problems if int value is negative. After summing, the sum may have some LL nodes with positive values and other with negative ones. Additional code needed to handle this, including the shrinking of the LL, should there be cancellation.

If code is only designed for positive numbers, then use unsigned value;

---

Consider an easier to code, review and maintain allocation idiom:

// ptr = malloc(sizeof (type_pointed_to_by_ptr));
ptr = malloc(sizeof *ptr);

---

OP's use of a local root would benefit with a "only the .next member is used" comment. The use of a temporary "root" makes for efficient code. Don't give up on this style.

SinglyLinkedListInt *add_two_numbers(SinglyLinkedListInt *l1, SinglyLinkedListInt *l2) {
 SinglyLinkedListInt root = { .next = NULL /* Only next member used */};
 SinglyLinkedListInt *current = &root;

---

const can allow for some optimizations and it also conveys to the caller that the LL are not changed.

SinglyLinkedListInt *add_two_numbers(const SinglyLinkedListInt *l1, 
 const SinglyLinkedListInt *l2) {

---

OP did not use restrict here, which is good, to allow b = a + a

SinglyLinkedListInt *result = add_two_numbers(&l11, &l11);

Answer 3

The artificial root node gets inaccessible after the return of root.next. One should immediately free it. However better is to not allocate it in the first place.

This is done by having current be an alias of either the root list (null), or a next field.

SinglyLinkedListInt *root = NULL;
SinglyLinkedListInt **current = &root;
...
 *current = next;
 carry = value / 10;
 l1 = l1 ? l1->next : NULL;
 l2 = l2 ? l2->next : NULL;
 current = &(*current)->next;
...
return root;

As you see aliasing (altering root or a next field) is a unique property of C, not present in java for instance.

Freeing a list can be done on the entire list, as long as lists are created in their integrally, not single nodes.

void freeSinglyLinkedListInt(SinglyLinkedListInt *list) {
 while (list) {
 SinglyLinkedListInt *current = list;
 list = list->next;
 free(current);
 }
}

Usage:

freeSinglyLinkedListInt(list);
list = NULL; // No longer usable.

About naming and so on I see no problem; a bit long, but clear. The struct would be a "node", but a struct pointer already a "list." Borrow the convention from other places, I am no longer primarily occupated with C, and am unsure whether to recommend anything like a typedef.

• chux: OP's SinglyLinkedListInt root = { .value = 0, .next = NULL }; is not allocated and so should not be free'd. Only the root.next is returned and the fact that root goes out of scope is of no consequence.
• Joop Eggen: @chux that betrays my everydays work is in java.

Answer 4

Here's a problem:

SinglyLinkedListInt *next = malloc(sizeof(SinglyLinkedListInt));
next->value = value % 10;

If malloc() returns a null pointer, then accessing next->value is undefined behaviour. Always handle all possible return values!

Style point: instead of repeating the type name to compute the size, it's usually safer to use the object as argument:

SinglyLinkedListInt *const next = malloc(sizeof *next);

(I added const to make it more obvious that we never change next to point anywhere else.)