Arrays

A contiguous block of same-sized elements. Constant-time indexing, cache-friendly scans, and costly middle inserts.

Level: beginner

What is it?

An array stores elements one after another in memory. Because every element has the same size, the address of element i is base + i × size, so any element is reached in constant time. Dynamic arrays (Python list, Java ArrayList, C++ vector) grow by allocating a bigger block, copying, and doubling capacity, which makes appends O(1) amortized.

Why does it matter?

Arrays are the default sequence and the foundation for strings, heaps, hash tables, matrices, and buffers. Their contiguous layout is friendly to the CPU cache, so they often beat 'better' asymptotic structures in practice.

Mental model

A row of numbered mailboxes of equal size. You can jump to box 500 without opening the first 499. But to insert a new box at position 0 you must slide every other box one place over.

How it works

Index read and write are O(1): address = base + i × element size.
Search in an unsorted array is O(n); in a sorted array binary search makes it O(log n).
Insert or delete in the middle is O(n) because later elements shift.
Append at the end is O(1) amortized for a dynamic array; each resize copies all elements.
Contiguous memory means sequential scans use the cache well.
Bounds matter: reading outside the array is an error in safe languages and undefined behavior in C.

Steps

Allocate a contiguous block
Compute base + i × size
Read or write the slot
On overflow allocate double and copy
Shift elements for middle inserts

Code example: What is cheap and what is not

a = [10, 20, 30]
a[1] = 25            # O(1): index write
a.append(40)         # O(1) amortized
a.insert(0, 5)       # O(n): every element shifts right
print(a)             # [5, 10, 25, 30, 40]
print(30 in a)       # O(n): linear scan -> True

Complexity and trade-offs

Time: Index O(1); search O(n); insert/delete O(n); append O(1) amortized

Space: O(n)

Trade-offs

Best locality and the smallest overhead per element
Middle inserts and deletes are expensive
Fixed-size arrays cannot grow; dynamic arrays pay for occasional copies

Real-world usage

The default list of things in nearly every program
Buffers, pixel data, and matrices
The backing store for heaps, hash tables, and stacks

Common mistakes

Using insert(0, x) or pop(0) in a loop and getting O(n²).
Off-by-one errors at the ends (n elements, indexes 0 to n-1).
Assuming a resize never happens and holding a pointer into the old block.

Interview questions

Why is array indexing O(1)?

Elements are contiguous and equally sized, so the address of element i is the base address plus i times the element size — one multiplication and one addition regardless of n.

Why is append amortized O(1) for a dynamic array?

When full, the array allocates double the capacity and copies everything, costing O(n). But that happens after n cheap appends, so the average cost per append stays constant.

Array versus linked list?

Arrays give O(1) indexing and cache-friendly scans but O(n) middle inserts. Linked lists give O(1) insert at a known node but O(n) access and poor locality. In practice arrays win most of the time.