Array Data Structure: Representation and Operations

Core Idea

Arrays store elements in contiguous memory locations, enabling O(1) random access by index. Insertion and deletion away from the end require shifting elements (O(n)). Understanding memory layout, cache locality, and resizing overhead is critical for performance.

How It's Best Learned

Implement insertion and deletion at different positions, measure performance, and reason about why access is fast (address arithmetic) while modification is slow. Compare empirically to linked lists.

Common Misconceptions

• Assuming all array operations are O(1).
• Forgetting the cost of array resizing on dynamic arrays.
• Not considering cache performance; O(1) operations may perform very differently in practice.

Explainer

You already know arrays from programming — you've used them to store lists of values and access elements by index. Now we examine *why* arrays behave the way they do by looking at how they are laid out in memory. An array allocates a single contiguous block of memory, with each element occupying a fixed number of bytes. When you request element at index *i*, the computer calculates the memory address using simple arithmetic: `base_address + i × element_size`. This single multiplication and addition is why array access is O(1) — no searching, no following pointers, just one address computation.

This contiguous layout also gives arrays an enormous hidden advantage: cache locality. Modern CPUs don't fetch individual bytes from main memory; they load entire cache lines (typically 64 bytes) at once. When you access array[0], the CPU loads array[0] through roughly array[15] (for 4-byte integers) into the fast L1 cache. Iterating through the array sequentially hits the cache almost every time, making array traversal far faster in practice than the O(n) notation alone suggests. This is why arrays often outperform linked lists even when both have O(n) traversal — the array's sequential memory access pattern plays to the hardware's strengths.

The cost shows up during insertion and deletion. If you insert an element at position 3 of a 1000-element array, every element from position 3 onward must shift one slot to the right — that's 997 copy operations, making insertion O(n) in the worst case. Deletion works the same way in reverse: removing an element leaves a gap that must be closed by shifting elements left. The only exception is operating at the end of the array, where no shifting is needed. Dynamic arrays (like Python's list or Java's ArrayList) add another consideration: when the array fills its allocated capacity, it must allocate a new, larger block of memory and copy everything over. This resizing is O(n) when it happens, but because the new block is typically double the old size, the amortized cost of appending remains O(1).

Understanding these tradeoffs — O(1) random access and excellent cache performance versus O(n) insertion and deletion — is the foundation for choosing between arrays and other data structures. When your workload is mostly reading and appending, arrays are hard to beat. When your workload involves frequent insertions and deletions at arbitrary positions, you'll want to consider linked lists or tree-based structures, which trade away contiguous memory for pointer-based flexibility.