Arrays

An array is a fixed-length block of memory holding elements of one type, laid out end to end. Every other structure in this track is either built on one or defined by contrast with one.

The one idea

Because the elements are the same size and contiguous, the address of any element is arithmetic:

address(i) = base + i * elementSize

One multiply, one add. That is why values[999_999] costs exactly what values[0] costs — O(1), no search involved. This is called random access, and it is the array's entire advantage.

int[] values = new int[1000];

Two things Java does here that C does not. Every element is initialised — 0 for numeric types, false for boolean, null for references — so there is no reading of uninitialised memory. And every access is bounds-checked, so a bad index is an ArrayIndexOutOfBoundsException rather than silently reading whatever was next in memory. The check costs a little; the JIT eliminates most of them in loops it can prove safe.

The costs

Insert and delete are O(n) for a physical reason, not a bookkeeping one. There is no space between elements, so making room means moving everything after the gap:

System.arraycopy(items, index, items, index + 1, size - index);
items[index] = item;

System.arraycopy is an intrinsic — the JVM compiles it to a block memory move, far faster than the loop you would write. It is still O(n).

The fixed length is the problem

An array's length is decided at creation and can never change. That is not an API limitation; a longer array is a different block of memory. Growing one means allocating a new array and copying, which is what ArrayList does for you.

items = Arrays.copyOf(items, items.length * 2);

Arrays of objects are not contiguous

Worth being precise about, because it undoes the main advantage.

An int[1000] is 1000 ints in a row — 4,000 bytes, one block.

A String[1000] is 1000 references in a row. The strings themselves are separate objects scattered across the heap. Walking the array is contiguous; reading the values it points at is pointer chasing. Same O(n) scan, very different behaviour.

So the advice from the memory post narrows: int[] beats List<Integer> substantially in a hot loop, while String[] beats List<String> only slightly, because both end up chasing references anyway.

Two-dimensional arrays are arrays of arrays

int[][] table = new int[a.length() + 1][b.length() + 1];

Java has no true 2D array. That line makes one array of references, each pointing at its own row — so the rows are contiguous internally but not with each other, and they need not even be the same length. It follows that iterating row by row is meaningfully faster than column by column, because row order is the order the memory is actually in.

When an array is the right answer

Yes when the size is known and fixed, when access is by index, when the element type is primitive and the loop is hot, or when you are implementing something else — every structure in the next four posts has an array underneath.

No when the size changes (use ArrayList), when you look things up by key (use a hash table), or when you insert and remove at the front constantly (use a linked list or a deque).

What to remember

• Contiguous memory plus fixed-size elements is what makes indexing O(1).
• Insert and delete are O(n) because elements physically move.
• The length can never change; growing means a new array and a copy.
• An array of objects is contiguous in its references only.