Linked Lists with Structs

A linked list is the canonical example of a self-referential data structure in C. Each node contains a data payload and a pointer to the next node. Because a struct cannot contain an instance of itself (that would be infinite size), the link field must be a pointer: `struct Node *next`. The list ends when a node's `next` pointer is `NULL`. Linked lists allow O(1) insertion at the head and avoid the need for contiguous memory, but they offer O(n) access by index and have poor cache locality. Building a linked list requires dynamic memory allocation for each node. Traversal follows the `next` pointers until `NULL` is reached. Insertion at the head is trivial: allocate a node, set its `next` to the current head, then update the head pointer. Insertion in the middle or at the tail requires traversing to the correct position. Deletion must update the predecessor's `next` pointer and then free the removed node. Freeing a linked list must be done node by node. You cannot simply free the head pointer — that would leak all the other nodes. The standard pattern is to walk the list with a temporary `next` pointer: save `current->next` before freeing `current`, then move to the saved pointer. Failing to free each node individually is a classic C memory leak.

Example

#include <stdio.h>
#include <stdlib.h>

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

Node *push_front(Node *head, int val)
{
    Node *n = malloc(sizeof(Node));
    if (!n) { perror("malloc"); exit(EXIT_FAILURE); }
    n->value = val;
    n->next  = head;
    return n;
}

void print_list(const Node *head)
{
    for (const Node *p = head; p; p = p->next)
        printf("%d -> ", p->value);
    printf("NULL\n");
}

Node *remove_value(Node *head, int val)
{
    Node dummy = {0, head};
    Node *prev = &dummy;
    while (prev->next) {
        if (prev->next->value == val) {
            Node *del = prev->next;
            prev->next = del->next;
            free(del);
            break;
        }
        prev = prev->next;
    }
    return dummy.next;
}

void free_list(Node *head)
{
    while (head) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main(void)
{
    Node *list = NULL;
    for (int i = 5; i >= 1; i--)
        list = push_front(list, i);

    printf("Initial:  "); print_list(list);

    list = remove_value(list, 3);
    printf("Remove 3: "); print_list(list);

    free_list(list);
    printf("List freed — no memory leaks\n");
    return 0;
}

HTML

Full Editor

Related Resources

C Reference

Complete tag & property list

C How-To Guides

Step-by-step practical guides

C Exercises

Practice what you've learned