Arrays

An array stores a fixed number of equal-size elements in one contiguous block, giving constant-time access by index.

The contiguous block

An array is the most basic data structure: a run of memory holding n elements of identical size laid out back to back. If the block starts at address base and each element occupies s bytes, then element i lives at base + i*s. That single multiply-and-add is why reading or writing an element by index takes constant time, written O(1), no matter how large the array is.

What is cheap and what is not

Random access is the array's superpower. Its weakness is structural change. Inserting or deleting anywhere except the end forces every later element to shift by one slot, which is O(n) work. Growing beyond the reserved capacity means allocating a larger block and copying everything across.

• Access by index: O(1)
• Update by index: O(1)
• Search for a value (unsorted): O(n)
• Insert or delete in the middle: O(n)

Row-major and cache behaviour

Multi-dimensional arrays are flattened into one dimension. In row-major order a matrix element at (r,c) with W columns sits at r*W + c. Because neighbouring elements are physically adjacent, iterating in memory order lets the CPU cache prefetch efficiently. Walking a matrix column by column in a row-major layout defeats the cache and runs much slower even though the operation count is identical.

When to reach for an array

Use an array when the number of elements is known or bounded, when you index by position often, and when you iterate in order. When frequent insertion and deletion in the middle dominate, a linked list or a tree is usually a better fit. Most higher-level structures, including heaps and hash tables, are built on top of plain arrays.