Memory Layout of Vectors and Linked Lists

The update loop scans every stored MarketUpdate. Its next memory address depends on the container.

With std::vector<MarketUpdate>, the next update sits beside the current one. With std::list<MarketUpdate>, the current node contains a pointer to wherever the next node was allocated. That difference changes what the processor must fetch during the scan.

Contiguous vs scattered memory

A vector stores all of its elements in one contiguous block. If an update begins at address p, the next one begins at p + sizeof(MarketUpdate). As the loop advances, it reads a predictable sequence of addresses.

A list lays out the same updates differently. Each update sits inside a separate node alongside pointers to the previous and next nodes. Those nodes are allocated separately, so two consecutive updates in the list can live far apart in memory.

During the vector scan, the processor fetches memory in blocks rather than one field at a time. Reading one update often brings bytes from the following updates into the cache. The regular address pattern also lets the processor start fetching upcoming data before the loop asks for it.

In comparison, the list cannot reveal the next node's address until the loop reads the current node's pointer. If that next node is missing from the cache, the processor has to fetch another block before it can continue. Repeating this sequence—read a node, find the next address, fetch the next node—is called pointer chasing.

The vector scan moves forward through memory. The list scan has to follow a pointer at every step.

C++ example

Here are the two scans side by side. The loop bodies do exactly the same work.

Copy
struct MarketUpdate {
    std::uint64_t sequence;
    char symbol[8];      // "AAPL"
    std::int64_t price;  // 19010 = USD 190.10
    std::int32_t qty;    // 100
};

// The vector stores adjacent elements.
void scan_vector(const std::vector<MarketUpdate>& updates) {
    for (const MarketUpdate& u : updates) {
        apply_update(u);
    }
}

// The list stores elements in separate nodes.
void scan_list(const std::list<MarketUpdate>& updates) {
    for (const MarketUpdate& u : updates) {
        apply_update(u);
    }
}

The difference is hidden inside the iterators. The vector iterator advances to the object beside the current one. The list iterator reads a pointer from the current node and follows it to another address. That extra dependency appears on every iteration of the list scan.

This comparison is about full scans. A list can still be useful when you need stable references or want to splice or erase a known node without moving the remaining elements. For a hot path that repeatedly reads every update, the vector's layout matches the job better.

Vector of pointers

There is one version that is easy to misread: std::vector<MarketUpdate*>. The vector still uses contiguous storage, but its elements are pointers. The MarketUpdate objects remain wherever they were allocated.

The loop can read those pointers in sequence. It then has to visit the address stored in each one, and that address may lead to an object elsewhere in memory. If the object is missing from the cache, the dereference delays the next step of the scan. A plain std::vector<MarketUpdate> avoids that lookup because the objects themselves sit together.

The pointers sit together in the top row, while their objects occupy separate locations below.

In interviews

• "Why is a vector scan usually faster than a list scan when both are O(n)?" → "The vector keeps its elements together, so the processor can fetch them in a predictable sequence. The list has to follow a pointer to find each next node."
• "When would you use std::list?" → "I would consider it when I need stable references or constant-time splicing of known nodes and do not spend the hot path scanning the list."
• "Does a vector of pointers give locality to its objects?" → "The pointers are contiguous, but the objects can still be scattered. Each dereference may send the processor to a different part of memory."

The next article examines the cache lines behind these memory accesses.