Call sum([3, 1, 4, 1, 5]) - a new frame is pushed onto the call stack.
primitives are shown in Variables.
Real execution, step by step. Press play or scrub with the controls - every variable and array index updates live.
Start here: what this lesson is for
An array is the first real data structure anyone meets, and almost everyone learns it as 'a list of things' and stops there. That description is not wrong, but it explains none of the behaviour that actually matters.
By the end of this lesson you will understand one physical fact - that an array's items sit side by side in memory - and you will be able to derive every strength and weakness of arrays from it, without memorising a table.
That includes why reading item 500 is instant, why inserting in the middle is slow, why an array cannot grow, and why arrays beat linked lists in practice even when the theory says otherwise. One fact, all of it.
- What you need first: lesson 1, so you can count steps.
- What you will be able to do: predict the cost of any array operation from first principles.
- How long: about 16 minutes, plus two problems at the end.
- data structure
- - a way of arranging data in memory that makes some operations cheap and others expensive
One long shelf
An array is the simplest data structure there is, and understanding it deeply pays off for everything that comes later. Picture a single long shelf, divided into equal-sized slots, numbered from 0. Every slot is the same width, and they sit right next to each other in memory with no gaps. That 'no gaps, equal width' rule is the whole secret behind an array's every strength and weakness.
Because the slots are identical and touching, the computer finds slot number i with a single multiplication: the start of the shelf, plus i times the slot width. It doesn't walk the shelf - it jumps straight there. That's why reading arr[0] and arr[500] cost exactly the same. One jump either way. We call that cost O(1), constant time.
Imagine it like this: Numbered lockers in a hallway. To open locker 500 you don't check lockers 1 to 499 - you walk straight to it, because you know exactly how far down the wall it sits.
- array
- - a fixed row of equal-sized, numbered slots sitting together in memory
- index
- - a slot's number, starting at 0 - the address the computer jumps to
- O(1)
- - constant time - the work doesn't grow with the size of the data
The catch: inserting in the middle
That same 'no gaps' rule is also the array's weakness. Suppose you want to insert a new value in the middle. There's no room - the slots are packed tight. So every element after your insertion point must shuffle one slot to the right to open a space. For an array of n items, that's up to n moves: O(n).
Deleting from the middle is the mirror image: everything after the gap slides left to close it. This is the trade every data structure makes. Arrays buy you instant reads by giving up cheap inserts. Later chapters build structures - linked lists, trees - that make the opposite bargain.
Adding or removing at the end of an array is usually O(1) - nothing sits after it to shuffle. That's why 'append' is cheap and 'insert at the front' is not.
- Read or write arr[i] by index: O(1), instant, any position
- Insert or delete in the middle: O(n), everything after it shuffles
- Add or remove at the END: usually O(1) - nothing to shuffle
- contiguous
- - packed together with no gaps - what makes indexing instant and inserting slow
Why an array cannot simply grow
Here is a consequence people meet as a bug rather than as a concept. An array's size is fixed the moment you create it, and this is not a limitation someone forgot to remove - it follows directly from the shelf.
The items must stay adjacent, because adjacency is what makes the address arithmetic work. To add an eleventh item to a ten-item array, the memory immediately after it would have to be free - and it usually is not, because something else is already living there.
So growing an array means allocating a bigger one and copying everything across. That copy is O(n), and it is why int[] in Java has a fixed length while ArrayList does not.
ArrayList hides this by keeping spare capacity and doubling when it runs out. Most adds are O(1) because there is room; occasionally one triggers a doubling copy costing O(n). Spread across all the cheap adds, the average stays constant - the amortised O(1) you met in the hashing chapter, arriving here for the same reason.
int[] fixed = new int[10]; // fixed[10] = 99; -> ArrayIndexOutOfBoundsException. The shelf ends. List<Integer> list = new ArrayList<>(); // capacity 10 to begin with for (int i = 0; i < 40; i++) list.add(i); // watch WHEN it copies
add #1..#10 capacity 10 no copy add #11 capacity 10 -> 15, copy 10 items add #16 capacity 15 -> 22, copy 15 items add #23 capacity 22 -> 33, copy 22 items add #34 capacity 33 -> 49, copy 33 items 40 adds, 4 copies, 80 items copied in total average cost per add: still O(1)
- capacity
- - how many items an ArrayList can hold before it must resize
- amortised O(1)
- - expensive rarely, cheap usually, so the average is constant
Recap: one fact explains everything
Everything in this lesson came from a single physical property: array items sit next to each other in memory. Nothing else had to be memorised.
Because they are adjacent, the machine can calculate any item's address instead of searching for it, so reading by index is O(1) no matter how large the array is.
Because they must stay adjacent, inserting or deleting in the middle has to shift everything after the gap, so both are O(n).
Because adjacency cannot be extended into memory someone else owns, arrays cannot grow, and growable lists must copy.
And because adjacent data is fetched together into cache, arrays are quick in ways Big-O does not show - which is why they usually beat linked lists in practice even where the theory suggests otherwise. You will see that measured in chapter 6.
- Read by index: O(1) - the address is computed, not searched
- Insert or delete in the middle: O(n) - everything after must shift
- Add or remove at the END: O(1) - nothing has to move
- Fixed size; growable lists copy into a bigger array and double
- Adjacency also buys cache locality, which Big-O never shows
Your turn
Reading is not learning. Open each one in NeonFlow and watch your own code run, step by step.
Feel the shift cost
Insert at the front of an array a thousand times, then at the end a thousand times, counting how many elements move each way. Predict which is worse and by roughly how much before you run it.
import java.util.*;
public class ShiftCost {
static long moves = 0;
// insert value at index 0, shifting everything right
static void insertFront(int[] a, int size, int value) {
for (int i = size; i > 0; i--) {
a[i] = a[i - 1];
moves++; // count every element that MOVED
}
a[0] = value;
}
static void insertEnd(int[] a, int size, int value) {
// TODO: add at the end. How many elements move?
a[size] = value;
}
public static void main(String[] args) {
int[] a = new int[2001];
moves = 0;
for (int i = 0; i < 1000; i++) insertFront(a, i, i);
System.out.println("front inserts, elements moved: " + moves);
moves = 0;
int[] b = new int[2001];
for (int i = 0; i < 1000; i++) insertEnd(b, i, i);
System.out.println("end inserts, elements moved: " + moves);
}
}Why arr[500] is instant
Write the address calculation the machine actually performs. If an array starts at address 1000 and each int takes 4 bytes, work out where item 500 lives - then confirm it takes the same arithmetic for item 0 and item 999,999.
public class AddressMath {
static final int START = 1000; // where the array begins in memory
static final int SIZE = 4; // bytes per int
static int addressOf(int index) {
// TODO: one line. start + index * bytes-per-item
return 0;
}
public static void main(String[] args) {
System.out.println("item 0 -> " + addressOf(0));
System.out.println("item 500 -> " + addressOf(500));
System.out.println("item 999999 -> " + addressOf(999999));
System.out.println("all three took the same one multiply and one add");
}
}