Linked Lists in C

Arrays are like assigned seats at a movie theater. Everyone sits in a row, numbered positions, fixed size. Want to add someone in the middle? Everyone has to scoot over.

Linked lists are different. They’re like a treasure hunt. Each clue tells you where to find the next one. You can add or remove clues anywhere without moving everything else.

This is your first real data structure - a way of organizing data that makes certain operations easier.

What’s a Linked List?

A linked list is a chain of nodes. Each node holds:

Some data (a value)
A pointer to the next node

Here’s a linked list with three nodes containing values 1, 2, and 3. Each node points to the next with an arrow, and the final node points to NULL to mark the end of the list.

+-------+     +-------+     +-------+
|   1   | --> |   2   | --> |   3   | --> NULL
+-------+     +-------+     +-------+

The last node points to NULL - that’s how you know the chain ends.

Think of it like a conga line. Each person knows who’s in front of them. If someone leaves, the person behind just grabs onto whoever’s now in front. No need to shuffle everyone around.

The Node Structure

typedef struct Node {
    int value;
    struct Node *next;  // Pointer to another Node
} Node;

Why struct Node inside the definition? Because we’re referring to the type before we’ve finished defining it. C needs the full name struct Node here; the shortcut Node isn’t available yet.

Creating Nodes

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

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

Node *create_node(int value) {
    Node *n = malloc(sizeof(Node));
    if (n != NULL) {
        n->value = value;
        n->next = NULL;
    }
    return n;
}

Each new node starts with next set to NULL. It’s not connected to anything yet.

Building a List by Hand

int main(void) {
    // Create three nodes
    Node *first = create_node(1);
    Node *second = create_node(2);
    Node *third = create_node(3);

    // Link them together
    first->next = second;
    second->next = third;
    // third->next is already NULL

    // Now we have: 1 -> 2 -> 3 -> NULL
    return 0;
}

We only need to keep track of the first node (called the head). From there, we can follow the next pointers to reach any node.

Walking Through a List

To visit every node, start at the head and follow the arrows:

void print_list(Node *head) {
    Node *current = head;
    while (current != NULL) {
        printf("%d -> ", current->value);
        current = current->next;
    }
    printf("NULL\n");
}

It’s like following a trail of breadcrumbs. Keep going until you hit NULL.

Adding to the Beginning (Prepend)

Adding at the front is fast - just one operation:

Node *prepend(Node *head, int value) {
    Node *new_node = create_node(value);
    if (new_node != NULL) {
        new_node->next = head;  // New node points to old head
    }
    return new_node;  // New node is the new head
}

The diagram shows what happens when you prepend value 0 to a list containing 1 and 2. The new node becomes the head, and points to the old head.

Before: head -> [1] -> [2] -> NULL

After prepend(head, 0):
        head -> [0] -> [1] -> [2] -> NULL

It’s like cutting in line at the front. You just step in and point to whoever was first.

Adding to the End (Append)

Adding at the end requires walking to the last node first:

void append(Node **head, int value) {
    Node *new_node = create_node(value);
    if (new_node == NULL) return;

    // Empty list? New node becomes head
    if (*head == NULL) {
        *head = new_node;
        return;
    }

    // Find the last node
    Node *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }

    // Link it
    current->next = new_node;
}

Why Node **head (pointer to pointer)? Because if the list is empty, we need to change what head points to. With just Node *head, we’d only change a local copy.

Think of it like this: if someone wants to tell you a new meeting location (change where head points), they need your phone number (pointer to head), not just the old meeting location (copy of head).

Inserting in the Middle

To insert after a specific node:

void insert_after(Node *node, int value) {
    if (node == NULL) return;

    Node *new_node = create_node(value);
    if (new_node == NULL) return;

    new_node->next = node->next;  // New points to what was after node
    node->next = new_node;        // Node now points to new
}

When inserting value 2 after node 1, the new node 2 is created and placed between nodes 1 and 3 by updating the pointers.

Before: [1] -> [3] -> NULL

insert_after(first, 2):

After:  [1] -> [2] -> [3] -> NULL

No shifting required! Just update two pointers.

Finding a Node

Search by walking through and checking each value:

Node *find(Node *head, int value) {
    Node *current = head;
    while (current != NULL) {
        if (current->value == value) {
            return current;  // Found it!
        }
        current = current->next;
    }
    return NULL;  // Not found
}

Deleting a Node

Deleting is trickier. You need to update the previous node’s next pointer:

void delete_value(Node **head, int value) {
    if (*head == NULL) return;

    // Special case: deleting the head
    if ((*head)->value == value) {
        Node *temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }

    // Find the node BEFORE the one we want to delete
    Node *current = *head;
    while (current->next != NULL && current->next->value != value) {
        current = current->next;
    }

    // Found it?
    if (current->next != NULL) {
        Node *temp = current->next;
        current->next = temp->next;  // Skip over the deleted node
        free(temp);
    }
}

When deleting value 2, node 1’s pointer is changed to skip over node 2 and point directly to node 3. The memory for node 2 is then freed.

Before: [1] -> [2] -> [3] -> NULL

delete_value(2):

After:  [1] --------> [3] -> NULL
        (2 is freed)

It’s like removing someone from a conga line. The person behind just grabs onto whoever’s now in front.

Freeing the Whole List

When you’re done, free every node:

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

Important: Save the next pointer before freeing! Once you free a node, you can’t read its next field anymore.

// WRONG - accessing freed memory!
while (head != NULL) {
    free(head);
    head = head->next;  // head was just freed!
}

// RIGHT - save next first
while (head != NULL) {
    Node *temp = head;
    head = head->next;  // Save this before freeing
    free(temp);
}

Counting Nodes

int count_nodes(Node *head) {
    int count = 0;
    Node *current = head;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

Reversing a List

This is a classic interview question. We need to flip all the arrows:

Node *reverse(Node *head) {
    Node *prev = NULL;
    Node *current = head;

    while (current != NULL) {
        Node *next = current->next;  // Save next
        current->next = prev;        // Flip the arrow
        prev = current;              // Move prev forward
        current = next;              // Move current forward
    }

    return prev;  // New head
}

Reversing a list flips all the arrows. The node that was last becomes the new head, and the node that was first now points to NULL.

Before: [1] -> [2] -> [3] -> NULL

After:  NULL <- [1] <- [2] <- [3]

        [3] -> [2] -> [1] -> NULL

It’s like everyone in the conga line doing an about-face.

Doubly Linked Lists

So far we’ve built a singly linked list - you can only go forward. A doubly linked list has arrows in both directions:

typedef struct DNode {
    int value;
    struct DNode *next;
    struct DNode *prev;
} DNode;

In a doubly linked list, each node has pointers going both forward (next) and backward (prev). The first node’s prev pointer is NULL, and the last node’s next pointer is NULL.

NULL <- [1] <-> [2] <-> [3] -> NULL

Benefits:

Can traverse backwards
Easier to delete (don’t need to find previous node)

Cost:

Uses more memory (extra pointer per node)
More pointers to maintain

void dlist_insert_after(DNode *node, int value) {
    if (node == NULL) return;

    DNode *new_node = malloc(sizeof(DNode));
    if (new_node == NULL) return;

    new_node->value = value;
    new_node->next = node->next;
    new_node->prev = node;

    if (node->next != NULL) {
        node->next->prev = new_node;
    }
    node->next = new_node;
}

Complete Example: To-Do List

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

typedef struct Task {
    char description[100];
    int done;
    struct Task *next;
} Task;

Task *create_task(const char *desc) {
    Task *t = malloc(sizeof(Task));
    if (t != NULL) {
        strncpy(t->description, desc, 99);
        t->description[99] = '\0';
        t->done = 0;
        t->next = NULL;
    }
    return t;
}

void add_task(Task **head, const char *desc) {
    Task *new_task = create_task(desc);
    if (new_task == NULL) return;

    if (*head == NULL) {
        *head = new_task;
    } else {
        Task *current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = new_task;
    }
}

void print_tasks(Task *head) {
    printf("\n=== TO-DO LIST ===\n");
    int num = 1;
    Task *current = head;
    while (current != NULL) {
        printf("%d. [%c] %s\n", num,
               current->done ? 'X' : ' ',
               current->description);
        num++;
        current = current->next;
    }
    if (head == NULL) {
        printf("No tasks! Time to relax.\n");
    }
}

void mark_done(Task *head, int number) {
    Task *current = head;
    int count = 1;
    while (current != NULL && count < number) {
        current = current->next;
        count++;
    }
    if (current != NULL) {
        current->done = 1;
        printf("Marked '%s' as done!\n", current->description);
    }
}

void free_tasks(Task *head) {
    while (head != NULL) {
        Task *temp = head;
        head = head->next;
        free(temp);
    }
}

int main(void) {
    Task *todo = NULL;

    add_task(&todo, "Save the world");
    add_task(&todo, "Do laundry");
    add_task(&todo, "Learn C programming");
    add_task(&todo, "Build a linked list");

    print_tasks(todo);

    mark_done(todo, 4);  // Build a linked list - done!
    mark_done(todo, 3);  // Learn C programming - done!

    print_tasks(todo);

    free_tasks(todo);
    return 0;
}

Arrays vs Linked Lists

Operation	Array	Linked List
Access by index	Fast (instant)	Slow (must walk)
Insert at beginning	Slow (shift all)	Fast (change 1 pointer)
Insert at end	Fast (if room)	Slow (must walk to end)
Insert in middle	Slow (shift half)	Fast (change 2 pointers)
Delete	Slow (shift)	Fast (change pointers)
Memory	Contiguous block	Scattered nodes

Use arrays when you need fast access by position. Use linked lists when you’re doing lots of inserting and deleting.

Try It Yourself

Write a function that finds the middle node of a linked list
Write a function that checks if a linked list has a cycle (last node points to an earlier node instead of NULL)
Implement a doubly linked list with insert and delete operations
Merge two sorted linked lists into one sorted list

Common Mistakes

Forgetting to handle the empty list case
Losing the head pointer (memory leak of entire list)
Forgetting to free nodes when deleting
Accessing node->next when node might be NULL

Next Up

In Part 17, we’ll learn about stacks and queues - two data structures built on linked lists that are used everywhere in computing.

Enjoyed This?

If this helped something click, subscribe to my YouTube channel. More content like this, same approach - making things stick without insulting your intelligence. It’s free, it helps more people find this stuff, and it tells me what’s worth making more of.