Array fundamentals

An array stores its elements in one contiguous block of memory. Because every slot has the same size, element i lives at address base + i × slotSize: one multiplication and one addition, independent of the array's length. That is why reading a[i] is O(1).

Compare reading element k from an array with reaching element k in a linked list, which has to follow k references.

1int[] a = {10, 20, 30, 40};
2int x = a[2];      // base + 2 * 4 bytes: one computed address, one read
3// a linked list needs 2 hops to reach its third node

1static int getFromArray(int[] arr, int k) {
2    return arr[k];                      // address = base + k * 4: one memory read
3}
4
5static int getFromList(Node head, int k) {
6    Node cur = head;
7    for (int i = 0; i < k; i++) {
8        cur = cur.next;                 // pointer chase: one read per hop
9    }
10    return cur.value;
11}

Java arrays are zero-based: the first element is a[0] and the last is a[a.length - 1]. Zero fits the address formula, since the offset of the first element is 0 slots from the base. Indexing outside 0 to length - 1 throws ArrayIndexOutOfBoundsException; Java checks every access.

Off-by-one errors almost always come from using <= where < is needed, or from forgetting that the last valid index is length - 1.

1int[] a = new int[5];
2for (int i = 0; i < a.length; i++) a[i] = i * i;   // i runs 0..4
3// a[5] throws ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5

A Java array's length is its capacity: it is fixed when the array is created and never changes. A program often uses only part of the array, so it keeps a separate size variable for how many slots hold real data. Dynamic arrays such as ArrayList wrap exactly this pair.

In the animation, filled slots are the size and the empty slots are the spare capacity.

1int[] data = new int[8];   // capacity 8
2int size = 0;              // nothing stored yet
3data[size++] = 42;         // size 1
4data[size++] = 7;          // size 2: data.length is still 8

1void add(int x) {
2    if (size == data.length) {                        // buffer is full
3        data = Arrays.copyOf(data, newCapacity());     // allocate bigger, copy size elements
4    }
5    data[size++] = x;
6}
7int removeLast() {
8    int x = data[--size];
9    if (size <= data.length / 4) data = Arrays.copyOf(data, Math.max(1, data.length / 2));   // optional shrink
10    return x;
11}

Reading is x = a[i] and writing is a[i] = x. Both are O(1) and touch exactly one slot. For primitive arrays the value itself is stored in the slot; for object arrays the slot holds a reference, so writing replaces the reference, not the object.

Arrays are mutable and shared by reference: a method that receives an array can modify the caller's data.

1int[] a = {1, 2, 3};
2a[1] = 20;                 // write: {1, 20, 3}
3int y = a[1] + a[2];       // two reads: 23
4static void zeroFirst(int[] arr) { arr[0] = 0; }   // the caller's array changes

Visit every element with an indexed for loop when you need the index or want to write, with the enhanced for when you only read, and with Arrays.stream for pipelines. Iterating the whole array is O(n). Prefer iterating forward; it matches how memory is laid out.

Use the indexed form whenever you write to the array. The loop variable of an enhanced for is a copy.

1int[] a = {4, 8, 15};
2for (int i = 0; i < a.length; i++) a[i] *= 2;      // indexed: can write
3int sum = 0;
4for (int x : a) sum += x;                           // enhanced: read only (x is a copy)
5int total = Arrays.stream(a).sum();                 // stream: 8 + 16 + 30 = 54

On a 64-bit HotSpot JVM an array object has a 12-byte header plus a 4-byte length, so 16 bytes of overhead, followed by the elements, and the total is rounded up to a multiple of 8. An int[n] therefore needs about 16 + 4n bytes. An Integer[n] stores references (4 bytes each with compressed pointers) and each Integer is a separate 16-byte object.

Primitive arrays are much smaller and denser than arrays of wrappers.

Memory is loaded into the CPU cache in 64-byte lines, which hold 16 ints. Reading a[0] brings a[0..15] along, so the next 15 reads are cache hits. Sequential array traversal therefore runs close to memory bandwidth, while pointer-chasing structures miss the cache on nearly every step.

Run the simulator: row-order traversal of a 2D array reuses each loaded line, column order throws lines away.

1int sumRowMajor(int[][] m) {                  // inner loop walks along a row
2    int sum = 0;
3    for (int r = 0; r < m.length; r++)
4        for (int c = 0; c < m[0].length; c++) sum += m[r][c];
5    return sum;
6}
7int sumColumnMajor(int[][] m) {               // inner loop jumps down a column
8    int sum = 0;
9    for (int c = 0; c < m[0].length; c++)
10        for (int r = 0; r < m.length; r++) sum += m[r][c];
11    return sum;
12}