Linked List Deallocation

The Problem: Orphaned Nodes and Memory Leaks

As we established in Module 7, linked list nodes are allocated on the heap. A head pointer, which typically resides on the stack, holds the address of the first node, and each subsequent node holds the address of the next.

This structure presents a unique challenge for deallocation. If you were to simply call free(head), you would only release the memory for the first node. The head pointer would become invalid, and you would lose your only entry point to the rest of the list. All subsequent nodes would become "orphaned" — their memory would remain allocated on the heap, but your program would have no way to access or free them. This is a classic memory leak.

A slow memory leak might go unnoticed in a short program, but in a game that runs for hours, constantly creating and destroying objects (like enemies, projectiles, or inventory items), the cumulative effect is disastrous. The program's memory footprint will grow relentlessly until it consumes all available system resources and crashes.

To see a dramatic example of this, let's watch a short demonstration of what happens when a program allocates memory in a loop without ever freeing it.

The Algorithm: Safe Traversal and Deallocation

To avoid memory leaks, we must traverse the entire list and call free() on every single node. However, the order of operations is critical. Consider this incorrect approach:

// DO NOT DO THIS
struct Node* current = head;
while (current != NULL) {
    free(current);
    current = current->next; // CRASH! 'current' was just freed.
}

The moment you call free(current), the memory current points to becomes invalid. Attempting to access current->next is undefined behavior and will almost certainly lead to a program crash.

The correct approach requires a temporary pointer to "save" the location of the next node before you free the current one.

The safe deallocation algorithm builds on this traversal pattern:

1. Initialize a current pointer to the head of the list.
2. Loop as long as current is not NULL.
3. Inside the loop:
   a. Create a next_node pointer and store the address from current->next.
   b. Now that you have a safe reference to the rest of the list, you can free the current node: free(current).
   c. Advance to the next node for the next iteration: current = next_node.

The following resource provides an excellent walkthrough of this exact logic, complete with code and diagrams.

An Elegant Alternative with Double Pointers

In our previous lesson, we saw how using a double pointer (struct Node**) could create more robust functions for modifying the list. We can apply the same principle to our deallocation function for a very clean and powerful implementation.

Consider this function signature: void destroy_list(struct Node** head_ref). By taking a pointer to the head pointer, we can not only free every node but also set the original head pointer in the calling function back to NULL. This is excellent practice, as it leaves the list in a valid, defined "empty" state, preventing any future use of a dangling pointer.

Here is how such a function works:

void destroy_list(struct Node** head_ref) {
    while (*head_ref != NULL) {
        // 1. Save the current head node in a temporary pointer.
        struct Node* temp = *head_ref;

        // 2. Advance the original head pointer to the next node.
        *head_ref = (*head_ref)->next;

        // 3. Free the saved (old) head node.
        free(temp);
    }
}

// In main:
// destroy_list(&inventory_head);
// After this call, inventory_head is now NULL.

This approach iteratively "chops" the node off the front of the list, advances the real head pointer, and frees the chopped node. It continues until the head pointer itself becomes NULL. This is a concise and common C idiom. You can see a similar implementation in the following Stack Overflow answer, labeled as a clear function.

Verification with Valgrind

How can you be certain your destroy_list function worked correctly and didn't miss any nodes? As we learned in Module 7, the Valgrind memory debugger is the definitive tool for this. By running your program under valgrind, you can get a detailed report on heap usage. A clean run will show that all allocated blocks were eventually freed.

# Compile with debug symbols
gcc -g -Wall your_program.c -o your_program




# Run with Valgrind's memory checker
valgrind --leak-check=full ./your_program

If the "HEAP SUMMARY" reports that all heap blocks were freed -- no leaks are possible, you have succeeded. This practice of verifying your memory management is a professional discipline that separates reliable C code from brittle, unpredictable code.

Conclusion

You have now covered the complete lifecycle of a fundamental dynamic data structure. You can create nodes, insert them, search for them, delete them, and, as of today, safely dismantle an entire list, ensuring you return all borrowed memory to the system.

Key Takeaways:

• Failing to free every node in a linked list causes a memory leak, which is catastrophic for long-running programs.
• The safe deallocation algorithm requires a temporary pointer to store the address of the next node before freeing the current node.
• A more elegant implementation uses a double pointer (struct Node**) to not only free each node but also to set the original head pointer back to NULL, leaving the list in a valid empty state.
• Valgrind is the essential tool for verifying that your deallocation logic is correct and that no memory has been leaked.

With these skills in hand, you are fully prepared for our next lesson. We will refactor the dynamic array-based inventory from our game project into a more flexible linked list, applying everything we've learned about insertion, deletion, and destruction.