Skip to content

Part 3 · Lesson 20

Linked Lists

On this page

What you'll learn: building a singly linked list with malloc: nodes, the head pointer, inserting, printing and freeing.

Before you start: Lessons 12 and 13.

So far, our primary way of storing a collection of items has been the ARRAY. Arrays are great, but they have one major limitation: they have a fixed size. If you declare int my_array[100];, you can't store 101 items without creating a new, larger array and copying everything over.

Welcome to the LINKED LIST, a data structure that solves this problem.

What Is a Linked List?

A LINKED LIST is a sequence of data elements, which are connected together via links. Each element, called a NODE, contains two things:

  1. The DATA itself (e.g., a number, a struct, etc.).
  2. A POINTER to the next node in the sequence.

Think of it like a train. Each Node is a train car. It holds some cargo (the data) and has a coupling that connects it to the next car (the next pointer). All we need to know to find the entire train is where the first car is. This first-car pointer is called the HEAD.

To add a node at the front, insert_at_beginning takes a pointer to the head pointer (Node **), so it can modify the head pointer in main.

Full Source

20_linked_lists.c 200 lines Download View on GitHub
/**
 * @file 20_linked_lists.c
 * @brief Part 3, Lesson 20: Linked Lists
 * @author dunamismax
 * @date 06-15-2025
 *
 * This file serves as the lesson and demonstration for a singly linked list.
 * It shows how to build one of the most fundamental dynamic data structures
 * from scratch using structs, pointers, and dynamic memory allocation.
 */

/*
 * =====================================================================================
 * |                                   - LESSON START -                                  |
 * =====================================================================================
 *
 * So far, our primary way of storing a collection of items has been the ARRAY.
 * Arrays are great, but they have one major limitation: they have a fixed size.
 * If you declare `int my_array[100];`, you can't store 101 items without
 * creating a new, larger array and copying everything over.
 *
 * Welcome to the LINKED LIST, a data structure that solves this problem.
 *
 * WHAT IS A LINKED LIST?
 * A LINKED LIST is a sequence of data elements, which are connected together via
 * links. Each element, called a NODE, contains two things:
 * 1. The DATA itself (e.g., a number, a struct, etc.).
 * 2. A POINTER to the next node in the sequence.
 *
 * Think of it like a train. Each `Node` is a train car. It holds some cargo (the
 * data) and has a coupling that connects it to the next car (the `next` pointer).
 * All we need to know to find the entire train is where the first car is. This
 * first-car pointer is called the HEAD.
 */

#include <stdio.h>
#include <stdlib.h> // For malloc() and free()

// --- Part 1: The Building Block - The Node ---

// This is the blueprint for a single "car" in our train.
// It's a SELF-REFERENTIAL struct because it contains a pointer to another
// struct of its own type (`struct Node`).
typedef struct Node
{
    int data;          // The data this node holds
    struct Node *next; // A pointer to the next node in the list
} Node;

// --- Function Prototypes (Lesson 7) ---
// Declaring the functions up front gives a summary of the file. Their
// definitions, with the explanations, follow below.
Node *create_node(int data);
void insert_at_beginning(Node **head_ref, int data);
void print_list(Node *head);
void free_list(Node **head_ref);

// --- Part 2: Core List Operations ---
// We will write functions to handle the list's main operations.

/**
 * @brief Creates a new node, allocates memory for it, and initializes its fields.
 * @param data The integer data to store in the new node.
 * @return A pointer to the newly created node.
 */
Node *create_node(int data)
{
    // Allocate memory for one Node on the HEAP.
    Node *new_node = (Node *)malloc(sizeof(Node));
    if (new_node == NULL)
    {
        fprintf(stderr, "Error: Memory allocation failed!\n");
        exit(1);
    }
    new_node->data = data; // Set the data.
    new_node->next = NULL; // The new node doesn't point to anything yet.
    return new_node;
}

/**
 * @brief Inserts a new node at the beginning of the list.
 * @param head_ref A pointer to the head pointer. We need this double pointer
 *                 so we can modify the `head` pointer in the main function.
 * @param data The data for the new node.
 */
void insert_at_beginning(Node **head_ref, int data)
{
    // 1. Create the new node.
    Node *new_node = create_node(data);

    // 2. Point the new node's `next` to what `head` is currently pointing to.
    new_node->next = *head_ref;

    // 3. Update `head` to point to our new node, making it the new first node.
    *head_ref = new_node;
}

/**
 * @brief Prints all the elements of the list from beginning to end.
 * @param head A pointer to the first node of the list.
 */
void print_list(Node *head)
{
    Node *current = head; // Start at the beginning.

    while (current != NULL)
    {
        printf("%d -> ", current->data);
        current = current->next; // Move to the next node.
    }
    printf("NULL\n"); // The end of the list points to nothing.
}

/**
 * @brief Frees all memory allocated for the list to prevent memory leaks.
 * @param head_ref A pointer to the head pointer.
 */
void free_list(Node **head_ref)
{
    Node *current = *head_ref;
    Node *temp;

    while (current != NULL)
    {
        temp = current;          // Save the current node.
        current = current->next; // Move to the next one.
        free(temp);              // Free the saved node.
    }

    // Finally, set the original head pointer in main() to NULL.
    *head_ref = NULL;
}

int main(void)
{
    // The HEAD pointer. This is our only entry point into the list.
    // An empty list is represented by a NULL head pointer.
    Node *head = NULL;

    printf("Building the linked list by inserting at the beginning...\n");

    // Insert elements. Since we insert at the beginning, the last one
    // we insert will be the first one in the list.
    insert_at_beginning(&head, 30);
    insert_at_beginning(&head, 20);
    insert_at_beginning(&head, 10);

    printf("The current list is:\n");
    print_list(head);
    printf("\n");

    printf("Adding another element, 5...\n");
    insert_at_beginning(&head, 5);

    printf("The final list is:\n");
    print_list(head);
    printf("\n");

    // CRITICAL STEP: Always clean up memory when you're done.
    printf("Freeing all nodes in the list...\n");
    free_list(&head);

    printf("List after freeing:\n");
    print_list(head); // Should print "NULL"

    return 0;
}

/*
 * =====================================================================================
 * |                                    - LESSON END -                                   |
 * =====================================================================================
 *
 * Key Takeaways:
 *
 * 1.  A LINKED LIST is a dynamic data structure made of NODES linked by pointers.
 * 2.  A NODE contains DATA and a POINTER to the next node.
 * 3.  The HEAD pointer is the entry point to the entire list. If `head` is `NULL`,
 *     the list is empty.
 * 4.  Nodes are created on the HEAP using `malloc()`, which gives us the flexibility
 *     to grow or shrink the list at runtime.
 * 5.  Because we use `malloc()`, we are responsible for using `free()` on every
 *     single node to prevent memory leaks.
 * 6.  To modify the head pointer from within a function, we must pass its
 *     address (a pointer to a pointer, or `Node **`).
 *
 * You have just built one of the most fundamental data structures in all of
 * computer science. Understanding linked lists is key to tackling more complex
 * structures like trees, graphs, and hash tables.
 *
 * HOW TO COMPILE AND RUN THIS CODE:
 *
 * 1. Open a terminal or command prompt.
 * 2. Navigate to the directory where you saved this file.
 * 3. Use the GCC compiler to create an executable file:
 *    `gcc -Wall -Wextra -std=c17 -o 20_linked_lists 20_linked_lists.c`
 * 4. Run the executable:
 *    - On Linux/macOS:   `./20_linked_lists`
 *    - On Windows (WSL): `./20_linked_lists`
 */

How to Compile and Run

Runs the lesson in Compiler Explorer (GCC 16.2), nothing to install.

Once, before your first lesson

Install Apple's command line tools. They include the cc compiler: xcode-select --install

New to the terminal? The setup guide walks through it.

Build

$ cc -Wall -Wextra -std=c17 -o 20_linked_lists 20_linked_lists.c

Run

$ ./20_linked_lists

Try It Yourself

Practise what this lesson taught. Change a copy of the lesson file, or start a new one.

  1. Write int list_length(const Node *head).
  2. Write void insert_at_end(Node **head, int data).
  3. Write a function that deletes the first node holding a given value, and free it.

Finished this lesson?

Mark it complete to track your progress through the course.

Search the course

Type at least two letters. Press / anywhere to search.

↑ ↓ to choose, Enter to open. On a lesson, j and k go to the next and previous lesson.