Array Fundamentals

An array stores elements in a contiguous block of memory. Given a base address $b$ and element size $s$, the address of index $i$ is $b + i \cdot s$. This arithmetic is constant time, so reading or writing any element is $O(1)$.

Why contiguity matters

CPUs prefetch and cache adjacent memory. Iterating through an array hits the cache on almost every access, making it dramatically faster than a structure with the same number of items scattered across the heap (like a linked list). On modern hardware, this constant factor often beats theoretically "better" data structures.

Insertion and deletion

Random-access reads are $O(1)$, but inserting or deleting in the middle is $O(n)$ because every following element must shift. Appending at the end is $O(1)$ amortized for dynamic arrays (assuming the buffer doesn't need resizing on this call).

Fixed vs dynamic

Static arrays (C arrays, Java's int[]) have a size fixed at allocation. Dynamic arrays (vector, ArrayList, Python list) grow by reallocating to a larger buffer when full — usually doubling. Doubling gives amortized $O(1)$ appends but means at any moment you may be using up to 2x the space you strictly need.

Common pitfalls

Off-by-one errors at boundaries, integer overflow on indices in very large arrays, and forgetting that "shrinking" a Python list doesn't actually free the buffer. In C-family languages, missing bounds checks lead to security bugs; this is why bounds-checked languages (Python, Java, Rust) catch these at runtime or compile time.