Arrays: Numbered Lockers

A row of lockers

Picture a school corridor with lockers numbered 0, 1, 2, 3… all the same size, side by side. That is an array. Because every locker has the same width, Java can work out where locker i is with one sum: start + i × width. No searching – it jumps straight there. So a[i] is O(1), whether the array has 5 items or 5 million.

public class Main {
    public static void main(String[] args) {
        int[] lockers = new int[5];          // 5 lockers, all start at 0
        lockers[0] = 12;
        lockers[3] = 40;
        System.out.println("locker 3 holds " + lockers[3]);
        System.out.println("there are " + lockers.length + " lockers");

        String[] names = new String[3];      // object arrays start as null
        names[1] = "Asha";
        for (int i = 0; i < names.length; i++) {
            System.out.println(i + ": " + names[i]);
        }
    }
}

Output

locker 3 holds 40
there are 5 lockers
0: null
1: Asha
2: null

The catch: a fixed size

The corridor was built with exactly 5 lockers. There is no room for a 6th – the wall is in the way. A Java array has the same problem: new int[5] can never grow. To get more room you must build a new, bigger array and copy everything across:

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] small = {7, 8, 9};
        int[] bigger = new int[small.length * 2];      // twice the room
        for (int i = 0; i < small.length; i++) {
            bigger[i] = small[i];                       // copy item by item: O(n)
        }
        bigger[3] = 10;
        System.out.println(Arrays.toString(bigger));
    }
}

Output

[7, 8, 9, 10, 0, 0]

Remember: Array: reading or writing a[i] is O(1). Making it bigger means copying everything: O(n).

Common mistake: Using a[a.length]. The last locker is a.length - 1; going past it stops the program with ArrayIndexOutOfBoundsException.