Data structures: linked lists
18 min lesson
- A linked list is a chain of nodes, where each node holds a value and a pointer to the next node, so the elements do not need to sit next to each other in memory.
- Linked lists matter because they can grow and shrink easily and let you insert or remove items without shifting a whole array.
- Think of a linked list as a treasure hunt: each clue has a piece of treasure and the address of the next clue. You follow the chain from the first clue to the last.
- A node is a small struct with a value and a next pointer, like struct Node { int value; struct Node *next; }.
- The head is a pointer to the first node; if the head is NULL, the list is empty.
- Traversal means walking the list from the head to the end, following each next pointer until you reach NULL.
- The computer stores each node separately on the heap, and the next pointers tie them into a chain, so inserting a node only changes a couple of pointers.
- The syntax for a node struct is: struct Node { int value; struct Node *next; }; and to create one: struct Node *n = malloc(sizeof *n);.
- A realistic use: an undo history, a playlist that grows and shrinks, or a queue of tasks that arrive one at a time.
- A surprising detail: finding the nth item takes time proportional to n, because you must walk from the head; arrays can jump straight to an index.
- The example program builds a small list by adding nodes at the front, prints it, sums its values, and frees every node to avoid leaks.
- Always keep a pointer to the head; without it you lose the whole list.
- Free every node when you are done, or you leak memory.
- Remember that inserting at the front is fast, but searching is slow.
- Draw the pointers on paper when learning; it makes the logic clear.
- Linked lists are the gateway to real data structures. Great work!
#include <stdio.h>
#include <stdlib.h>
// A node holds an int value and a pointer to the next node
struct Node {
int value;
struct Node *next;
};
// Add a new node at the front of the list
struct Node *pushFront(struct Node *head, int value) {
// Allocate a new node on the heap
struct Node *node = malloc(sizeof *node);
// Stop if allocation failed
if (node == NULL) {
return head;
}
// Set the value and link the node to the current head
node->value = value;
node->next = head;
// The new node becomes the new head
return node;
}
int main(void) {
// Start with an empty list
struct Node *head = NULL;
// Push three values; each becomes the new front
head = pushFront(head, 10);
head = pushFront(head, 20);
head = pushFront(head, 30);
// Walk the list and sum the values
int total = 0;
for (struct Node *cur = head; cur != NULL; cur = cur->next) {
printf("Node: %d\n", cur->value);
total += cur->value;
}
printf("Total: %d\n", total);
// Free every node to avoid leaks
struct Node *cur = head;
while (cur != NULL) {
struct Node *next = cur->next;
free(cur);
cur = next;
}
return 0;
}What happens: Node: 30 Node: 20 Node: 10 Total: 60
Breaking it down
Node struct
struct Node { int value; struct Node *next; };Defines the shape of one link: a value and a pointer to the next node. The pointer is the chain.
Empty list
struct Node *head = NULL;An empty list is just a NULL head. Every traversal checks for NULL to know when to stop.
pushFront
node->next = head; return node;Creates a node, points it at the current head, and returns it as the new head. This makes insertion at the front very fast.
Traversal
for (cur = head; cur != NULL; cur = cur->next)Visits each node by following next pointers until NULL. This is the standard way to walk a list.
Freeing
free(cur); cur = next;Saves the next pointer before freeing the current node, so the chain is not lost. This prevents leaks.
Array vs linked list
| Operation | Array | Linked list |
|---|---|---|
| Access by index | Fast, O(1) | Slow, O(n) |
| Insert at front | Slow, shift all | Fast, O(1) |
| Insert in middle | Slow, shift | Fast if you have the node |
| Memory layout | Contiguous | Scattered nodes |
| Resize | Fixed or copy | Grows node by node |
A helpful analogy
A linked list is like a treasure hunt. Each clue has a piece of treasure (the value) and the address of the next clue (the next pointer). You start at the first clue (the head) and follow the chain until the last clue, which points to nowhere (NULL).
Nesting rules
- 1.Every node must have its next pointer set before it becomes part of the list.
- 2.Always stop traversal at NULL; dereferencing NULL crashes the program.
- 3.When freeing, save the next pointer before calling free on the current node.
- 4.Keep a single head pointer; without it the whole list is unreachable.
Common mistakes
Losing the next pointer before free
Avoid
free(cur);
cur = cur->next; // use after freeUse instead
struct Node *next = cur->next;
free(cur);
cur = next;After free, cur->next is invalid. Save the next pointer first, then free.
Forgetting to link the new node
Avoid
node->value = 5; // next uninitializedUse instead
node->value = 5;
node->next = head;An unlinked node is not part of the list, and its next pointer is garbage. Always set next.
Not checking malloc for NULL
Avoid
struct Node *n = malloc(sizeof *n);
n->value = 1; // crash if NULLUse instead
if (n == NULL) { /* handle */ }malloc returns NULL on failure. Dereferencing NULL crashes. Check before using the node.
Quick tips
- •Draw the list on paper before writing insert or delete code.
- •Write a helper to print the list and use it after each change.
- •Free the whole list at the end of every test to keep Valgrind clean.
- •Try adding a value in the middle and see how the pointers change.
- •Use a tail pointer if you need fast appends; it is a common next step.