Structs & Data Structures · intermediate · ~15 min
- Define a self-referential `struct` node that stores a value and a pointer to the next node - Build a singly-linked list on the heap and traverse it from head to tail - Insert at the front, insert after a node, and delete a node without leaking or corrupting the chain - Use the **pointer-to-pointer** technique to handle the head and interior nodes with one uniform code path - Free an entire list correctly, avoiding memory leaks, use-after-free, and dangling pointers - Reason about why access is O(n) but insertion/deletion at a known position is O(1)
A linked list is a chain of small heap-allocated blocks called nodes. Each node carries a piece of data plus a pointer to the next node in the chain. Follow the pointers one at a time and you visit every element; when a pointer is NULL, you have reached the end.
Picture a scavenger hunt. Each clue tells you where the next clue is hidden. You cannot skip ahead to clue five — you must read clue one, which sends you to clue two, and so on. That is exactly how a linked list works: the only way to reach a later node is to walk through the earlier ones.
This lesson builds directly on three prerequisites. From Structs you already know how to bundle related fields into one type; a node is just a struct with an unusual twist — one of its fields points to another struct of the same type. From malloc and the heap you know how to request memory that outlives the current function; every node lives on the heap so the list can grow at runtime. From free and ownership you know that whoever allocates memory is responsible for releasing it; a linked list makes ownership concrete because you must free each node individually.
In plain terms: an array stores its elements shoulder-to-shoulder in one contiguous block, so you can jump to element 100 instantly. A linked list scatters its elements anywhere in memory and stitches them together with pointers, so jumping to element 100 means following 100 links. In exchange, you can splice a new element into the middle without shifting anything. The terminology to lock in: node (one link in the chain), head (pointer to the first node), tail (the last node, whose next is NULL), and traversal (walking the chain).
The linked list is the gateway data structure. It is the simplest structure that forces you to combine three ideas at once: structs, heap allocation, and pointers that point to other pointers. Get comfortable here and every later structure — stacks, queues, trees, hash-table chains, graphs — feels like a variation on a theme you already know.
The standout skill is the pointer-to-pointer idiom. Many list operations have an annoying special case: "what if the node I'm changing is the head?" A pointer-to-pointer erases that special case, letting one loop handle insertion or deletion anywhere. This same trick appears throughout professional C — in the Linux kernel's list macros, in memory allocators that thread free blocks together, and in any code that edits a chain in place.
Even though arrays usually win on raw speed because of cache locality, linked lists shine when you need cheap splicing, stable element addresses, or a structure whose size you cannot predict in advance. Understanding the trade-off — and being able to explain why it exists — is exactly the kind of reasoning that separates someone who memorises code from someone who designs it.
Definition. A node is a struct that stores your data plus a pointer to another node of the same type.
typedef struct node {
int v; /* the value this node holds */
struct node *next; /* pointer to the next node, or NULL at the end */
} node_t;
Why it works. The field next is a pointer, not a whole struct node. A struct cannot contain a copy of itself (that would be infinitely large), but it can hold a pointer to one, because a pointer is just an address of fixed size. Note that inside the braces you must still write struct node *next; — the node_t typedef name does not exist yet at that point.
When to use / when not. Use a node when elements are created and destroyed dynamically and you want cheap splicing. Do not reach for a linked list when you mostly index by position or iterate tight loops over millions of elements — an array's contiguous layout is dramatically faster there.
Pitfall. Writing node_t next; (a value) instead of struct node *next; (a pointer) will not compile — the type is incomplete at that line.
Knowledge check: Why can a node hold a struct node * but not a struct node?
Definition. The head is a pointer to the first node. When head == NULL, the list is empty.
head
|
v
+----+----+ +----+----+ +----+------+
| 10 | o-+--> | 20 | o-+--> | 30 | NULL |
+----+----+ +----+----+ +----+------+
first second tail
Why it works. The head is your only handle on the whole list. Lose it (overwrite it without saving the old value) and every node becomes unreachable — a guaranteed leak. That is why front-insertion functions must return the new head or take a node_t **.
Pitfall. Treating an empty list as an error. NULL is a valid, well-formed empty list; your loops should handle it naturally, not crash on it.
Definition. Traversal means visiting each node in order by repeatedly following next until you hit NULL.
for (node_t *p = head; p != NULL; p = p->next) {
printf("%d ", p->v);
}
How it works internally. p starts at the head. Each iteration reads p->v, then reassigns p = p->next, hopping to the next address. The loop stops the moment p becomes NULL, so you never dereference past the tail.
Pitfall. Accessing p->next after the loop, or forgetting the p != NULL guard, dereferences NULL and crashes.
Knowledge check (predict the output): For the list 10 -> 20 -> 30, what does the loop above print, and how many times does p = p->next execute?
Definition. Insertion adds a node by rewiring the next pointers of its neighbours.
Front insertion (prepend) is O(1) and the most common:
Before: head -> [20] -> [30] -> NULL
Step 1: new -> [5] ; set 5.next = head (points at 20)
Step 2: head = &[5]
After: head -> [5] -> [20] -> [30] -> NULL
Order matters. Set the new node's next to the current head before moving the head. Reverse the order and you lose the rest of the list.
When to use. Front insertion when order does not matter or you want newest-first (a stack). Insert-after when you already hold a pointer to the predecessor.
Pitfall. Updating head first, then setting new->next = head, which makes the node point at itself and orphans the rest of the list.
Definition. To delete a node you make its predecessor's next skip over it, then free it. A node_t ** (pointer to the next field you might change) removes the "is it the head?" special case.
node_t **pp = &head; /* points at the head pointer itself */
while (*pp && (*pp)->v != target)
pp = &(*pp)->next; /* advance to the next link slot */
if (*pp) { /* found it */
node_t *dead = *pp;
*pp = dead->next; /* unlink */
free(dead);
}
Why it works. pp always points at the pointer that leads to the current node — first the caller's head, then each node's next. Writing through *pp edits whichever pointer that is, so deleting the head and deleting an interior node use identical code.
| Aspect | Array | Linked list |
|---|---|---|
| Access element k | O(1) | O(k) |
| Insert/delete at known position | O(n) (shift) | O(1) (rewire) |
| Memory layout | contiguous | scattered |
| Cache locality | excellent | poor |
| Extra memory per element | none | one pointer |
| Grows at runtime | needs realloc | just malloc a node |
Knowledge check (find the bug): A learner writes free(dead); *pp = dead->next;. Why does reading dead->next after free(dead) invoke undefined behaviour, and how do you fix it?
/* 1. The self-referential node type */
typedef struct node {
int v;
struct node *next; /* MUST be a pointer; 'struct node', not node_t, here */
} node_t;
/* 2. An empty list is just a NULL head */
node_t *head = NULL;
/* 3. Prepend: order of the two assignments is critical */
node_t *n = malloc(sizeof *n); /* sizeof *n = sizeof(node_t), stays correct if type changes */
if (n == NULL) { /* handle allocation failure */ }
n->v = 42;
n->next = head; /* first: link new node to old list */
head = n; /* then: move head */
/* 4. Traverse */
for (node_t *p = head; p != NULL; p = p->next)
printf("%d ", p->v);
/* 5. Pointer-to-pointer walk (edits the chain in place) */
for (node_t **pp = &head; *pp != NULL; pp = &(*pp)->next) {
/* *pp is the current node; (*pp)->next is the link to the following one */
}
A linked list is a chain of nodes. Each node holds a value and a pointer to the next node. The list ends when a next pointer is NULL.
The trade-off
A note on real-world use
Linked lists are mostly educational. In practice, arrays and vectors are usually faster, because their elements sit next to each other in memory (good cache locality).
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int v;
struct node *next;
} node_t;
/* Allocate one node, or return NULL if out of memory. */
node_t *make_node(int v) {
node_t *n = malloc(sizeof *n);
if (n == NULL) return NULL;
n->v = v;
n->next = NULL;
return n;
}
/* Prepend v to the list. Returns the new head, or the old head on failure. */
node_t *push_front(node_t *head, int v) {
node_t *n = make_node(v);
if (n == NULL) return head; /* allocation failed: list unchanged */
n->next = head;
return n;
}
/* Print every value, then a newline. */
void print_list(const node_t *head) {
for (const node_t *p = head; p != NULL; p = p->next)
printf("%d -> ", p->v);
printf("NULL\n");
}
/* Delete the first node whose value == target. Returns the (maybe new) head. */
node_t *remove_value(node_t *head, int target) {
node_t **pp = &head; /* pointer to the pointer we may edit */
while (*pp != NULL && (*pp)->v != target)
pp = &(*pp)->next;
if (*pp != NULL) { /* found a match */
node_t *dead = *pp;
*pp = dead->next; /* unlink before freeing */
free(dead);
}
return head;
}
/* Free every node so nothing leaks. */
void free_list(node_t *head) {
while (head != NULL) {
node_t *next = head->next; /* save the link before freeing */
free(head);
head = next;
}
}
int main(void) {
node_t *head = NULL;
/* Build 30 -> 20 -> 10 by prepending 10, 20, 30. */
head = push_front(head, 10);
head = push_front(head, 20);
head = push_front(head, 30);
printf("start: ");
print_list(head);
head = remove_value(head, 30); /* delete the head node */
printf("del 30: ");
print_list(head);
head = remove_value(head, 10); /* delete the tail node */
printf("del 10: ");
print_list(head);
head = remove_value(head, 99); /* not present: no change */
printf("del 99: ");
print_list(head);
free_list(head); /* release everything */
head = NULL; /* avoid a dangling head */
return 0;
}
What it does. It builds a three-node list by prepending, prints it, deletes the head node (30), deletes the tail node (10), attempts to delete a value that is not present (99, a no-op), then frees the whole list.
Expected output:
start: 30 -> 20 -> 10 -> NULL
del 30: 20 -> 10 -> NULL
del 10: 20 -> NULL
del 99: 20 -> NULL
Edge cases covered: deleting the head, deleting the tail, deleting a value that does not exist, and freeing a list that still has nodes. An empty list (head == NULL) also flows through every function safely — the loops simply never execute.
make_node calls malloc(sizeof *n). Using sizeof *n (the size of what n points to) instead of sizeof(node_t) keeps the code correct even if the type name later changes. It checks for NULL, then initialises both fields so next is never garbage.push_front(head, 10) with head == NULL: a new node holding 10 gets next = NULL, and the function returns it. head now points at [10] -> NULL.push_front(head, 20): new node [20] sets next = head (the [10] node), returns [20]. List is now 20 -> 10.push_front(head, 30): same again, giving 30 -> 20 -> 10. Prepending reverses insertion order, which is why the values come out newest-first.print_list starts p at [30], prints 30 -> , hops to [20], prints 20 -> , hops to [10], prints 10 -> , hops to NULL, exits the loop, and prints NULL.remove_value(head, 30): pp = &head. *pp is [30], whose value equals the target, so the loop body never runs. dead = [30]; *pp = dead->next writes [20]'s address into head; free(dead) releases the old head. This is the pointer-to-pointer payoff: editing the head used the same code as editing any node.remove_value(head, 10): *pp is [20] (value 20 != 10), so pp advances to &[20]->next. Now *pp is [10] (match). *pp = dead->next writes NULL into [20]'s next, and [10] is freed. [20] becomes the tail.remove_value(head, 99): the loop walks until *pp == NULL (past the tail) without a match, so the if (*pp != NULL) block is skipped. Nothing changes.free_list saves head->next into next before freeing head, then advances. Skipping the save would mean reading a freed node — undefined behaviour.| Step | Action | List after |
|---|---|---|
| push 10 | head = [10] | 10 |
| push 20 | [20].next = [10] | 20 -> 10 |
| push 30 | [30].next = [20] | 30 -> 20 -> 10 |
| remove 30 | head = [20] | 20 -> 10 |
| remove 10 | [20].next = NULL | 20 |
| remove 99 | no match | 20 |
| free_list | free each node | (empty) |
1. Updating the head before linking (front insertion).
/* WRONG */
head = n;
n->next = head; /* n now points at itself; the old list is lost */
Why it is wrong: after head = n, the name head already equals n, so n->next = head makes the node point to itself and orphans every other node. Correct version:
n->next = head; /* link to the old list first */
head = n; /* then move the head */
Recognise it by an infinite print loop or a sudden "lost" list. Prevent it by always writing the two lines in this order.
2. Losing the head when a function inserts at the front.
/* WRONG: caller's head is never updated */
void push_front(node_t *head, int v) { /* ... modifies local copy ... */ }
The parameter head is a copy of the caller's pointer; reassigning it changes nothing outside. Fix by returning the new head (head = push_front(head, v);) or taking a node_t **.
3. Freeing a node before reading its next.
/* WRONG */
free(head);
head = head->next; /* use-after-free: head is already released */
Save next first (as free_list does). Recognise it via a Valgrind "invalid read" report.
4. Forgetting to free the list at all. Every malloc needs a matching free. Without a free_list walk, every node leaks. Recognise it with Valgrind's "definitely lost" summary.
5. Dereferencing a NULL head. Calling head->v on an empty list crashes. Always guard with if (head != NULL) or a loop condition that tests for NULL first.
Compiler errors
node_t next; or struct node next; (a value) instead of struct node *next; (a pointer). Add the *.struct node *next; inside the braces.p->v where p is void * or the struct is not fully declared. Check the type of p.Runtime errors
NULL, usually by using p->next after the loop, or by not initialising a new node's next to NULL.next pointer was left dangling. Confirm the predecessor's next was rewired before the free.Logic errors
next points back to an earlier node) or you never advance p. Verify the tail's next is NULL.p != NULL (visits all) versus p->next != NULL (stops one early).Debugging steps
valgrind ./a.out): it flags leaks, invalid reads/writes, and use-after-free with the offending line.head, p, and pp addresses to confirm the chain is wired as you expect.Questions to ask when it breaks: Did I save next before freeing? Did I set every new node's next? Is the head being updated in the caller? Does an empty list flow through this code without crashing?
Linked lists are a classic source of memory bugs in C because every node is a separate heap allocation with its own lifetime.
Ownership. Each node is owned by exactly one list. When you unlink a node, you (the code doing the unlinking) become responsible for freeing it. Do not free a node that is still reachable from the list, and do not free the same node twice (a double-free corrupts the allocator).
Initialisation. After malloc, a node's fields are indeterminate. Always set next (to another node or NULL) before the node joins the list; an uninitialised next is a dangling pointer waiting to crash a traversal.
Check every allocation. malloc can return NULL. Dereferencing that NULL is undefined behaviour, so test the result before using it, as make_node does.
Use-after-free and dangling pointers. The destroy loop must save head->next before free(head); reading a freed node is undefined behaviour. After free_list, set the head to NULL so no stale pointer is accidentally dereferenced later.
Leaks. Losing the head, or forgetting to free before the program exits, leaks every node. Pair every list you build with a free_list call, and verify with Valgrind that allocations and frees balance.
Cycles. If a next accidentally points back into the list, both traversal and free_list loop forever. Ensure exactly one tail whose next is NULL.
Concrete uses. The Linux kernel threads nearly every dynamic collection onto intrusive doubly-linked lists via its list_head macros (task lists, timer queues, and more). Memory allocators keep freed blocks on a free list so they can be reused quickly. LRU caches, undo/redo histories, job schedulers, and the collision chains inside hash tables are all linked lists at heart. Music playlists and browser back/forward histories are everyday mental models of the same idea.
Professional best practices (beginner):
typedef and meaningful field names.next, always check malloc, always pair a build with a free_list.make_node, push_front, free_list) instead of inlining the same pointer juggling everywhere.Professional best practices (advanced):
node_t ** idiom to delete the head-vs-interior special case.tail pointer (or use a doubly-linked list) when you need O(1) append.realloc-backed vector when you iterate hot loops — measure cache effects before choosing a list for performance-critical code.1. (Beginner) Length. Write int list_length(const node_t *head) that returns the number of nodes. Requirements: traverse with a counter; an empty list returns 0. Example: 10 -> 20 -> 30 returns 3. Hint: a single for loop over p = p->next. Concepts: traversal.
2. (Beginner) Sum. Write long list_sum(const node_t *head) that returns the sum of all v fields (use long to reduce overflow risk). Empty list returns 0. Example: 10 -> 20 -> 30 returns 60. Hint: accumulate inside the traversal loop. Concepts: traversal, integer types.
3. (Intermediate) Append at tail. Write node_t *push_back(node_t *head, int v) that adds v at the end and returns the head. Requirements: handle the empty-list case (new node becomes the head); otherwise walk to the tail and set its next. Example: appending 40 to 10 -> 20 gives 10 -> 20 -> 40. Constraint: no tail pointer allowed — walk each time. Hint: stop when p->next == NULL. Concepts: traversal, insertion, the empty-list edge case.
4. (Intermediate) Reverse in place. Write node_t *reverse(node_t *head) that reverses the links and returns the new head, without allocating new nodes. Example: 10 -> 20 -> 30 becomes 30 -> 20 -> 10. Constraint: O(1) extra space. Hint: keep three pointers — prev, cur, next — and rewire one link per step. Concepts: pointer rewiring, traversal.
5. (Challenge) Remove-by-index with pointer-to-pointer. Write node_t *remove_at(node_t *head, int index) that removes the node at position index (0-based), frees it, and returns the head. Requirements: use a node_t ** so removing index 0 needs no special case; if index is out of range, leave the list unchanged. Example: removing index 1 from 10 -> 20 -> 30 gives 10 -> 30. Constraint: exactly one free, no leaks. Hint: advance the node_t ** index times, then unlink *pp. Concepts: pointer-to-pointer, deletion, memory safety.
next pointers + a head. A node is a self-referential struct (struct node *next;), and an empty list is just head == NULL.for (p = head; p; p = p->next); it is O(n), which is why indexing element k costs O(k) while splicing at a known spot is O(1).n->next = head before head = n. Functions that change the head must return it or take a node_t **.node_t **) idiom deletes the head-vs-interior special case — master it, because it recurs in stacks, trees, and hash chains.malloc, initialise next, save next before free, run a free_list destroy loop, and null the head afterward. Verify with Valgrind.