How arrays work
One block of memory, fixed-size slots, and the arithmetic that makes arr[i] instant.
Big idea
An array is one contiguous block of memory divided into equal-sized slots. Because every slot is the same size, the address of arr[i] is a single calculation — so reading or writing any index is O(1), no matter how long the array is.
The address arithmetic
Say an array of 32-bit integers (4 bytes each) starts at memory address 1000. Then:
| Index | Address |
|---|---|
| 0 | 1000 |
| 1 | 1004 |
| 2 | 1008 |
| i | 1000 + 4 × i |
To read arr[7], the computer computes 1000 + 4 × 7 = 1028 and goes straight there. It doesn't walk past items 0–6. That's what random access means: any position costs the same.
This is also why arrays are 0-indexed in most languages: the index is the offset from the start.
Watch it
Why contiguous is fast in practice
When the CPU reads one slot, it pulls a whole cache line (typically 64 bytes — sixteen 4-byte ints) into fast cache. So the next 15 reads in a left-to-right scan are almost free. A linked list, whose nodes are scattered across memory, gets no such help. Two O(n) scans can differ several-fold in real speed because of this.
The cost table
| Operation | Cost | Why |
|---|---|---|
Read / write arr[i] | O(1) | one address calculation |
| Scan all items | O(n) | touch each once |
| Search for a value (unsorted) | O(n) | may have to check every slot |
| Search for a value (sorted) | O(log n) | binary search |
| Insert / delete at the end | O(1) amortized | see next lesson |
| Insert / delete at the front or middle | O(n) | shift everything after it |
Words you'll see in problems
- Subarray — a contiguous run:
[2, 3, 4]in[1, 2, 3, 4, 5]. An array of n has n(n+1)/2 of them. - Subsequence — items in their original order, gaps allowed:
[1, 3, 5]. There are 2ⁿ. - Circular array — the item after the last is the first; index with
i % n. - 2D array — rows of arrays;
grid[r][c]. See matrix.
Confusing subarray with subsequence is one of the most common misreads: "maximum sum subarray" and "longest increasing subsequence" are very different problems.
Arrays in each language
nums = [5, 2, 8] # Python list: a dynamic array of references
nums.append(1) # amortized O(1)
nums[1] # 2Quick check
An array of 8-byte values starts at address 2000. What is the address of index 5?
In [4, 1, 7, 3], which of these is a subsequence but NOT a subarray?
What does inserting a value at index 0 of an array with n items cost?