Linked Lists: The Complete Guide

July 2026 · 22 min read

An array asks the machine one question: where does the block start? Everything else is arithmetic. A linked list asks a different question at every single element: where do I go next? That one change — replacing address arithmetic with an explicit pointer — is the whole subject. It buys you O(1) splicing anywhere you already stand, and it costs you random access, cache locality, and one pointer of memory per element.

Linked lists are the cheapest possible way to learn pointer discipline. Nearly every hard bug you will ever hit in a systems codebase — a dangling pointer, a leaked allocation, a broken invariant halfway through an update, an iterator invalidated under you — has a two-line linked-list version you can hold in your head. That is why interviewers keep asking, and why the topic never really goes away: the Linux kernel, every serious allocator, every LRU cache, every intrusive scheduler queue, and every lock-free MPSC channel is a linked list wearing a hat.

The One Invariant Behind Every Problem

Every linked-list algorithm is a sequence of pointer rewrites, and every pointer rewrite has exactly one danger: overwriting the only reference to a node before you are done with it. That is the whole failure mode. The discipline that prevents it is mechanical:

1. Save whatever you are about to lose (next = cur->next).
2. Rewire the pointers (cur->next = prev).
3. Advance your cursors in the order that keeps them consistent (prev = cur; cur = next).

Save, rewire, advance. Reversal is that loop. Insertion is that loop unrolled once. Deletion is that loop with one hop skipped. Merge is two of those loops interleaved. If you can see the three steps, you can re-derive every routine on this page under interview pressure instead of recalling it.

When a Linked List Is Right — and When It Is Not

Being able to implement one is table stakes. Knowing when not to reach for one is what separates a competent engineer from a candidate reciting Big-O. The honest comparison:

Read that table as one sentence: linked lists trade throughput for stability and splice cost. Choose them when you hold references to elements that must stay valid, when you splice ranges between containers, when you cannot afford a reallocation pause, or when nodes are already owned by something else (intrusive lists). Choose an array almost every other time — a modern CPU can scan a contiguous array faster than it can chase 1/10th as many pointers.

How to Read This Series

Top to bottom, once. The posts assume the previous ones: Module 2 uses the sentinel technique from Module 1, Module 3 assumes you can reverse and merge without thinking, and Module 4 is pure consolidation. If you already write lists comfortably, start at Fast & Slow Pointers and treat Module 1 as reference.

Module 1: Foundations and representation

1. Nodes, Pointers & Memory Layout: what a node really is in memory, heap allocation cost, pointer chasing vs. sequential scanning, cache lines and why lists lose benchmarks, and the ownership question every list must answer.
2. Singly Linked List From Scratch: building, traversing, inserting at head/middle/tail, deleting by value and by position, searching, length, and a complete C++ class with correct destruction.
3. Sentinels, Dummy Heads & Tail Pointers: how one fake node deletes half your edge cases, the pointer-to-pointer trick, maintaining a tail for O(1) append, and why std::forward_list exposes insert_after.
4. Doubly Linked Lists: the prev pointer, symmetric splice/unlink primitives, O(1) deletion given only a node, bidirectional iteration, and the memory/complexity trade-off against singly linked.
5. Circular Linked Lists: circular singly and doubly variants, tail-only representation, round-robin scheduling, the Josephus problem, and how to traverse without an infinite loop.
6. std::forward_list & std::list in Practice: the real APIs, splice, merge, remove_if, unique, iterator invalidation guarantees, allocator behaviour, and when the standard containers beat a hand-rolled list.

Module 2: Core techniques that get tested

7. Traversal & Pointer-Surgery Patterns: the prev/cur idiom, the pointer-to-pointer idiom, loop conditions that never off-by-one, deleting while iterating, and the templates that solve a third of all list problems.
8. Reversing a Linked List: the three-pointer loop derived from first principles, the recursive formulation and its stack cost, reversing a doubly linked list, and the invariant that proves the loop correct.
9. Sublist & K-Group Reversal: reverse between positions m and n in one pass, reverse every k nodes with and without a remainder, swap adjacent pairs, and the reconnection bookkeeping people get wrong.
10. Fast & Slow Pointers: finding the middle with both midpoint conventions, n-th node from the end, deleting the middle, splitting a list in half, and the general "gap" template.
11. Cycle Detection: Floyd, Brent & the Proofs: tortoise and hare, the full proof of why resetting to head finds the cycle entrance, cycle length, Brent's algorithm, happy numbers, and cycle detection in functional graphs.
12. Merging Sorted Lists: two-way merge with a dummy head, in-place merging, k-way merge with a heap versus divide and conquer, and the complexity comparison that decides which to use.
13. Sorting a Linked List: why merge sort is the list sort, top-down versus bottom-up O(1)-space merge sort, insertion sort on lists, quicksort by splicing, and what std::list::sort actually does.
14. Partitioning, Reordering & Rotation: stable partition around a pivot, odd-even splitting, reorder L0→Ln→L1→Ln-1, rotate right by k, and removing duplicates from sorted and unsorted lists.
15. Arithmetic on Linked Lists: adding two numbers in forward and reverse digit order, carry propagation without reversing, subtraction, multiplication, plus-one, and big-integer representation as a list.
16. Recursion on Linked Lists: the structural-induction template, head recursion vs. tail recursion, palindrome checking in O(1) space, why deep lists blow the stack, and converting any list recursion into a loop.

Module 3: Advanced structures and real systems

17. Deep Copy with Random Pointers: the hash-map clone, the O(1)-space interleaving trick, restoring the original list, and how the same idea copies arbitrary object graphs.
18. Flattening Multilevel & Nested Lists: depth-first flattening of a child/next list, flattening a list of sorted lists, the stack-based iterative version, and reconstructing the original structure.
19. LRU Cache: Hash Map + Doubly Linked List: the canonical O(1) design, sentinel-based implementation, why a singly linked list fails, std::list::splice as a one-liner, and eviction correctness.
20. LFU Cache: frequency buckets as lists of lists, O(1) get and put, the min-frequency invariant, tie-breaking by recency, and the comparison against LRU.
21. Skip Lists: probabilistic levels, expected O(log n) search/insert/delete, the coin-flip height distribution, why Redis uses one for sorted sets, and skip lists versus balanced trees.
22. XOR Linked Lists: storing prev ^ next in one field, bidirectional traversal from either end, the arithmetic that makes it work, and why this is a curiosity rather than production code.
23. Unrolled & Intrusive Lists: packing k elements per node to win back cache locality, the Linux kernel list_head pattern, container_of, zero-allocation membership, and Boost.Intrusive.
24. Concurrent & Lock-Free Lists: fine-grained locking and hand-over-hand traversal, the Michael–Scott queue, CAS-based insertion, the ABA problem, logical deletion with marked pointers, and memory reclamation.

Module 4: Consolidation and mastery

25. Pitfalls, Leaks & Memory Safety: the ten bugs that account for nearly every failed list implementation, recursive destructor stack overflow, double free, self-loops, use-after-free, and how to test a list properly.
26. Interview Pattern Catalog: a decision tree from problem statement to technique, the eight recurring patterns, the questions to ask before writing code, and how to talk through pointer surgery out loud.
27. Curated Problem Catalog: the problem set that actually covers the space, grouped by pattern and ordered by difficulty, with the one insight each problem is testing.
28. Capstone: The Linked List Final Exam: a self-assessment covering the entire series, a from-memory implementation checklist, and the complexity table you should be able to reproduce cold.

Prerequisites

• Comfort with pointers or references in one systems language. All code here is C++, but the pointer surgery translates directly to C, Rust (with care), Java, or Go.
• Basic asymptotic analysis. If Big-O still feels vague, read Time & Space Complexity first.
• Nothing else. This series is self-contained and builds the data structure from a single struct.

Quick Reference: Complexities to Memorise

Start Here

Begin with Nodes, Pointers & Memory Layout. It is the shortest post in the series and the one that makes every later trick feel obvious rather than clever.