Scrolls
5 min read
On this page

Linked Lists

A linked list is a sequence of nodes where each node contains data and a pointer to the next node. Unlike arrays, linked lists do not require contiguous memory. You can insert and remove elements without shifting other elements. However, the per-node allocation overhead and poor cache performance make linked lists slower than arrays in most practical scenarios. Understanding linked lists is essential because they appear in kernels, libraries, and interview questions, but knowing when not to use them is equally important.

Singly Linked List

The simplest linked list: each node points to the next, and the last node points to NULL.

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

struct Node {
    int data;
    struct Node *next;
};

struct Node *create_node(int value) {
    struct Node *node = malloc(sizeof(struct Node));
    if (node == NULL) {
        return NULL;
    }
    node->data = value;
    node->next = NULL;
    return node;
}

Insert at Head

Inserting at the head is O(1) because you only update one pointer.

void push_front(struct Node **head, int value) {
    struct Node *new_node = create_node(value);
    if (new_node == NULL) return;
    new_node->next = *head;
    *head = new_node;
}

The double pointer (**head) is necessary because inserting at the head changes the head pointer itself. If you pass a single pointer, the change would be local to the function.

Insert at Tail

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

    if (*head == NULL) {
        *head = new_node;
        return;
    }

    struct Node *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = new_node;
}

This is O(n) because you traverse the entire list. Maintaining a tail pointer makes it O(1).

struct Node *find(struct Node *head, int value) {
    struct Node *current = head;
    while (current != NULL) {
        if (current->data == value) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

Search is always O(n). There is no way to jump to the middle of a linked list.

Delete a Node

void delete_node(struct Node **head, int value) {
    struct Node *current = *head;
    struct Node *prev = NULL;

    while (current != NULL) {
        if (current->data == value) {
            if (prev == NULL) {
                *head = current->next;
            } else {
                prev->next = current->next;
            }
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

Reverse a List

Reversing a singly linked list in place is a classic exercise that tests pointer manipulation.

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

    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *head = prev;
}

Three pointers track the previous, current, and next nodes. Each iteration reverses one link. After the loop, prev points to the new head.

Print & Free

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

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

Always save current->next before freeing current. Accessing a freed node is undefined behavior.

Complete Example

int main(void) {
    struct Node *list = NULL;

    push_front(&list, 30);
    push_front(&list, 20);
    push_front(&list, 10);
    push_back(&list, 40);

    print_list(list);

    delete_node(&list, 20);
    print_list(list);

    reverse(&list);
    print_list(list);

    free_list(list);
    return 0;
}

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

Doubly Linked List

A doubly linked list adds a prev pointer, enabling traversal in both directions and O(1) deletion when you have a pointer to the node.

struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
};

void insert_after(struct DNode *node, int value) {
    struct DNode *new_node = malloc(sizeof(struct DNode));
    if (new_node == NULL) return;

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

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

void remove_node(struct DNode **head, struct DNode *node) {
    if (node->prev != NULL) {
        node->prev->next = node->next;
    } else {
        *head = node->next;
    }
    if (node->next != NULL) {
        node->next->prev = node->prev;
    }
    free(node);
}

With a prev pointer, deletion no longer requires scanning for the predecessor. This makes doubly linked lists better for LRU caches and other structures where you frequently remove specific nodes.

Circular Lists

In a circular list, the last node points back to the first node instead of NULL. This is useful for round-robin scheduling and ring buffers.

void print_circular(struct Node *head) {
    if (head == NULL) return;

    struct Node *current = head;
    do {
        printf("%d -> ", current->data);
        current = current->next;
    } while (current != head);
    printf("(back to head)\n");
}

The termination condition changes from current != NULL to current != head. Forgetting this change creates an infinite loop.

The malloc-per-Node Cost

Every malloc call has overhead: memory allocator bookkeeping, potential system calls, and fragmentation. A linked list of 1 million integers allocates 1 million small chunks of memory scattered across the heap.

/* Linked list: 1M mallocs, poor cache locality */
struct Node *head = NULL;
for (int i = 0; i < 1000000; i++) {
    push_front(&head, i);
}

/* Array: 1 malloc, excellent cache locality */
int *arr = malloc(1000000 * sizeof(int));
for (int i = 0; i < 1000000; i++) {
    arr[i] = i;
}

The array version is typically 10-50x faster for iteration because the data is contiguous in memory and the CPU prefetcher loads subsequent cache lines automatically. Each linked list node may be in a different cache line, causing a cache miss per access.

When to Use Linked Lists

Linked lists are the right choice when:

  • You need O(1) insertion and deletion at arbitrary positions (and you already have a pointer to the node)
  • The element size is large enough that moving elements in an array is expensive
  • You are implementing a kernel data structure where allocation constraints apply

In practice, arrays (or dynamic arrays like C++'s vector) outperform linked lists for almost every workload due to cache effects. Measure before choosing a linked list.

Intrusive Lists: The Linux Kernel Pattern

The Linux kernel uses intrusive linked lists. Instead of the list node containing the data, the data structure contains the list node.

/* Non-intrusive: the list owns the data */
struct Node {
    void *data;
    struct Node *next;
};

/* Intrusive: the data owns the list node */
struct list_head {
    struct list_head *next;
    struct list_head *prev;
};

struct Task {
    int pid;
    char name[64];
    struct list_head list; /* Embedded list node */
};

The container_of macro recovers the containing structure from a pointer to the embedded list_head:

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

/* Given a list_head pointer, get the Task */
struct Task *task = container_of(list_ptr, struct Task, list);

Intrusive lists have zero allocation overhead (no separate node allocation), work with any data type, and allow a structure to be on multiple lists simultaneously. This pattern is used throughout the Linux kernel for process lists, file system structures, and device driver queues.

Common Pitfalls

  • Forgetting to free nodes — Every malloc needs a corresponding free. Use a free_list function that traverses and frees every node.
  • Use-after-free during deletion — Saving current->next after freeing current reads freed memory. Always save the next pointer before calling free.
  • Not handling the empty list — Functions that operate on linked lists must handle head == NULL. Dereferencing a NULL head pointer crashes.
  • Single pointer instead of double pointer — Functions that modify the head of the list need struct Node **head. A single pointer cannot change the caller's head variable.
  • Using linked lists when arrays are better — For sequential access, searching, and sorting, arrays are almost always faster. Use linked lists only when you have measured that the insertion/deletion pattern benefits from them.
  • Infinite loops in circular lists — The termination condition for circular lists is current != head, not current != NULL. Mixing these up causes an infinite loop.

Key Takeaways

  • A singly linked list stores data and a next pointer per node. Insert at head is O(1). Search, insert at tail, and delete are O(n).
  • A doubly linked list adds a prev pointer, enabling O(1) deletion when you have a pointer to the node.
  • Reversing a linked list requires three pointers: prev, current, and next. It is the most common linked list interview question.
  • Linked lists have poor cache performance because each node is allocated separately. Arrays are 10-50x faster for iteration.
  • Use linked lists when you need O(1) insertion/deletion at known positions. Use arrays for almost everything else.
  • The Linux kernel uses intrusive lists with container_of to avoid per-node allocation and support multiple simultaneous list memberships.