An introduction to algorithm analysis with a practical focus on how CPUs execute code and fetch data. Topics include growth rates, locality, and why memory layout matters

An introduction to data structures and algorithms from a practical, hardware-first perspective. Learn how the physical layout of your data in memory impacts performance.

Data Structures & Algorithms

Understand how our code interacts with physical hardware. Learn about virtual memory, the stack vs. heap, cache lines, and prefetching.

CPUs, Memory, and Locality

Learn how input size affects execution speed and the most common class of algorithms.

Polynomial Algorithms

Working with massive datasets using divide and conquer strategies, and the the required trade-offs.

Logarithmic and Linearithmic Algorithms

Learn why some problems are impossible to solve exactly and how we can use approximations like Monte Carlo simulations to cheat.

NP-Hard and Approximations

Practical Algorithm Analysis

Setting up a lightweight framework for measuring performance. Create benchmarks that produce reliable, meaningful results

Separate our core logic into libraries, configure CMake for multiple targets, and apply hardware-aware optimizations.

Configuring a CMake Project

Integrate the industry-standard Google Benchmark library into a CMake project to capture nanosecond-precision timings.

Integrating Google Benchmark

Fight the compiler's aggressive optimizations to ensure benchmarks measure reality.

Writing Effective Benchmarks

Learn to interpret CPU time, variance, and the trade-offs between insertion speed and read speed.

Analyzing Benchmark Data

Using Google Benchmark's Range and Complexity features to visualize Big O growth and identify the moment our data falls off the CPU cache cliff.

Mapping Complexity and Hardware Cliffs

Using benchmarks to calculate the 'break-even point' where investing in data preparation pays off.

Amortized Costs and Crossover Points

Google Benchmark for C++

Understand how C++20 ranges reshape the standard library. Learn to combine algorithms and views for clean, efficient code

The bridge between data layout and algorithms. Learn how iterators abstract memory traversal and the hierarchy of capabilities.

The Iterator Pattern

An introduction to the C++ Standard Library's algorithms, lambda expressions, and handling memory safely with insertion iterators.

Standard Library Algorithms

Learn how C++20 Ranges and Views allow us to compose safe, lazy-evaluated data pipelines without sacrificing performance.

C++20 Ranges

Learn how to build readable, lazy-evaluated data pipelines that execute in a single pass, and chain C++20 views together using the pipe operator `|`

View Composition and Pipes

Bridge the gap between iterators and views using `std::ranges::subrange` to turn any pair of iterators into a composable, safe C++20 View.

Subranges and Range Interoperability

Iterators, Ranges, and Views

Implement modern C++23 data processing with views and algorithms. Reduce boilerplate while improving correctness and performance

The Producer-Consumer model of C++20 Ranges and the hardware implications of eager vs lazy evaluation.

The Four Algorithm Families

Integrate sorting into C++20 pipelines, the difference between stable and unstable sorts, and how to use partial sorting.

Sorting and Materialization

Learn how C++20 Projections allow us to separate sorting logic from data layout, the mechanics of `std::invoke` and the hardware reality of sorting large objects.

Comparators and Projections

Learn why sorting large objects is slow, and how to optimize it using Proxy Sorting and Data-Oriented Design (SoA).

Proxy Sort and Structure of Arrays

Iterate multiple containers simultaneously with `zip`, handle indices with `enumerate`, and skip elements with `drop` and `stride`.

Composition, Zipping, and Indicies

Using Algorithms and Views

Modern processors are built for parallel execution, not sequential code. Learn how to use multithreading and vectorization in C++ to match that reality

Offload heavy work to other CPU cores. Learn how `std::async` and `std::future` enable concurrent execution.

Asynchronous Tasks with `std::async`

Combine the elegance of C++20 Ranges with the power of parallel execution policies.

Parallel Algorithms and Execution Policies

Learn how mutexes and atomics prevent race conditions, and why hardware contention can make multithreaded code slower than single-threaded code.

Locks and Atomics

Explore the performance cost of synchronization, how to mitigate it, and how to avoid it entirely with better algorithm design.

Cache Coherency and False Sharing

Learn how SIMD registers allow you to process multiple data points in a single instruction, unlocking the full power of each CPU core.

SIMD and Automatic Vectorization

Introduction to Parallelism

Learn how to design and implement a domain-specific container from scratch. The chapter focuses on cache efficiency, data-oriented design, and real-world performance trade-offs

Build a custom container that combines the performance of data-oriented design with the ergonomics of object-oriented programming.

Domain-Specific Containers

Implement proxy sorting, physical memory permutations, and multi-threaded reordering.

Sorting and Permuting Containers

Comparing the performance cost of deletion techniques, and implementing the Swap-and-Pop approach in a Structure of Arrays container.

The Swap-and-Pop Idiom

Solving the index invalidation problem and the trade-offs between memory density and reference stability.

Stable Addressing and Tombstones

Upgrade simple indices into Generational Handles, creating safe, persistent references that detect stale access.

Generational Indices

The hidden cost of `std::vector` growth, why it is dangerous for real-time systems, and how to mitigate it.

The Reallocation Spike

Implementing a Structure of Arrays

Learn advanced bit-centric techniques including fast filtering, bit packing, and compression to maximize efficiency

Learn to use bitwise operators to pack multiple states into a single byte, reducing memory bandwidth use.

Working with Bits

Replace slow logical operators with fast bitwise arithmetic. Learn how to filter data without branching, avoiding pipeline flushes and speeding up queries.

Fast Filtering and Branchless Logic

Trade CPU cycles for memory bandwidth by compressing data using bit packing, quantization, and delta encoding.

Quantization and Delta Encoding

Use bloom filters for fast rejection, hierarchical bitmasks for spatial skipping, and hardware intrinsics using C++20's `<bit>` library.

Advanced Bitwise Techniques

Implement the high-performance Entity-Component-System (ECS) design pattern, alongside an API that makes the architecture easy to use

Transitioning from monolithic data structures to the ECS architecture, splitting our data into dedicated component pools.

Entity-Component-System (ECS)

Connecting components to their entities using the sparse set pattern, achieving fast lookups while maintaining cache-friendly contiguous data.

Relational Data and Sparse Sets

Efficiently pulling data from multiple component pools simultaneously using the smallest set driver pattern, and optimizing it using bitmasks to minimize cache misses.

The Join Algorithm

Improving our API using templates and a centralized registry using `std::tuple`.

Templatizing Components

Updating our ECS to support composable, range-based views that handle the smallest-set algorithm automatically using C++20 ranges.

Creating Views

Entity-Component-System

Learn the physical reality and problems of allocating memory on the heap, and how to bypass these issues using custom allocators

Understanding the mechanisms of memory allocation, and the severe hardware cost of working with the heap.

The Physical Reality of `new` and `delete`

Why do long-running programs inevitably degrade and crash? Discover the hardware reality of memory fragmentation and TLB thrashing.

Memory Fragmentation

Bypass the OS and the global allocator. Build a custom linear arena allocator to implement fast memory allocation with zero fragmentation.

Linear and Arena Allocators

Solve the problem of dynamic entity lifespans. Build a zero-allocation object pool using an implicit free list hidden inside dead memory.

Object Pools and Free Lists

Memory Management and Custom Allocators

An introduction to the mechanics of linked lists, their strengths and weaknesses, and how those weaknesses can be mitigated in high-performance systems

An introduction to node-based data structures. The physical reality of `std::list`, pointer swapping, fast insertions, and why pointer chasing destroys performance.

The Mechanics of Linked Lists

Replace 64-bit pointers with lightweight indices and back our linked list with a contiguous memory pool to maximize performance.

Index-Based and Pool-Allocated Lists

Balance the flexibility of linked lists with cache-line sympathy of arrays. Learn how to group data into contiguous chunks to drastically reduce pointer chasing.

Unrolled Linked Lists

Eliminate node wrappers and heap allocations entirely. Learn how the Linux kernel uses intrusive structures to weave physical memory into multiple logical lists simultaneously.

Intrusive Linked Lists

Trade memory capacity for faster search speeds. Learn how probabilistic express lanes create highly concurrent, self-balancing data structures.

Skip Lists and Probabilistic Linking

Linked Lists

Build high-performance, lock-free algorithms using native hardware instructions. Master optimistic concurrency, tame out-of-order execution with memory fences, and navigate the ABA pointer problem.

Review concurrency and learn how to directly manage OS threads using `std::thread` and `std::jthread`.

Execution Contexts and `std::thread`

Understand the physical reality of moving data between RAM and registers. Learn why explicit loads and stores are required to prevent data tearing in complex structs.

Data Tearing and `std::atomic`

Learn how to perform complex lock-free atomic updates using `compare_exchange_weak()` and the hardware limitations.

Compare-And-Swap (CAS)

Learn how CPU out-of-order execution breaks lock-free code, and how to use `seq_cst`, `acquire`, `release`, `acq_rel`, and `relaxed` to fix it.

Instruction Reordering

Discover why using CAS on pointers is a hardware minefield, exposing the physical realities of memory allocators and the infamous ABA problem.

Lock-Free Pointers

Lock-Free Mechanics

Transition from static data storage to data flow. Implement decoupled architectures and stream data across CPU cores using lock-free concurrency

Learn how to decouple producers and consumers using FIFO and LIFO buffering structures.

Queues and Stacks

Learn how to bend a contiguous array into an infinite circle to build fast FIFO data pipelines.

Ring Buffers

Build a Single-Producer Single-Consumer lock-free queue using atomics, memory barriers, and cache-line alignment.

SPSC Ring Buffers

Build a Multi-Producer Multi-Consumer lock-free queue using CAS loops, Sequence Tickets, and memory ordering.

MPMC Ring Buffers

Build a highly concurrent, lock-free object pool and defeat the ABA problem using generation tags.

Lock-Free Object Pools

Build a highly concurrent Treiber stack using atomic Compare-And-Swap (CAS) instructions.

Lock-Free Stacks

Stacks and Queues

Building optimized containers that use open addressing, Robin Hood heuristics, cuckoo hashing, and consistent hashing techniques

Explore hashing, bitwise masking, and why the standard library's implementations hurt CPU cache performance.

Hash-Based Containers

Learn how to build a contiguous, cache-friendly hash set using open addressing and linear probing.

Flat Sets and Linear Probing

Fix the worst-case scenarios of linear probing by implementing Robin Hood Hashing to minimize variance and keep CPU cache lines packed.

Robin Hood Hashing

Learn why string keys destroy cache locality, and how to fix it using Hash Caching and Heterogeneous Lookups.

Hash Caching and Heterogeneous Lookups

Learn how to globally deduplicate string data and transform complex data into fast integer handles.

String Interning

When our work outgrows a single machine's capability, learn how to partition it across a cluster using Consistent Hashing.

Hash Rings and Consistent Hashing

Implement strict guarantees by bounding a lookup to exactly two memory locations, and build a fast rejection path for massive databases.

Cuckoo Hashing and Filters

High-Speed Hashing

Additional lessons and chapters covering vectorization and trees are coming soon

Coming Soon

This course is intended for those who already have a basic familiarity with C++

Learn data structures and algorithms by building real systems, measuring performance, and understanding how your code interacts with the physical hardware.

A hands-on course where you'll implement, benchmark, and optimize code, turning abstract concepts into practical skills you can immediately apply.

Implement real systems like ECS and custom containers from scratch, reinforcing concepts through hands-on work and gaining confidence by building complete, working solutions.

Learn by Building

Turn abstract concepts into efficient implementations, learning how theoretical ideas translate into real-world code you can understand, modify, and confidently apply.

From Theory to Code

Identify performance bottlenecks, measure improvements correctly, and apply practical optimization techniques without guesswork or misleading assumptions about what actually matters.

Debug and Optimize

Use C++20 and C++23 features to write cleaner, more expressive code while reducing boilerplate and improving both safety and performance in everyday development.

Modern C++ Techniques

Build a toolkit of reusable patterns and approaches that transfer across projects, helping you solve new problems faster without relying on memorized solutions.

Reusable Patterns

Learn how to balance performance, readability, and maintainability, making better engineering decisions based on real constraints rather than idealized or purely theoretical scenarios.

Real-World Tradeoffs

What You'll Learn

Become a software engineer with C++.  Starting from the basics, we guide you step by step along the way

Intro to C++ Programming

If you're completely new to programming, we recommend starting with our introductory course:

New to Programming?

Practical DSA

With our memory foundation secure, we are ready to transition away from flat, contiguous arrays and begin building structural layouts. We are moving into the world of **node-based data structures**.


With a contiguous array, the physical arrangement dictates the logical order.  If we had a collection of sorted characters, `A`, `B`, and `C`, they would sit right next to each other, in that order, in memory.


A linked data structure works differently. The physical location of elements is not related to their logical ordering. Instead, the logical order is dictated by **pointers** that are stored and managed alongside the key data.


<Interactive id="dsa-contiguous-linked-add-item">


Accessibility Note: An interactive component visualizing a block of memory. It displays several objects.

- When the "Contiguous" button is clicked, the objects are arranged tightly together in a single block, one after another.
- When the "Linked" button is clicked, the objects are scattered randomly across the memory space. Arrows are drawn from one object to the next, visualizing the pointers that connect them.

</Interactive>


In this lesson, we will dissect the simplest linked structure in existence: the **linked list**. We will look at its key strengths compared to contiguous structures, how a standard linked list is typically implemented, and some of the problems with that approach.  We will then introduce to some of the techniques we'll apply throughout the rest of the chapter to mitigate against those problems.


## The Physical Structure of a Node


When we use a `std::vector<int>`, the standard library allocates a single, contiguous block of memory to hold our integers.  Nothing else is required, as the logical ordering of the data can be inferred by physical ordering in memory.


When we use a linked list, the physical location of each object in the collection is relatively meaningless.  To express how the data is ordered, we need additional pointers.  To set this up, linked list implementations have the concept of a **node**.  Conceptually, a node is an object that contains both the data we're storing for each element in the collection, in addition to the pointers that define the overall structure of the collection.


If we wanted to store a linked list of integers, for example, each node would contain the integer, as well as a pointer to the next node in the collection.  The linked list itself can then be as simple as a pointer to the first node in the chain, which is usually called the **head** of the list:


<Interactive id="dsa-singly-linked-list">


A grid showing a memory layout and three nodes in our linked list.  Each node stores an `int` called `Payload` and a `Node*` called `Next` pointing to the next node in the list.  The nodes are visually connected by these pointers.  The `Next` value of the last node is a `nullptr`, representing the end of the list.


</Interactive>


### Singly Linked (`std::forward_list`)


The previous diagram was an example of a **singly linked list**.  This represents the absolute minimum structural overhead required to maintain a sequence. Every node contains the **payload** (the primary data we're trying to store) and one pointer, which holds the memory address of the next node in the chain, or a `nullptr` if there are no further nodes.


The C++ standard library implementation of this is `std::forward_list`. If we were to strip away the template magic, the physical structure of a singly linked node looks like this:


```c++
template <typename T>
struct SinglyNode {
  T Payload;             // Your data
  SinglyNode* Next;      // Memory address of the next node
};
```


Below, we use the `SinglyNode` type to create a linked list containing three elements:


```c++
// We allocate nodes on the heap and wire their pointers together
SinglyNode<int>* node3 = new SinglyNode<int>{30, nullptr};
SinglyNode<int>* node2 = new SinglyNode<int>{20, node3};
SinglyNode<int>* Head  = new SinglyNode<int>{10, node2};

// In real code, we must also delete these to avoid leaks
```


Wrappers like `std::forward_list` hides these intermediate node objects and these mechanical steps.  They expose a simple public interface that makes adding, removing, and iterating through the objects in our collection much easier.  Some of the key methods are shown below:


```c++
#include <forward_list>
#include <iostream>

int main() {
  // Create a list for storing int values
  std::forward_list<int> list;

  // Add elements to the front
  list.push_front(30);
  list.push_front(20);
  
  // Construct an element in-place
  list.emplace_front(10);
  
  // Iterate through the nodes
  for (int value : list) {
    std::cout << value << " ";
  }
  
  // Access the first element
  int value = list.front(); // 10
  
  // Remove the first element
  list.pop_front();
  
  value = list.front(); // 20
  
  // Wipe the entire chain
  list.clear();
}
```


However, behind the scenes, because each node only has a `Next` pointer, we can only move forward. If we are currently looking at node number 50, and we realize we need to check something on node 49, we are out of luck. Unless we remembered where node 49 was, the only way to get back to it was to jump all the way back to the `Head` pointer (the start of the list) and manually walk forward 49 steps.


We can see these limitations if we attempt to iterate through a `std::forward_list` in reverse order:


```c++
#include <forward_list>
#include <ranges>
#include <iostream>

int main() {
  std::forward_list<int> list{10, 20, 30};

  for (int value : std::views::reverse(list)) { //<e>
    std::cout << value << " ";
  }
}
```


```c++
//<oe>
error: std::forward_list does not satisfy bidirectional_range
```


### Doubly Linked (`std::list`)


To solve the traversal problem, we can add more metadata. A doubly linked list node contains _two_ pointers: one pointing forward, and one pointing backward.


<Interactive id="dsa-doubly-linked-list">


A grid showing a memory layout and three nodes in our  doubly linked list.  Each node stores an `int` called `Payload`, a `Node*` called `Next`, pointing to the next node in the list, and a `Node*` called `Prev`, pointing to the previous node in the list.  The nodes are visually connected by these pointers.  The `Next` value of the last node and the `Prev` value of the first node are `nullptr`s.


</Interactive>


This is the implementation used by the `std::list` container. Mechanically, it looks like this:


```c++
template <typename T>
struct DoublyNode {
  T Payload;
  DoublyNode* Prev; //<h>
  DoublyNode* Next;
};
```


Now, we can traverse our collection in either direction:


```c++
#include <list>
#include <ranges>
#include <iostream>

int main() {
  std::list<int> list{10, 20, 30};

  for (int value : std::views::reverse(list)) {//<h>
    std::cout << value << " ";
  }
}
```


```c++
//<o>
30 20 10
```


## The Advantages of Linked Structures


We previously saw how contiguous structures like `std::vector` give us the best possible iteration speed, but manipulating their structure is relatively expensive.

- If we want to add an element to an array, we need to physically shift everything that comes after that element to make space.  Even if we add an element to the end, that might take us over our capacity, leading to a massive <InlineLessonPromo url="dsa/reallocation" title="The Reallocation Spike" description="The hidden cost of `std::vector` growth, why it is dangerous for real-time systems, and how to mitigate it.">reallocation spike</InlineLessonPromo>
- If we want to remove an element, we need to shift everything that comes after to fill the gap, or perform a <InlineLessonPromo url="dsa/swap-and-pop" title="The Swap-and-Pop Idiom" description="Comparing the performance cost of deletion techniques, and implementing the Swap-and-Pop approach in a Structure of Arrays container.">swap-and-pop</InlineLessonPromo> operation that changes the logical order of the remaining elements
- If we want to sort the collection, that's a particularly heavy, physical operation

In addition, all of this physical movement invalidates pointers, adding more engineering overhead or risk of bugs.


<Interactive id="dsa-array-ops">


Interactive showing an array, with buttons to Add, Remove, Sort, and Splicing multiple elements out of the array.  Clicking these buttons shows the physical movement required to implement these instructions


</Interactive>


The primary benefit of linked data is their algorithmic efficiency and stability when modifying the structure.  Elements rarely need to be physically moved - we can change the logical structure of the collection simply by changing where the pointers point to.


The most powerful example of this is **splicing**, where large sequences of nodes can be taken out of one list and placed into another in constant $O(1)$ time with no physical movement - all it takes is some pointer updates.


<Interactive id="dsa-linked-list-ops">


Interactive showing a singly linked list, with buttons to Add, Remove, Sort, and Splicing multiple elements out of the list.  Clicking these buttons shows the pointer adjustments required to implement these instructions, with no physical movement of elements required


</Interactive>


### The `size()` Caveat


Traditionally, determining how many elements are in a linked list was an $O(N)$ operation - we needed to walk through all the nodes, tracking how many steps it takes until we reach the node with the null `Next` value.  Alternatively, if we want the size of our collection to be available faster, we could proactively keep track of how many elements are in our list, updating a `size` variable every time elements are added or removed.


However, we sometimes won't know how many elements we're adding or removing.  We may just have two pointers or iterators representing the first and last nodes of a chain we want to insert.  In that scenario, the container must walk the range to know how the `size` of our collection will be affected.


When designing our own containers, we can set our own preferences here - we can let `size()` be an $O(N)$ algorithm that traverses the list, or we can make insertions and deletions slightly slower to ensure a `size` variable is always up to date and immediately available.


From C++11 onwards, the specification requires that  `size()` must be $O(1)$ for all standard containers, so `std::list` chooses the latter option.  This most notably affects its `splice()` method.  The simple pointer updates to move a range of nodes between lists is an $O(1)$ operation, but updating the `size` of the lists requires an $O(N)$ scan over the range to count how many nodes are being transferred.


## The Disadvantages of Linked Structures


While it is conceptually elegant that linked lists do not physically move elements when they are added or removed, this design ignores the physical reality of the machine. The CPU does not care about logical elegance; it cares about physical data layout.


Because the elements of a standard linked list are allocated individually on the global heap, they are scattered randomly across the machine's RAM. To understand why this is a massive problem, we need to examine the actual memory footprint of a single node and how the CPU attempts to read that scattered memory.


### The Tax of the Pointers


On a modern 64-bit CPU, every pointer consumes exactly 8 bytes of physical RAM.  Let's look at the true physical size of a `std::list<int>`. Our payload is a standard 32-bit integer, which typically consumes 4 bytes. We have a `Prev` pointer (8 bytes) and a `Next` pointer (8 bytes).


But we are not done. Remember the strict CPU alignment rules we discussed when building our <InlineLessonPromo url="dsa/linear-arena-allocators" title="Linear and Arena Allocators" description="Bypass the OS and the global allocator. Build a custom linear arena allocator to implement fast memory allocation with zero fragmentation.">arena allocator</InlineLessonPromo> Because our struct contains 8-byte pointers, the compiler will force the entire struct to align to an 8-byte boundary.


It will inject 4 bytes of dead padding into our node to ensure the subsequent pointers land on safe memory addresses.


```c++
struct ListNode {
  int Payload;     // 4 bytes
  // Padding       // 4 bytes injected by compiler //<w>
  ListNode* Prev;  // 8 bytes
  ListNode* Next;  // 8 bytes
};
```


Each 4 byte integer in our collection now requires 24 bytes, but we're still not done.  To help with bookkeeping, the global allocator also allocates the hidden chunk headers we discussed <InlineLessonPromo slug="physical-reality-new-delete">earlier in the course</InlineLessonPromo>.


These chunk headers are rarely smaller than 16 bytes, so we're now up to 90% waste - allocating 40 bytes to store a 4 byte integer.


### The Hardware Prefetcher


As we covered in the initial chapter, the CPU is orders of magnitude faster than the main RAM. To keep the CPU fed, the hardware relies on the **L1 cache** and the **hardware prefetcher**.


When we iterate through a `std::vector`, the memory accesses are perfectly linear (`Buffer + 0`, `Buffer + 4`, `Buffer + 8`). The prefetcher recognizes this pattern instantly. It runs ahead of our code, pulling 64-byte chunks of data from main RAM into the L1 cache before the CPU even asks for them.


When we iterate through a linked structure, we execute a completely different mechanical pattern.


```c++
void Traverse(DoublyNode* current) {
  while (current != nullptr) {
    Process(current->Payload);

    // The CPU stall happens here
    current = current->Next; //<w>
  }
}
```


Think about how the CPU actually executes `current = current->Next`.  The CPU cannot ask for the next node until it has finished reading the current node to find out what the `Next` memory address actually is.


Because each node was likely allocated at a random time by the global heap allocator, they are physically scattered across gigabytes of virtual memory.  The hardware prefetcher is completely blind - it cannot predict where the next read will occur.


When the CPU executes `current->Next`, it looks in the L1 cache. It misses. It looks in L2. It misses. It is forced to halt the execution pipeline entirely, reach all the way out to main RAM, suffer a massive latency penalty, and fetch the cache line containing the new node.


It resumes, processes the payload, and then immediately hits the next pointer. It misses again.  This is called **pointer chasing**, and we are forcing the CPU to wait on the physical latency of RAM chips over and over again.


## Optimizing Linked Structures


So, do we throw linked lists in the trash? Absolutely not.  There are complex systems, such as operating system task schedulers and game engine scene graphs, where physical shifting is either structurally impossible or fundamentally too expensive.


The solution is not to abandon the linked list - the solution is to rescue it from the global allocator.  In this lesson, we assumed that each node was randomly allocated by `new`. But we just spent an entire chapter learning how to build our own memory allocators.


In the rest of this chapter, we'll apply and build on these techniques to drastically reduce the cost of using linked structures whilst maintaining their flexibility.


## Summary


In this lesson, we introduced the basics of node-based structures.  Here are the key points:

1. A **node** acts as a structural envelope, carrying our payload alongside pointer metadata.
2. Singly linked lists like `std::forward_list` uses a single `Next` pointer, minimizing size but restricting us to forward traversal.
3. Doubly linked lists like `std::list` uses `Prev` and `Next` pointers, increasing size but enabling bidirectional traversal.
4. Linked lists achieve $O(1)$ insertions and deletions because modifying the sequence only requires rewiring local pointers, not physically shifting surrounding data.
5. Because data never physically moves, pointers to list elements are stable, remaining valid until explicitly deleted.
6. Standard linked lists are often catastrophically slow due to the increased memory footprint of the pointers and the latency of chasing those pointers. Random heap allocations destroy spatial locality, causing continuous CPU cache misses.

We have established that the architecture of a linked list is useful, but the global heap implementation is fatal to performance.


In the next lesson, we will combine our knowledge of custom allocators and node mechanics. We will ditch the 64-bit heap pointers entirely, replace them with tiny integer indices, and build a fast, cache-friendly **index-based linked list**.

std::list

std::forward_list

CppCon 2014: Bjarne Stroustrup - Make Simple Tasks Simple! (Vector vs List)

Game Engine Architecture

EASTL Design - Linked Lists

Master the mechanics of singly and doubly linked lists in C++. We dissect std::list and std::forward_list, explain O(1) insertions and splicing, and expose the hardware penalty of pointer chasing.

The Mechanics of Linked Lists

Understanding the Basics

Practical Applications

Common Mistakes

Next Steps

Additional Resources

Assessment Preparation

Practical DSA