Array

An array is the simplest and most fundamental data structure in computing: a contiguous block of memory indexed by integer positions. Every element occupies the same amount of space, and the address of any element can be computed in constant time from its index and the base address. This predictability makes the array the substrate upon which virtually all other data structures are built — the hash table scatters its buckets across memory, but each bucket is an array; the graph stores its adjacency information in arrays of pointers or edge lists; even the linked list, which prides itself on non-contiguity, is typically implemented as an array of nodes when performance matters.

The array's simplicity is deceptive. It is not merely a container; it is a contract between logical addressability and physical contiguity. The programmer thinks in indices; the machine thinks in cache lines. When the programmer requests element 0, then element 1, then element 2, the hardware loads an entire cache line from memory into the processor — and because the array is contiguous, the next several requests are satisfied from the cache without additional memory accesses. This is spatial locality, and the array is its most perfect realization. No other data structure can match the array's cache efficiency because no other data structure makes the same commitment to physical adjacency.

The Tyranny of Contiguity

The array's strength is also its prison. Insertion and deletion are O(n) operations because contiguity must be preserved: inserting an element at position i requires shifting all elements from i to n−1 one position forward. Deleting requires shifting backward. The array does not forgive fragmentation; it does not accommodate growth gracefully. When an array reaches its allocated capacity, the entire block must be copied to a larger region of memory — a traumatic event for cache locality that can stall the processor for hundreds of cycles.

This trade-off — fast random access and iteration against expensive mutation — is not accidental. It is a structural commitment that shapes the systems built upon it. A database that stores its rows as arrays makes table scans fast but updates slow. A scientific computing framework that represents matrices as arrays of arrays makes element-wise operations trivial but sparse matrices wasteful. The array is not a neutral container. It is an epistemic frame that privileges access patterns over modification patterns, reading over writing, spatial coherence over temporal flexibility.

Arrays and Parallelism

The array's contiguous layout makes it the natural data structure for SIMD (Single Instruction, Multiple Data) operations and vector processors. When a modern CPU executes a vector instruction — adding four floating-point numbers in parallel, for instance — it loads a contiguous block of memory into a wide register. The array's layout guarantees that these four elements are physically adjacent and can be fetched in a single memory transaction. Strided access — jumping through memory at regular intervals — is still possible, but it degrades performance because each vector load crosses cache line boundaries.

This connection between array layout and parallel execution has profound implications for the design of high-performance systems. Memory alignment — ensuring that array boundaries align with cache line boundaries and page boundaries — can determine whether a loop achieves its theoretical peak performance or stalls on every iteration. The programmer who ignores alignment is not merely leaving performance on the table; they are violating the contract between the array and the substrate, and the hardware punishes this violation with latency.

The array is the most successful data structure in the history of computing not because it is the most powerful, but because it is the most honest. It makes a single, radical commitment — contiguity — and derives every one of its properties from that commitment. Other data structures offer more flexibility, but they pay for it in cache misses, pointer chasing, and unpredictable memory access patterns. The array does not apologize for its rigidity. It is the foundational contract of computing, and every system that deviates from it pays a price that compounds with scale. The programmer who chooses a linked list over an array for a workload dominated by sequential access has not made a design decision; they have made a category error.