Structs & Data Structures · intermediate · ~15 min

Linked lists

Build and walk a singly-linked list.

Overview

A linked list is a chain of nodes, each holding a value and a pointer to the next node. Compared with an array, a linked list trades random access (slow — O(n) by index) for cheap insertion and deletion anywhere (O(1) given a pointer).

Why it matters

Linked lists are the gateway data structure — they're the simplest non-trivial use of pointers and heap allocation. Mastering insert / delete / traverse teaches the pointer-to-pointer technique that underpins every more advanced structure (trees, hash chains, B-trees).

Core concepts

Node. struct node { int v; struct node *next; };. Head. A pointer to the first node; NULL means empty list. Traversal. for (node *n = head; n; n = n->next). Insertion. Update neighbouring next pointers. Pointer-to-pointer. node **cur lets you uniformly handle 'first node' and 'middle node' cases without an if-statement special case.

Syntax notes

typedef struct node { int v; struct node *next; } node_t;
node_t *head = NULL;
/* prepend */
node_t *n = malloc(sizeof *n);
n->v = 42; n->next = head; head = n;
/* traverse */
for (node_t *p = head; p; p = p->next) printf("%d ", p->v);

Lesson

A linked list is a chain of nodes, each holding a value and a pointer to the next node. The list ends when the next pointer is NULL.

Linked lists let you insert anywhere in O(1) (given a pointer to the previous node), but indexing is O(n). They're educational; in practice arrays/vectors are usually faster due to cache locality.

Code examples

typedef struct node {
    int v;
    struct node *next;
} node_t;

node_t *push_front(node_t *head, int v) {
    node_t *n = malloc(sizeof *n);
    n->v = v; n->next = head;
    return n;
}

Common mistakes

  • Forgetting to update the head when inserting at the front — return the new head, or pass a node_t **.
  • Leaking the list — write a free_list helper that walks and frees each node.

Debugging tips

If a traversal loops forever, you've accidentally created a cycle — check that the last node's next is NULL. If a delete corrupts the list, you probably forgot to fix the predecessor's next. Use valgrind to catch leaks (every node must eventually be freed).

Memory safety

Every malloc'd node must eventually be freed. The classic 'destroy whole list' loop: walk, save next, free current, advance. Setting freed pointers to NULL prevents dangling-pointer use-after-free in surrounding code.

Real-world uses

LRU caches, scheduler queues, undo histories, hash-table chains, dynamic memory free-lists, the Linux kernel's many circular doubly-linked lists.

Practice tasks

  1. Implement insert-at-head and traverse. 2. Implement remove-by-index using pointer-to-pointer. 3. Implement reverse-in-place. 4. Implement length, then a destroy function that frees all nodes.

Summary

A linked list is nodes + next pointers + a head. Master traversal, insertion, deletion (especially via pointer-to-pointer), and the destroy loop, and you have the foundation for every more advanced linked structure.

Practice with these exercises