Arrays & Dynamic Arrays

The array is the most used data structure in every language. Knowing exactly what it is good and bad at saves you from slow code that looks innocent.

beginner⏱ 10 min read

←Builds on

0Big-O & Growth RatesAmortised O(1) push_back is a Big-O argument about many operations taken together.

Leads to→

1Hash Tables: Sets & MapsA hash table is an array of buckets indexed by the hash of the key.1Prefix Sums, Two Pointers & Sliding WindowPrefix sums are a second array where any range sum is two O(1) lookups.2Elementary SortsEvery elementary sort swaps elements in place inside one array.2Counting SortCounting sort uses the keys themselves as array indices.3Linked ListsA linked list trades the array's O(1) indexing for O(1) insertion anywhere.3Stack (LIFO) & Expression EvaluationA stack is a dynamic array that only pushes and pops at its back.5Binary Heap & Priority QueueA heap lives in an array: the children of i sit at 2i+1 and 2i+2.6Graph RepresentationsAn adjacency list is an array of dynamic arrays, one per vertex.9GCD & the Sieve of EratosthenesThe sieve is a boolean array indexed by the numbers themselves.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01One block of memory

An array stores its elements side by side in one contiguous block of memory. Every element has the same size, for example 4 bytes for an int.

That makes finding any element pure arithmetic. If the array starts at address base, then

address of a[i] = base + i × size

One multiplication and one addition, no matter whether i is 3 or 3 million. This is random access in O(1), the array's superpower.

Contiguous memory has a second bonus: when the CPU loads a[i], it also pulls its neighbours into the cache, so scanning an array from left to right is very fast in practice.

02The weakness: inserting in the middle

Because elements must stay side by side, there are no gaps to use. To insert a value at index i, every element from i to the end has to shift one place right first. Deleting from the middle is the mirror image: everything after the hole shifts left.

In the worst case (inserting at the front) that is n moves, so insert and erase in the middle cost O(n).

Searching for a value in an unsorted array is also O(n): you have to look at elements one by one. Only the end of the array is cheap to change, which is why the most common operation is appending.

03Dynamic arrays: size and capacity

A fixed array cannot grow. A dynamic array (C++ vector, Java ArrayList, Python list) fakes growth by keeping two numbers:

size: how many elements you stored
capacity: how many fit in the block it allocated

While size < capacity, push_back just writes into the next free slot: O(1). When the block is full, the vector allocates a new block twice as big, copies every element across, frees the old one, and then writes. That one push costs O(n).

If you know the final size in advance, call reserve(n) so it never has to copy. And be careful: after a reallocation, old pointers and iterators into the vector point to freed memory.

04Amortized O(1): why doubling is cheap

Some pushes cost O(n), so is push_back slow? Look at the total cost of n pushes instead of the worst single one.

Copies happen only when the size passes a power of two, and each time the vector copies everything it has: 1, 2, 4, 8, … up to n. That sum is less than 2n. Add the n ordinary writes and n pushes cost less than 3n steps in total.

Spread over n operations, that is at most 3 steps each: amortized O(1). The expensive copies are rare enough that they average out.

This only works because the capacity multiplies. If the vector grew by a fixed +10 slots each time, it would copy 10, 20, 30, … elements, about n²/20 in total, and each push would be O(n) on average.

Orange spikes are the copies on pushes 2, 3, 5, 9 and 17.

Cost at a glance

Access a[i]O(1)

push_backO(1) amortized

Insert / erase in the middleO(n)

Search (unsorted)O(n)

Remember

Contiguous memory turns indexing into arithmetic, so a[i] is O(1).
Inserting or erasing in the middle shifts the rest of the array and costs O(n).
Doubling the capacity makes n push_backs cost under 3n steps: amortized O(1) each.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Count the shift steps during the insert: try your own array and insert at index 0, then at the end.

Interactive visualizerfocus here, then space ← →

Array in memory (element = 4 bytes)

0x10012[0]0x1045[1]0x1088[2]0x10c23[3]0x1109[4]0x11416[5]

An array is one contiguous block. It starts at base address 0x100, and each element takes 4 bytes.

Pseudocode

 1 array elements sit in contiguous memory 2 a[i]  →  address = base + i * elementSize   // O(1) 3 insert(i, x): shift a[i..] right by one      // O(n) 4   then write a[i] = x 5 push_back(x): append; vector doubles capacity when full

1 / 1

Check

Three questions. Pick an answer to see why.

An int array starts at address 1000 (4-byte ints). What is the address of a[25]?

You build a list of n items by inserting each new item at the FRONT of a vector. What is the total cost?

Why does a vector multiply its capacity instead of adding a fixed number of slots?

Practice

Real problems to lock it in, easiest first.

LeetCodeConcatenation of Array beginner↗CSESIncreasing Array beginner↗LeetCodeRemove Element beginner↗LeetCodeMove Zeroes beginner↗LeetCodeRotate Array intermediate↗