Lesson 2.1 · Arrays
How Arrays Work
Why reading a[i] is instant, why inserting in the middle is slow, and how dynamic arrays like ArrayList grow.
12 min
Think of it like this
An array is a row of identical boxes in a warehouse, numbered from 0. Because every box is the same size and they're side by side, the worker can walk straight to box 731 by measuring: start + 731 × box width. That's why a[i] takes the same time for any i.
1.Contiguous memory and O(1) access
An int[] of length n is one block of memory holding n integers side by side. The address of a[i] is start + i × 4 bytes, so any element is reached in one step: O(1) random access.
That same layout is why arrays are cache-friendly: reading a[i] loads its neighbours into the CPU cache too, so a left-to-right loop is very fast in practice.
2.Insertion and deletion cost O(n)
To insert a value at index 2, every element from index 2 onwards must shift one place right to make room. In the worst case (inserting at the front) that's n moves. Deleting works the same way in reverse.
Appending at the end is cheap only if there's spare room, which is exactly what dynamic arrays arrange.
a = [4, 7, 2, 5, _]Step 1/5We want 9 at index 1, but 7 is already there. Everything from index 1 must move right first.
3.Dynamic arrays (ArrayList)
Java arrays have a fixed size. ArrayList hides a bigger array inside and keeps a size counter. add writes into the next free slot in O(1). When the inner array is full, it allocates one about 1.5× bigger and copies everything over: O(n) for that one call, but rare enough that the average stays O(1) (amortised).
Quick check
Which is faster on a list of a million items: list.remove(0) or list.remove(list.size() - 1)?
Remember
- Index access is O(1) because elements are side by side.
- Insert or delete in the middle is O(n) because of shifting.
- ArrayList.add at the end is O(1) amortised.
- Left-to-right loops over arrays are cache-friendly and fast.
Common mistakes
- Calling
list.add(0, x)orlist.remove(0)inside a loop (O(n²) total). - Reading
a[a.length], which is one past the end.
Words used in this lesson
- Contiguous
- Next to each other in memory, with no gaps.
- Random access
- Jumping straight to any position without walking from the start.
- Dynamic array
- An array-backed list that grows automatically, like ArrayList.