An array is a contiguous block of memory divided into equal-sized slots, where any slot can be accessed in O(1) time using its integer index and the formula base_address + index × element_size.
An array is a row of labelled boxes in memory — every box is the same size and you can jump to any box in one step because you know exactly where it is.
Memory layout
All elements are stored one after another in a single contiguous block of memory. If a 32-bit integer takes 4 bytes and the array starts at address 1000, then element 0 is at 1000, element 1 at 1004, element 2 at 1008, and element i at 1000 + i⋅4. This is computed in one step — hence O(1) access.
#include <stdio.h>
int main() {
int arr[5] = {10, 20, 30, 40, 50};
/* arr[i] is identical to *(arr + i) */
printf("%d\n", arr[2]); /* 30 */
printf("%d\n", *(arr + 2)); /* 30 — same thing */
/* Print addresses to see contiguous layout */
for (int i = 0; i < 5; i++)
printf("arr[%d] at %p\n", i, (void*)&arr[i]);
/* Each address is exactly 4 bytes apart */
return 0;
}Complexity table
| Operation | Average | Worst | Notes |
|---|---|---|---|
| Access by index | O(1) | O(1) | Base + index * size — one computation |
| Search (unsorted) | O(n) | O(n) | Linear scan required |
| Search (sorted) | O(log n) | O(log n) | Binary search |
| Insert at end | O(1) amortised | O(n) | Occasional capacity doubling |
| Insert at index i | O(n) | O(n) | Must shift n-i elements right |
| Delete at index i | O(n) | O(n) | Must shift elements left |
| Space | O(n) | O(n) | Contiguous allocation |
Amortised: averaged over a sequence of operations.
Dynamic arrays
Static arrays are fixed-size. Dynamic arrays (Python list, Java ArrayList, C++ std::vector, Rust Vec) grow automatically. When the capacity is full, the implementation allocates a new block (typically 2× the size), copies all elements, and frees the old block. The amortised cost of append is O(1) because growth events are rare.
When to use an array
Use an array when you need fast random access by index, you know the size in advance (or are appending to the end), and cache performance matters. Arrays are the fastest sequential data structure due to memory locality — iterating them fills CPU cache lines with adjacent elements.
Amortised analysis: why append is O(1)
Over n appends to an initially empty dynamic array that doubles on overflow: total copy work = 1 + 2 + 4 + ⋯ + n/2 + n = 2n − 1 (geometric series). Cost amortised over n operations: (2n−1)/n < 2 = O(1). Python uses a growth factor slightly above 1 for small lists; Java ArrayList uses 1.5×; C++ std::vector requires at least doubling (standard specifies amortised O(1) push_back).
Cache lines and spatial locality
A CPU cache line is typically 64 bytes = 16 int32 values. When you access arr[0], the CPU loads a 64-byte cache line containing arr[0] through arr[15]. Accessing arr[1] next costs nothing (already in cache). Iterating an array has near-perfect spatial locality. Iterating a linked list (nodes scattered across the heap) has terrible locality — each node access is likely a cache miss costing ~60 ns vs ~1 ns for a cache hit. For n=10M elements, array iteration ≈ 10 ms; linked list iteration ≈ 1 second.
# CPython list growth: allocates more than needed
import sys
lst = []
prev = sys.getsizeof(lst)
for i in range(20):
lst.append(i)
size = sys.getsizeof(lst)
if size != prev:
print(f"Capacity grew at len={len(lst)}: {prev} -> {size} bytes")
prev = size
# Growth: 0, 4, 8, 16, 25, 35, 46, 58... (over-allocation pattern)Multi-dimensional arrays
A 2D array (matrix) can be stored in row-major order (C, NumPy default) or column-major order (Fortran, MATLAB). Row-major: element at row r, column c is at index r⋅cols + c. Column-major: c⋅rows + r. Iterating a row-major matrix row-by-row is cache-friendly; iterating column-by-column causes a cache miss per element. This is why matrix multiplication order matters for performance.
list is a dynamic array of object references. In Java, int[] is a static primitive array; ArrayList<Integer> is a dynamic array of boxed integers. In C, an array is a fixed-size block of primitives. The word "list" is ambiguous across languages.int arr[5]; sizeof(arr) = 20 (5 × 4 bytes). To get the element count: sizeof(arr)/sizeof(arr[0]). Once an array decays to a pointer (e.g. passed to a function), sizeof gives the pointer size (8 bytes on 64-bit), not the array size.ISO C17 array semantics
ISO C17 §6.3.2.1: an array type in most contexts is converted to a pointer to its first element ("array decay"). This means arrays are not first-class values in C — you cannot assign one array to another with =, or return an array by value from a function. §6.5.6 defines pointer arithmetic: E1[E2] is identical to *(E1 + E2). §6.2.6: accessing outside the bounds of an array is undefined behaviour — the compiler may assume this never happens and optimize accordingly (GCC with -O2 may eliminate "dead" bounds checks it proves can't be reached).
Dynamic array invariants (from CLRS)
Cormen et al. (CLRS, 4th ed.) §17.4 defines the dynamic table: when an array doubles, the amortised cost of n insertions is O(n) total. The potential function Φ = 2⋅num − size where num is element count and size is capacity. Each insert either costs O(1) actual (no overflow) with ΔΦ = 2, or costs O(n) actual (overflow: copy n elements) with ΔΦ = −size/2. Amortised cost = actual + ΔΦ = O(1) in both cases.
Cormen, T. H., Leiserson, C. E., Rivest, R. L. & Stein, C. (2022). Introduction to Algorithms (4th ed.), §17.4 — Dynamic tables. MIT Press. ISO C17 §6.3.2.1 (array decay), §6.5.6 (pointer arithmetic), §6.2.6 (undefined behaviour at out-of-bounds). Java Language Specification §10 — Arrays.