Practical Data Structures: Linked Lists
Arrays are the first data structure every programmer learns — and for good reason. They're simple, cache-friendly, and give O(1) random access. But arrays have a fundamental constraint: their size is fixed at allocation time. When you don't know how many elements you'll need, when insertions and deletions happen in the middle rather than at the end, or when elements are large and expensive to shift — the linked list becomes essential. This lesson builds a complete, production-quality singly linked list from scratch, teaching you not just the "how" but the "why" behind every design decision.
1. The Anatomy of a Linked List
A linked list is a chain of nodes scattered across the heap. Each node contains payload data and a pointer to the next node. The list is accessed through a head pointer; the last node points to NULL.
HEAD
|
v
+----------+ +----------+ +----------+
| data: 10 | | data: 20 | | data: 30 |
| next: -------->| next: -------->| next: NULL|
+----------+ +----------+ +----------+
address: address: address:
0x7f8a3c0000 0x7f8a3c0010 0x7f8a3c0020
(no pattern — (heap allocator (nodes are
not contiguous) chooses free wherever)
blocks)
VS. ARRAY (contiguous):
+----------+----------+----------+
| data: 10 | data: 20 | data: 30 |
+----------+----------+----------+
addr addr+4 addr+8
The tradeoffs are stark: arrays win on cache locality and random access; linked lists win on O(1) insertion/deletion at the head and the ability to grow without reallocation. In performance-critical code, the cache miss penalty of pointer chasing often dominates — but for dynamic data where you're always traversing from the head anyway, linked lists remain the right choice.
2. The Self-Referential Node Structure
The node is the foundation. The critical insight: a struct can contain a pointer to its own type. This is called a self-referential structure:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data; /* payload — could be any type */
struct Node *next; /* self-referential: points to another Node */
} Node;
The typedef lets us write Node instead of struct Node. But note the forward-reference trick: inside the struct body, we must use struct Node because the Node typedef doesn't exist yet. This is one of C's few circular-dependency patterns.
3. Complete Operations: Insert, Delete, Search, Traverse
Let's build a full API. Every function returns the new head pointer, because insertions and deletions may change which node is first.
3.1 Create a Node (Factory Function)
Node* node_create(int data) {
Node *new_node = (Node*)malloc(sizeof(Node));
if (!new_node) {
fprintf(stderr, "node_create: malloc failed\n");
return NULL;
}
new_node->data = data;
new_node->next = NULL;
return new_node;
}
3.2 Insert at Head — O(1), the linked list's killer feature
Node* list_insert_head(Node *head, int data) {
Node *new_node = node_create(data);
if (!new_node) return head; /* allocation failure: return unchanged */
new_node->next = head; /* new node points to old head */
return new_node; /* new node becomes head */
}
/* Trace: head -> [20] -> [30] -> NULL
list_insert_head(head, 10):
new_node: [10, next=NULL]
new_node->next = head => [10] -> [20] -> [30] -> NULL
return [10] as new head */
3.3 Insert at Tail — O(n), must walk the entire list
Node* list_insert_tail(Node *head, int data) {
Node *new_node = node_create(data);
if (!new_node) return head;
if (head == NULL) return new_node; /* empty list: new node IS head */
Node *curr = head;
while (curr->next != NULL) { /* walk to the last node */
curr = curr->next;
}
curr->next = new_node; /* attach at end */
return head; /* head unchanged */
}
3.4 Insert After a Specific Value — find-and-insert
Node* list_insert_after(Node *head, int target, int data) {
Node *curr = head;
while (curr != NULL) {
if (curr->data == target) {
Node *new_node = node_create(data);
if (!new_node) return head;
new_node->next = curr->next; /* splice between curr and next */
curr->next = new_node;
return head;
}
curr = curr->next;
}
fprintf(stderr, "insert_after: target %d not found\n", target);
return head;
}
3.5 Delete by Value — O(n) with pointer-to-pointer elegance
Deleting a node from a singly linked list requires modifying the previous node's next pointer. The pointer-to-pointer technique handles all cases (head deletion, middle deletion, not found) uniformly:
Node* list_delete(Node *head, int target) {
Node **indirect = &head; /* points to whatever points to current node */
while (*indirect != NULL) {
if ((*indirect)->data == target) {
Node *to_free = *indirect; /* node to delete */
*indirect = (*indirect)->next; /* bypass it in the chain */
free(to_free);
return head;
}
indirect = &(*indirect)->next; /* advance to pointer-to-next */
}
fprintf(stderr, "delete: value %d not found\n", target);
return head;
}
/* The key insight: indirect points to the *location* that holds
the current node pointer. If we're at the head, indirect == &head.
If we're in the middle, indirect == &(prev_node->next).
So *indirect = (*indirect)->next updates the correct pointer
regardless of whether we're at the head or in the middle. */
3.6 Traverse (Print All Elements)
void list_print(const Node *head) {
const Node *curr = head;
while (curr != NULL) {
printf("%d", curr->data);
curr = curr->next;
if (curr != NULL) printf(" -> ");
}
printf(" -> NULL\n");
}
3.7 Destroy (Free Entire List)
void list_destroy(Node *head) {
Node *curr = head;
while (curr != NULL) {
Node *next = curr->next; /* save next before freeing */
free(curr);
curr = next;
}
}
4. Complete Demo Program
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node* node_create(int data) {
Node *n = (Node*)malloc(sizeof(Node));
if (!n) { fprintf(stderr, "malloc failed\n"); exit(1); }
n->data = data;
n->next = NULL;
return n;
}
Node* list_insert_head(Node *head, int data) {
Node *n = node_create(data);
n->next = head;
return n;
}
Node* list_insert_tail(Node *head, int data) {
Node *n = node_create(data);
if (!head) return n;
Node *curr = head;
while (curr->next) curr = curr->next;
curr->next = n;
return head;
}
Node* list_delete(Node *head, int target) {
Node **indirect = &head;
while (*indirect) {
if ((*indirect)->data == target) {
Node *to_free = *indirect;
*indirect = (*indirect)->next;
free(to_free);
return head;
}
indirect = &(*indirect)->next;
}
return head;
}
void list_print(const Node *head) {
while (head) {
printf("%d", head->data);
head = head->next;
if (head) printf(" -> ");
}
printf(" -> NULL\n");
}
void list_destroy(Node *head) {
while (head) {
Node *next = head->next;
free(head);
head = next;
}
}
int main() {
Node *list = NULL;
list = list_insert_head(list, 30); /* [30] */
list = list_insert_head(list, 20); /* [20, 30] */
list = list_insert_head(list, 10); /* [10, 20, 30] */
list_print(list); /* 10 -> 20 -> 30 -> NULL */
list = list_insert_tail(list, 40); /* [10, 20, 30, 40] */
list_print(list); /* 10 -> 20 -> 30 -> 40 -> NULL */
list = list_delete(list, 20); /* remove 20 */
list_print(list); /* 10 -> 30 -> 40 -> NULL */
list = list_delete(list, 10); /* remove head */
list_print(list); /* 30 -> 40 -> NULL */
list_destroy(list);
return 0;
}
5. Common Pitfalls and Debugging Strategies
5.1 Losing the Head Pointer
The most common beginner bug: forgetting to capture the return value of an operation that changes the head.
list_insert_head(list, 10); /* WRONG: return value ignored */
list = list_insert_head(list, 10); /* RIGHT */
5.2 Dereferencing NULL After Deletion
/* WRONG: curr->next becomes dangling after free */
while (curr) {
free(curr);
curr = curr->next; /* UNDEFINED: reading freed memory */
}
/* RIGHT: save next before freeing */
while (curr) {
Node *next = curr->next;
free(curr);
curr = next;
}
5.3 Forgetting to Handle the Empty-List Case
Every list operation must handle head == NULL. Insert at head: return the new node. Insert at tail: return the new node. Delete: nothing to delete, return NULL. Print: print nothing. These edge cases are not optional — they will crash your program.
6. Beyond Singly Linked: A Glimpse at Doubly Linked Lists
A doubly linked list adds a prev pointer to each node, enabling O(1) deletion when you have a pointer to the node (no need to walk from head) and bidirectional traversal. The cost: twice the pointer overhead per node and more complex insertion/deletion logic:
typedef struct DNode {
int data;
struct DNode *prev;
struct DNode *next;
} DNode;
/* Inserting into a doubly linked list requires updating four pointers:
new->prev = curr;
new->next = curr->next;
curr->next->prev = new;
curr->next = new;
Plus edge cases for head and tail. */
7. Key Takeaways
- A linked list node is a self-referential struct: it contains a pointer to its own type. This is the minimal building block for all pointer-based dynamic data structures (trees, graphs, hash chains).
- Operations that change the head pointer must return the new head; the caller must capture it. The pointer-to-pointer (
Node **) pattern is an elegant alternative that eliminates this requirement. - Insert at head is O(1) — the linked list's single biggest advantage over arrays. Insert at tail is O(n) without a tail pointer; maintain a
tailpointer if you frequently append. - The
list_deletepointer-to-pointer technique (Node **indirect = &head) handles all cases (head deletion, middle deletion, empty list) without special-case branches. - Always free nodes in the correct order: save
nextbefore callingfreeon the current node. A single leak per iteration in a long-running program is a slow death.
8. Practice Exercises
Exercise 1: Reverse a Linked List In-Place
Write Node* list_reverse(Node *head) that reverses a singly linked list without allocating any new nodes. The function should work in O(n) time and O(1) space. Draw the pointer reassignments for each step.
Node* list_reverse(Node *head) {
Node *prev = NULL;
Node *curr = head;
/* TODO: implement the reversal loop */
return prev;
}
/* Input: 10 -> 20 -> 30 -> NULL
Output: 30 -> 20 -> 10 -> NULL */
Hint: At each step, save curr->next, then point curr->next backward to prev, then advance both prev and curr.
Exercise 2: Detect a Cycle (Floyd's Algorithm)
Write int list_has_cycle(const Node *head) that returns 1 if the list contains a cycle (a node's next points to an earlier node), 0 otherwise. Use Floyd's "tortoise and hare" algorithm with O(1) space.
int list_has_cycle(const Node *head) {
if (!head) return 0;
const Node *slow = head;
const Node *fast = head;
/* TODO: detect cycle */
return 0;
}
Hint: slow advances one step, fast advances two. If they ever meet, there's a cycle. If fast reaches NULL, there isn't.
Exercise 3: Merge Two Sorted Lists
Write Node* list_merge_sorted(Node *a, Node *b) that merges two sorted linked lists into one sorted list without allocating new nodes (reuse the existing nodes). Return the head of the merged list.
/* Input: a = 10 -> 30 -> 50 -> NULL
b = 20 -> 40 -> 60 -> NULL
Output: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> NULL */
Node* list_merge_sorted(Node *a, Node *b);
Exercise 4: Remove Duplicates from Sorted List
Write Node* list_remove_duplicates(Node *head) that removes all duplicate values from a sorted linked list, keeping only the first occurrence of each value. Free the removed nodes.
/* Input: 10 -> 20 -> 20 -> 30 -> 30 -> 30 -> 40 -> NULL
Output: 10 -> 20 -> 30 -> 40 -> NULL */
Node* list_remove_duplicates(Node *head);
Hint: Since the list is sorted, duplicates are adjacent. Compare each node with its successor; if they match, bypass and free the duplicate.