A catalog service answers priceOf(skuIndex) on every cart line. The prices live in a BigDecimal[] of 80,000 slots. Slot 47,392 is one address calculation. Then merchandising inserts a new SKU at catalog position 40 so it sorts with the rest of its category — and every later price has to slide one slot to the right.

An array is a contiguous block of slots with a length the JVM will not change. Index i is pointer arithmetic. Insert and delete in the middle are a copy of the tail. That trade-off is the whole structure.

This is the first layout post in the data-structures series. The glossary there — contiguous vs linked, Big-O, amortized — is assumed. Here we only care about a static T[], why a[i] is free, why the middle is expensive, and how a 2D matrix is still that same block with a stride.

The layout: a block and a length

In Java a static array is T[]. You pick the length at allocation. The JVM stores that length; it does not grow.

int[] ranks = new int[10_000];        // ten thousand zeros
String[] labels = new String[10_000]; // ten thousand nulls

ranks[i] and labels[i] are the same operation: start of the block, plus i times the slot size. For primitives the slot holds the value. For reference types the slot holds a pointer; the objects themselves live elsewhere. Either way, reaching slot i does not walk slots 0 through i - 1.

Note: arr.length is the allocated capacity. It is not a “size” you can shrink. Unused tail slots still exist; they just hold the default (0, false, null).

Random access is the point

The hot path that made you pick an array is a read or write of an index you already know:

BigDecimal priceOf(BigDecimal[] prices, int skuIndex) {
    return prices[skuIndex];
}

void bump(int[] counts, int bucket) {
    counts[bucket]++;
}

If the job is “I already know i”, an array is the default layout. A linked structure would walk i pointers to do the same read. Bounds are the only extra check: an i outside 0 .. length - 1 is ArrayIndexOutOfBoundsException, not a scan that happens to miss.

Insert in the middle slides everything

There is no hole to open. To insert at index i you must move every later live element one slot right — and you need a spare slot, or a new larger array.

static void insertAt(int[] a, int size, int i, int value) {
    if (size >= a.length) {
        throw new IllegalStateException("array full");
    }
    System.arraycopy(a, i, a, i + 1, size - i);
    a[i] = value;
}

The size argument is the logical count you are maintaining; a.length is capacity. After insertAt(a, 5, 2, 99) the block looks like this:

before:  [10, 20, 30, 40, 50,  0,  0,  0]   size = 5
insert 99 at i = 2
after:   [10, 20, 99, 30, 40, 50,  0,  0]   size = 6
                  ^-- 30..50 slid right

Delete is the same copy in the other direction:

static int deleteAt(int[] a, int size, int i) {
    int removed = a[i];
    System.arraycopy(a, i + 1, a, i, size - i - 1);
    a[size - 1] = 0;
    return removed;
}

That is why the catalog insert at slot 40 costs O(n). The work is not “put this SKU here.” The work is slide every later SKU. Append at size (when capacity remains) is O(1) because nothing slides. Insert at 0 slides the whole live range.

A static T[] has no add. The snippets above are you pretending there is a logical size smaller than a.length. If the array is already full, insert means allocate, copy, throw the old block away.

Iteration is a scan of the block

Walking 0 .. length - 1 is the array’s other cheap job. The slots sit next to each other, so a sequential pass is what CPUs prefetch well.

int sum(int[] a) {
    int total = 0;
    for (int n : a) {
        total += n;
    }
    return total;
}

Search, unless you already know the index, is that same scan:

int indexOf(int[] a, int target) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == target) {
            return i;
        }
    }
    return -1;
}

Unsorted search is O(n). If the array is already sorted you can binary-search it (Arrays.binarySearch) in O(log n) — that is an algorithm on the layout, not a reason the array itself became a tree. Do not sort on every lookup to “make search fast”; that is a different bill.

2D / matrix: still one idea, a stride

A matrix looks two-dimensional in code. In memory it is still slots plus arithmetic.

Row-major order stores row 0, then row 1, then row 2. Cell (r, c) in a grid with cols columns lives at:

index = r * cols + c

A 3×4 grid of seats as one int[] keeps every cell in a single contiguous block:

final int rows = 3;
final int cols = 4;
int[] seats = new int[rows * cols];

int at(int r, int c) {
    return seats[r * cols + c];
}

void put(int r, int c, int id) {
    seats[r * cols + c] = id;
}

Same O(1) get and set. Same O(n) if you insert a column in the middle — now you are sliding a 2D layout that was never designed to grow. A 2×3 row-major walk of the flat form:

r,c → index    seats layout
0,0 → 0        [ a, b, c, d, e, f ]
0,1 → 1
0,2 → 2
1,0 → 3
1,1 → 4
1,2 → 5

Java also gives you T[][]:

int[][] grid = new int[3][4];
grid[1][2] = 42;

That is an array of row arrays, not one guaranteed block. Each row is its own int[] (contiguous inside the row). The rows themselves are separate objects, so they may not sit next to each other, and rows can even have different lengths — a jagged array. Flatten to T[] with a stride when you need a true contiguous matrix: cache-friendly scans, JNI, or a single allocation. Use T[][] when jagged rows are the point, or when the extra indexing is worth the simpler syntax.

Inserting a cell in the “middle” of a matrix is the same slide as the 1D case, with a larger n (rows * cols). Growing the grid is a new allocation and a copy with a new stride — not an in-place hole.

Complexity

OperationTimeWhat you actually pay
get(i)O(1)Address arithmetic
set(i)O(1)Address arithmetic
insert at iO(n)Slide n - i slots (or allocate + copy if full)
delete at iO(n)Slide n - i - 1 slots
search (unsorted)O(n)Scan until you hit the value
iterate allO(n)Sequential pass of the block

Space is O(n) for the slots. A static array does not charge extra pointers per element. It also does not give you spare room unless you allocated it.

Read this table the way the series hub said: pick the layout for the operation on the hot path. If that path is get(i) / set(i) / a full scan, the array is doing its job. If that path is insert-at-zero on every request, you are paying the expensive column on purpose.

When not to use an array

Skip a static T[] when:

  • The length will grow — you will hand-roll copyOf on every overflow. That job is a growable list (ArrayList), not a raw T[].
  • Insert or delete in the middle is the hot path — every call slides. A linked list makes splice cheap when you already hold the node; you give up get(i).
  • You need uniqueness or “is this already here?” as the hot path — a scan of n slots is the wrong bill. Use a set or map (see the hub’s JDK table).
  • A sparse matrix — most cells empty, a few set. A dense rows * cols block wastes RAM; a map of coordinates is a different layout.

A fixed lookup table, a histogram, a replay buffer with a known cap, a packed matrix — those are array jobs.

JDK: T[] vs wrapping in a list

The hub’s default: fixed-size contiguous storage → T[]. Wrapping that block in a list “just in case” adds an object, a size field, and an API that looks like it can grow — then you either never grow, or you grow and you no longer had a static array.

int[] buckets = new int[256];           // histogram: length is the model
List<Integer> boxed = new ArrayList<>();
for (int b : buckets) {
    boxed.add(b);                       // boxes every int; loses the "256 slots" fact
}

Reach for T[] when the length is the model (256 buckets, 8×8 board, n known at construction), when you need primitives without boxing, or when the hot path is indexed get/set or a tight scan.

Reach for ArrayList (or another List) when callers must append, when the API should speak “collection,” or when you want equals / subList / streaming without Arrays helpers. Arrays.asList(arr) on an object array is a fixed-size list view of that array — still not a growable list, and it does not work the way you expect on an int[] (one element: the array object).

Note: List.of(...) and Arrays.asList(...) are not a reason to avoid T[]. They are adapters. If the structure in memory is a fixed block of slots, keep the T[] at the core and wrap only at a boundary that needs a List.

Cheat sheet

Layout:     contiguous slots, length fixed at allocation
get/set i:  O(1)  — start + i * slotSize
insert/del: O(n)  — slide the tail (or allocate a new block)
search:     O(n) unsorted; binary search if already sorted
2D:         index = r * cols + c  (row-major, one T[])
Java T[][]: array of rows — not one guaranteed block
JDK:        T[] when length is the model; do not wrap "just in case"

Do:

  • Pick an array because you already know i, or because you will scan the whole block.
  • Keep a logical size only when the allocated length is capacity, not the live count.
  • Flatten a matrix to T[] when you need one allocation and a stride.

Don’t:

  • Insert at 0 on every request and call the array “fast.”
  • Wrap a known-length T[] in ArrayList so the type looks more “Collections.”
  • Treat Java T[][] as a single contiguous C matrix without checking.

Wrap-up

An array is the simplest contiguous layout Java has: a length, a block of slots, and index i as arithmetic. That is why prices[skuIndex] is free and why inserting a SKU at position 40 is a slide. A 2D matrix is the same idea with r * cols + c; T[][] is a convenience that is really an array of rows.

Use a static T[] when the length is part of the model and the hot path is get, set, or a scan. When the hot path is growth or splicing, the array is the wrong bill — pick the layout that makes that operation cheap, starting from the Data Structures Roadmap.

Next optional step in the series Grow the backing store without pretending every append is free. Dynamic Arrays: Amortized Growth