Contiguous and scattered data

Two ways to arrange data

Once you know that memory is a row of numbered bytes, there are only two basic ways to keep a collection of values in it.

Contiguous data sits in one unbroken block: the first value, then the next, then the next, with nothing in between. Arrays, strings and the fields of a struct are laid out this way.

Scattered data lives in separate pieces, each allocated on its own, joined by pointers. A linked list, a tree and most object graphs are laid out this way.

Nearly every data structure in this track is one of these, or a mix of both. A hash table is an array of slots; a linked list is a chain of nodes; a B-tree is a tree of nodes, each holding an array. The layout decides what is cheap and what is expensive, so it is worth seeing each one at the level of addresses.

Contiguous: the address is a formula

If every element has the same size and they sit side by side, the address of element i is simple arithmetic:

address(i) = base + i × element_size

In the trace above, an array of 8-byte numbers starts at 0x1000, so item 3 is at 0x1000 + 3 × 8 = 0x1018. The processor computes that with one multiply-add, often folded into the load instruction itself, and reads the value. It doesn't matter whether the array has 4 elements or 4 billion: reaching any element costs the same. This is what "arrays have constant-time access" means, and it is also why indexes start at 0, since element 0 is at the base address itself.

Structs and objects use the same idea for their fields. A struct with a 4-byte id followed by an 8-byte price puts each field at a fixed offset from the start of the struct, so reading item.price is "base address plus 8". The compiler sometimes inserts a few bytes of padding so that each field starts at an address that is a multiple of its size, because processors load aligned values fastest.

The price of contiguity is rigidity. The block has a fixed size once it is allocated, and there is no room between elements. Growing an array means allocating a bigger block and copying everything; inserting in the middle means shifting everything after the insertion point. The arrays module covers both.

Scattered: the address is a pointer

A program that creates objects one at a time asks the memory allocator for space each time, and the allocator hands back whatever block fits, wherever it is. Objects created one after another often end up near each other, but nothing guarantees it, and after a program has run for a while and freed memory here and there, consecutive allocations can land far apart.

So a linked structure records the connections explicitly. Each list node carries the address of the next one, as in the trace's second half. To reach item 3 of the list, the processor loads node 0 to read where node 1 is, loads node 1 to read where node 2 is, and so on. These are dependent loads: each one needs the result of the one before it, so they can't overlap. Reaching item i takes i steps, and each step waits for memory.

In exchange, scattered data is flexible. Adding a node anywhere means allocating one node and rewriting two pointers, with no copying, and the structure never needs one large free block.

What high-level languages actually do

Most languages choose a layout for you, and the choice is often not the obvious one.

• Python: a list is a contiguous array of 8-byte references, and every element is a separate object somewhere else on the heap. An integer object takes about 28 bytes, so a list of a million integers costs roughly 36 MB. The array module and NumPy store raw numbers contiguously instead: a million 32-bit integers in 4 MB.
• Java: an int[] packs the numbers themselves. An ArrayList<Integer> holds a contiguous array of references to separately allocated Integer objects, which costs several times more memory and an extra pointer to follow for each element.
• JavaScript: engines such as V8 store small integers and doubles directly in the array when every element has the same kind, and fall back to references when the types are mixed.
• C, C++, Go and Rust: an array or a slice of structs holds the structs themselves, contiguously. A slice of pointers holds only pointers.

The pattern is the same everywhere: a contiguous array of references is fast to index but still scatters the actual values. When performance matters, check which kind you have.

Choosing between them

The table makes the two look evenly matched, as if each wins half the rows. On real hardware they are not, because the cost of "one pointer to follow" is far higher than it looks. The next lesson explains why: the processor fetches memory in blocks, and contiguous data uses every byte of each block while scattered data often uses only a few.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Contiguous and scattered data from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

# array: compute the address
addr = base + i * 8
value = load(addr)
# linked list: follow the chain
node = head
for _ in range(i):
    node = node.next
value = node.value

#include <vector>
#include <algorithm>
 
long long processArrayInvariants(std::vector<int>& nums) {
    long long acc = 0;
    int lo = 0, hi = static_cast<int>(nums.size()) - 1;
    while (lo <= hi) {
        acc += nums[lo];
        if (lo < hi) acc += nums[hi];
        ++lo; --hi;
    }
    return acc;
}

public class ArrayInvariantSolver {
    public static long processArrayInvariants(int[] nums) {
        long acc = 0;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            acc += nums[lo];
            if (lo < hi) acc += nums[hi];
            lo++; hi--;
        }
        return acc;
    }
}

def process_array_invariants(nums: list[int]) -> int:
    acc = 0
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        acc += nums[lo]
        if lo < hi:
            acc += nums[hi]
        lo += 1
        hi -= 1
    return acc

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.