Linked Lists

A linked list stores items in separate nodes, each pointing to the next. Unlike an array, it can grow one node at a time and insert or remove items in the middle without shifting everything else. Building one brings together structs, pointers and dynamic memory — a classic C exercise.

The node

TXT

 head
  │
  ▼
┌────┬───┐    ┌────┬───┐    ┌────┬──────┐
│ 10 │ ●─┼──▶ │ 20 │ ●─┼──▶ │ 30 │ NULL │
└────┴───┘    └────┴───┘    └────┴──────┘

Each node holds a value and a pointer to the next node; the last node's pointer is NULL. The list itself is just a pointer to the first node, the head.

A complete singly linked list

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

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

// Add to the front: O(1). Takes Node** because it changes the caller's head.
bool push_front(Node **head, int value) {
    Node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->value = value;
    n->next = *head;
    *head = n;
    return true;
}

// Add to the end: walks the list, O(n).
bool push_back(Node **head, int value) {
    Node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->value = value;
    n->next = NULL;
    Node **link = head;
    while (*link != NULL) link = &(*link)->next;
    *link = n;
    return true;
}

// Remove the first node with this value.
bool remove_value(Node **head, int value) {
    for (Node **link = head; *link != NULL; link = &(*link)->next) {
        if ((*link)->value == value) {
            Node *doomed = *link;
            *link = doomed->next;
            free(doomed);
            return true;
        }
    }
    return false;
}

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

void free_list(Node **head) {
    Node *n = *head;
    while (n != NULL) {
        Node *next = n->next;    // save before freeing
        free(n);
        n = next;
    }
    *head = NULL;
}

int main(void) {
    Node *list = NULL;
    push_back(&list, 20);
    push_back(&list, 30);
    push_front(&list, 10);
    print_list(list);

    remove_value(&list, 20);
    print_list(list);
    remove_value(&list, 10);
    print_list(list);

    free_list(&list);
    print_list(list);
    return 0;
}

Output

10 -> 20 -> 30 -> NULL
10 -> 30 -> NULL
30 -> NULL
NULL

Points worth studying

Node **head. Adding to the front changes which node is first, so the function needs the address of the caller's head pointer to update it.
The pointer-to-link trick. push_back and remove_value walk a Node **link that points at "the pointer that leads to the current node". Updating *link works the same whether that pointer is the head or some node's next, so there's no special case for the first node.
Freeing safely. Read n->next before freeing n — afterwards it's a use after free.

Reversing a list

A favourite interview question: reverse the links in place with three pointers.

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

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

Node *reverse(Node *head) {
    Node *prev = NULL;
    while (head != NULL) {
        Node *next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

int main(void) {
    Node nodes[4];
    for (int i = 0; i < 4; i++) {
        nodes[i].value = i + 1;
        nodes[i].next = i < 3 ? &nodes[i + 1] : NULL;
    }
    for (Node *n = reverse(&nodes[0]); n != NULL; n = n->next) printf("%d ", n->value);
    printf("\n");
    return 0;
}

Output

4 3 2 1

(Nodes don't have to come from malloc — here they live in an array, which is fine for a quick test.)

Lists vs. arrays

Operation	Dynamic array	Linked list
Access element i	Instant (O(1))	Walk i nodes (O(n))
Add at the end	Usually instant	O(1) with a tail pointer, else O(n)
Insert/remove in the middle (position known)	Shift elements (O(n))	Relink (O(1))
Memory	One compact block, cache-friendly	A separate allocation and a pointer per item

On modern hardware, dynamic arrays are faster for most tasks because their memory is contiguous. Linked lists still shine for queues, when nodes are frequently moved between lists, and as building blocks for structures like hash table chains. Doubly linked lists add a prev pointer so you can walk both ways and remove a node knowing only its address.

Try it yourself

Add a function that inserts a value into an already sorted list, keeping it sorted.

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

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

int insert_sorted(Node **head, int value) {
    Node *n = malloc(sizeof *n);
    if (n == NULL) return 0;
    n->value = value;
    Node **link = head;
    while (*link != NULL && (*link)->value < value) link = &(*link)->next;
    n->next = *link;
    *link = n;
    return 1;
}

int main(void) {
    Node *list = NULL;
    int values[] = { 42, 7, 19, 3, 25 };
    for (int i = 0; i < 5; i++) insert_sorted(&list, values[i]);
    for (Node *n = list; n != NULL; n = n->next) printf("%d ", n->value);
    printf("\n");
    while (list != NULL) {
        Node *next = list->next;
        free(list);
        list = next;
    }
    return 0;
}

Edit the code, copy it into main.c, then compile and run it with cc -std=c17 -Wall main.c -o main && ./main. How to set up a C compiler

Output

3 7 19 25 42

Previoustypedef NextSorting and Searching