Arrays

Fixed-length indexed data, default values, references, copying, and arrays whose rows can have different lengths.

Core19 min read5 exercises

Previously on

Section 3.3 gave you loops. You can now repeat work as many times as you need, decided while the program runs.

But every variable you have made so far holds exactly one value. A loop that repeats over nothing is not much use. The two ideas are made for each other, and this section is where they meet.

The problem

Store the marks of five students.

int mark1 = 78;
int mark2 = 65;
int mark3 = 91;
int mark4 = 54;
int mark5 = 88;

Now make it thirty students. Now make it however many students are in a file you have not opened yet.

You already hit this exact wall in Section 3.3, and loops solved it for actions. This is the same wall for data, and loops cannot help, because there is no way to write a loop over five variables with five different names.

There is a second problem hiding here. Even with only five, you cannot ask a useful question. What is the average? What is the highest? You would have to name all five variables by hand in every calculation, and rewrite every one of those lines the day a sixth student arrives.

What you need is one name for many values, numbered so a loop can walk them.

The idea

That is an array.

int[] marks = new int[5];

Read it in two halves.

int[] is the type: an array of ints.
new int[5] creates the array, with five slots, and every slot already usable.

The slots are numbered from 0, not 1.

Stack

main

int[] marks@1a2b

Heap

int[5]@1a2b

078

165

291

354

488

One name, five numbered slots. The numbers under the cells are index positions, not values.

marks[0] = 78;
marks[4] = 88;
System.out.println(marks[2]);      // read slot 2
System.out.println(marks.length);  // 5

And now the thing that makes it worth having:

for (int i = 0; i < marks.length; i++) {
    System.out.println(marks[i]);
}

That loop does not care whether the array holds 5 values or 5 million. This is why the counting convention from Section 3.3 was “start at 0 and use <”. It exists to match array positions exactly.

Three ways to make one

int[] a = new int[5];                  // 5 slots, all filled with 0
int[] b = {78, 65, 91, 54, 88};        // sizes itself from what you gave it
int[] c = new int[]{78, 65, 91};       // the long form of the same thing

The second form is the one you will write most.

Where the brackets go

int[] marks;      // preferred. The type is "array of int"
int marks[];      // legal, inherited from C, and worse

Both compile. Use the first. int[] keeps the type in one piece, which matters as soon as you declare two things on one line: int[] a, b; gives two arrays, but int a[], b; gives one array and one plain int.

Every slot is already filled

You never get garbage from a fresh Java array.

	Array of	Every slot starts as
byte, short, int, long	whole numbers	0
float, double	decimals	0.0
char	characters	'\u0000', an invisible character
boolean	true or false	false
any object type	references	null

Java specifies these defaults. C distinguishes storage durations and initialisation forms, so a broad claim that every C array starts with garbage is false. The useful Java rule is direct: every element in a newly created array already has the default value for its type.

The for-each loop

When you want every element and you do not care about the position:

for (int mark : marks) {
    System.out.println(mark);
}

Read the : as “in”. No counter, no length, no chance of an off-by-one error.

The limitation is that you do not have i, so you cannot say which position you are at, and you cannot change the array through it. Assigning to mark changes your local copy and does nothing to the array.

Under the hood

Core

Invalid lengths, indexes, and references

int[] marks = new int[5];
marks[5] = 100;     // ArrayIndexOutOfBoundsException at run time

Five slots, numbered 0 to 4. There is no slot 5.

Notice when this happens. The code compiles perfectly. The failure arrives while the program is running, because the index could have come from anywhere: a calculation, a file, a user.

The C language does not require a bounds check. An out-of-range access has undefined behaviour unless tooling or an implementation adds protection. Java requires a check and throws at the invalid access.

The required check has a runtime cost when it remains. A JIT compiler can remove checks that it proves redundant. Java still guarantees the exception for an invalid access.

Three array failures are worth separating:

	Code	Result
new int[-1]	negative requested length	NegativeArraySizeException
values[values.length]	index is outside 0 through length - 1	ArrayIndexOutOfBoundsException
values.length when values is null	no array object is designated	NullPointerException

Arrays are fixed size, permanently

int[] marks = new int[5];
// there is no marks.add(). There is no way to make it 6.

Once created, an array’s size never changes. To hold more you create a bigger array and copy everything across:

int[] bigger = new int[10];
System.arraycopy(marks, 0, bigger, 0, marks.length);
// or: int[] bigger = Arrays.copyOf(marks, 10);

This is inconvenient, and it is the reason ArrayList exists. In Phase X you will find that ArrayList is doing exactly the copy above, automatically, whenever it runs out of room.

Assignment creates an alias, not an array copy

An array variable holds a reference value, so its assignment rule differs from primitive value assignment.

int[] a = {1, 2, 3};
int[] b = a;          // copies the reference value
b[0] = 99;
System.out.println(a[0]);    // 99

There is only one array. b = a copied the reference, not the array object.

Stack

main

int[] a@1a2b

int[] b@1a2b

Heap

int[3]@1a2b

099

Two variables, one array. The arrows show that both references designate the same object, not a visible raw address.

Request a new array explicitly when you need an independent primitive array:

int[] b = a.clone();
int[] b = Arrays.copyOf(a, a.length);

Arrays of arrays

int[][] grid = new int[3][4];      // 3 rows, 4 columns
grid[1][2] = 7;

for (int row = 0; row < grid.length; row++) {
    for (int col = 0; col < grid[row].length; col++) {
        System.out.print(grid[row][col] + " ");
    }
    System.out.println();
}

Output after the assignment to grid[1][2]:

0 0 0 0
0 0 7 0
0 0 0 0

Java has no true two dimensional array. int[][] is an array of references to arrays. Which means the rows do not have to be the same length:

int[][] triangle = new int[3][];
triangle[0] = new int[1];
triangle[1] = new int[2];
triangle[2] = new int[3];

That is called a jagged array, and it is only possible because each row is a separate object with its own reference. Note grid[row].length in the loop above, not grid[0].length. If you ever write jagged arrays, that difference stops being cosmetic.

A first look at String

You have been using String since your first program without being told what it is. Here is the short version, because arrays make it explainable.

A String is not a primitive. It is a class with an immutable sequence of characters as its public abstraction. Its private storage is not a Java language promise. Current JDKs can use compact byte-based storage, while other implementations may choose another representation.

String name = "Atlas";
System.out.println(name.length());        // 5, a method call with parentheses
System.out.println(name.charAt(0));       // A
System.out.println(name.toUpperCase());   // ATLAS

Two things worth noticing now.

length versus length(). Arrays expose arr.length, a final field with no parentheses. Strings expose text.length(), a method. They are different APIs, so the syntax differs.

A String cannot be changed. toUpperCase() does not modify name. It builds and returns a new String, and name is untouched unless you assign the result. Every String method works this way.

Phase IX is entirely about Strings: why they cannot change, what the String Pool is, and why == behaved so strangely back in Section 3.2.

What it costs

The fixed size is the big one. You have to know how many slots you need before you create the array. Too small and you are copying into a bigger one. Too large and you have wasted the memory. That single limitation is why the whole Collections Framework exists.

Every read is checked against the length. In a tight loop over millions of elements that comparison is measurable. The JVM removes many of the checks when it can prove they are pointless, but not all of them.

An int[] holds ints and nothing else, forever.

Copying is a real operation. Assigning an array gives you a second name for the same data, silently. Getting an actual copy takes a method call, and for objects even that is not enough.

What you get back is constant-time indexed access and little API overhead. Do not turn that into a universal “fastest” claim. Performance depends on element type, access pattern, JVM and workload. ArrayList and HashMap use arrays internally in current JDK implementations, but their public contracts do not expose those arrays.

Check yourself

Answer from memory before opening the explanation. Then compare your rule with the answer and revisit the example if they differ.

`int[] scores = new int[5];` and you have not put anything in it. What is in `scores[0]`, and why is Java's answer different from C's?
Show the answer
Zero. Every slot is filled in for you, and what it gets filled with depends on the type: 0 for whole numbers, 0.0 for decimals, false for boolean, '\u0000' for char, and null for every reference type.

Java specifies these defaults for every newly created array. C has different rules: some storage is zero-initialised, while an uninitialised automatic array has indeterminate values and reading such a value can be invalid.
`arr.length` has no brackets but `text.length()` does. Both mean 'how big is it'. Why is one written differently from the other?
Show the answer
Because they are different language and API members. Every array has the final length field defined by the Java language. Its physical storage is a JVM implementation detail.

length() on a String is a method: a piece of code you call, which then gives you a number back.

Array types are created specially by the JVM rather than declared in a Java source file. String is a declared class whose public API supplies length().
You wrote `int[] a = {1, 2, 3};` and then `int[] b = a;`. You change `b[0]` to 99. Print `a[0]`. What do you get, and why?
Show the answer
99. There is only one array object.

b = a copied the reference, not the array. Both variables now designate the same array object, so a change through one is visible through the other. There was never a second array to change.

To get a real copy you have to ask for one: int[] b = a.clone(); or Arrays.copyOf(a, a.length).

Section 6.3 applies the same rule to objects with mutable fields and separates aliasing from shallow and deep copying.

Exercises

Write each solution in VS Code, predict its result, and then run the checks. Reading an example does not replace implementing it.

5 exercises115 pointsabout 125 minutes

The Layers of Logic VS Code extension runs the checks for exercises marked checked. For a manual exercise, run the program and compare its behaviour with the stated requirements and sample output.

Fill It, Walk It, Total It

Warm up·20 min·15 points

checkedex-4-1-a

The everyday array exercise, with one rule that matters: never type the size.

Use marks.length everywhere. It costs nothing and it means the day the array changes, your code does not.

The average will catch you if you are not paying attention. Both total and marks.length are ints, so the division is int division and your decimal disappears. You met this exact bug in Section 2.3.

Finish by adding an eighth mark. If you have to change anything other than the array itself, go back and find the number you hardcoded.

What to write

These exact signatures. The checks call them by name, so a different name or a different parameter type will not build.

class Marks {
    static int total(int[] marks)
    static double average(int[] marks)
    static int highest(int[] marks)
    static int lowest(int[] marks)
    static int countAtLeast(int[] marks, int threshold)
}

average must keep its fraction, and the threshold in countAtLeast is inclusive.

What your program must do

Print every mark with its position
Work out the total, average, highest and lowest
Count the marks at or above a threshold
Say why the average needs a cast and where the cast has to go

Marks.java

public class Marks {

    static int total(int[] marks)   { return 0; }  // TODO
    static double average(int[] marks) { return 0; }  // TODO: keep the fraction
    static int highest(int[] marks) { return 0; }  // TODO
    static int lowest(int[] marks)  { return 0; }  // TODO
    static int countAtLeast(int[] marks, int threshold) { return 0; }  // TODO

    public static void main(String[] args) {
        int[] marks = {78, 65, 91, 54, 88, 72, 95};
        // TODO: print every mark with its position
        // TODO: print the total, the average, the highest, the lowest
        // TODO: print how many are 70 or above
    }
}

Sample run

It prints

[0] 78
[1] 65
...
total   : 543
average : 77.57
highest : 95
lowest  : 54
70+     : 5

Hint 1

A for-each loop is enough for everything except printing the position, which needs the index.

Hint 2

Start highest and lowest at marks[0], not at 0 and not at Integer.MAX_VALUE. Starting at 0 breaks the moment every mark is negative.

Hint 3almost the answer

(double) total / marks.length works. (double) (total / marks.length) does not, because the integer division has already happened. That is Section 2.3.

One Array, Two Names

Real work·20 min·20 points

checkedex-4-1-b

Four variables. Three arrays. Work out which two share.

Predict all four printed lines before running. For each result, count the number of array objects and identify which variables designate each one.

Then compare the pairs two ways, with == and with Arrays.equals. They disagree, and the disagreement is exactly the same one you met with Strings in Section 3.2.

Finish with a reachability diagram: a box per variable, a node per array, and an arrow for each reference. Count three array nodes. Treat the boxes and arrows as an identity model, not fixed stack slots or raw addresses.

What to write

These exact signatures. The checks call them by name, so a different name or a different parameter type will not build.

class Shared {
    static int[] original()
    static boolean assignmentShares()
    static boolean cloneShares()
    static boolean copyOfShares()
    static boolean sameObject(int[] a, int[] b)
    static boolean sameContent(int[] a, int[] b)
}

Each shares method builds its own array, copies it the named way, changes the copy, and reports whether the original changed too.

What your program must do

Predict which of the three copies actually copy
Compare two equal arrays with == and with Arrays.equals
Say what an array variable actually holds
Show that clone only copies one level deep

Shared.java

import java.util.Arrays;

public class Shared {

    static int[] original() { return new int[]{1, 2, 3}; }

    // Copy the array the named way, change the COPY, and report whether the
    // original changed too. Predict all three before running.
    static boolean assignmentShares() { return false; }  // TODO: int[] b = a;
    static boolean cloneShares()      { return false; }  // TODO: a.clone()
    static boolean copyOfShares()     { return false; }  // TODO: Arrays.copyOf

    static boolean sameObject(int[] a, int[] b)  { return false; }  // TODO: ==
    static boolean sameContent(int[] a, int[] b) { return false; }  // TODO: Arrays.equals

    public static void main(String[] args) {
        // TODO: print all three, then compare two equal arrays with == and with equals
    }
}

Hint 1

An array variable holds an opaque reference. Assignment copies the reference, so both names designate the same array. Java does not expose a raw address.

Hint 2

== on arrays asks whether they are the same object, which is almost never the question you meant. Arrays.equals compares the contents.

Hint 3almost the answer

clone on a two dimensional array copies the outer array and shares the rows. Change copy[0][0] and the original changes with it.

Reverse It In Place

Real work·25 min·25 points

checkedex-4-1-c

Reverse an array without making a second one. Swap from both ends inwards.

The four test cases are not decoration. Odd length, even length, one element, and empty. Each one catches a different mistake, and the empty array catches the mistake people most often ship.

The interesting failure here is not a crash. It is the loop that runs to the end and swaps everything twice, giving you back exactly what you started with. That version looks completely reasonable and produces no error at all.

Explain that failure in your own words before you move on.

What to write

These exact signatures. The checks call them by name, so a different name or a different parameter type will not build.

class Reverse {
    static void reverseInPlace(int[] arr)
    static int swapsNeeded(int length)
}

reverseInPlace changes the array it is given and creates no second array. swapsNeeded reports how many swaps a reversal of that length takes.

What your program must do

Reverse the array without allocating a second one
Handle odd and even lengths, one element and none
Show that reversing twice gives back the original
Work out how many swaps it takes, and why it is not the length

Reverse.java

import java.util.Arrays;

public class Reverse {

    // Reverse arr WITHOUT creating another array.
    static void reverseInPlace(int[] arr) {
        // TODO
    }

    // How many swaps does a reversal of this length take?
    static int swapsNeeded(int length) { return 0; }  // TODO

    public static void main(String[] args) {
        for (int[] t : new int[][]{{1,2,3,4,5}, {1,2,3,4}, {1}, {}}) {
            int[] copy = t.clone();
            reverseInPlace(copy);
            System.out.println(Arrays.toString(t) + "  ->  " + Arrays.toString(copy));
        }
    }
}

Hint 1

Two indexes, one at each end, walking towards each other and swapping as they go.

Hint 2

The loop stops when they meet. With an odd length the middle element is already where it belongs, so it is never swapped.

Hint 3almost the answer

An empty array needs no special case if the condition is left < right. Test it anyway, because a loop that runs zero times is exactly where off by one errors hide.

A Grid With Uneven Rows

Real work·25 min·25 points

checkedex-4-1-d

Build a rectangle, then build a triangle.

The rectangle is the ordinary case, and nested loops handle it. The triangle is where Java shows you what a two dimensional array really is.

Use grid[row].length in your inner loop from the start, not grid[0].length. Both work on the rectangle. Only one survives the triangle, and getting into the right habit on the easy case is the point.

Finish by explaining, in one or two sentences, why the triangle is possible at all. The answer is about references, and if you can say it clearly then Section 4.2 will feel like confirmation rather than new information.

What to write

These exact signatures. The checks call them by name, so a different name or a different parameter type will not build.

class Jagged {
    static int[][] rectangle(int rows, int cols)
    static int[][] triangle(int rows)
    static int totalSlots(int[][] grid)
    static boolean isRectangular(int[][] grid)
    static String rowLengths(int[][] grid)
}

Both grids are filled so that value equals row times ten plus column. In the triangle, row r has r plus one slots. rowLengths returns the lengths separated by single spaces.

What your program must do

Build and fill a rectangular grid
Build a triangular grid where each row is its own length
Count the slots in each and compare
Say what new int[3][] gives you that new int[3][4] does not

Jagged.java

public class Jagged {

    // A rectangle. Fill it so grid[r][c] = r * 10 + c.
    static int[][] rectangle(int rows, int cols) { return new int[0][0]; }  // TODO

    // A triangle: row 0 has 1 slot, row 1 has 2, row 2 has 3. Same fill rule.
    static int[][] triangle(int rows) { return new int[0][]; }  // TODO

    static int totalSlots(int[][] grid)       { return 0; }     // TODO
    static boolean isRectangular(int[][] grid) { return false; } // TODO
    static String rowLengths(int[][] grid)     { return ""; }    // TODO

    public static void main(String[] args) {
        // TODO: print both grids and their row lengths
    }
}

Hint 1

new int[3][4] makes the outer array and all three rows at once. new int[3][] makes only the outer array, and every row starts as null.

Hint 2

So the triangle needs t[r] = new int[r + 1]; before anything can go in that row.

Hint 3almost the answer

Use row.length rather than a stored width when walking a jagged grid. Every row knows its own length, and that is the only thing that is true for both shapes.

The Registry Gets a Roster

Hard·35 min·30 points·The Registry

checkedex-4-1-e

Five units, four facts each, held in four separate arrays. Position i in every array describes the same unit. This is called parallel arrays, and it is how you hold structured data before you have objects.

Build the whole roster: a readable table, the top unit by name, the average readiness of active units only, and a count of deployable units.

Then sort by readiness, highest first. This is where the exercise earns its difficulty rating. Every swap has to happen in all four arrays, together, every time. Nothing in Java stops you from swapping three of them and leaving the fourth behind, and if you do, a unit silently ends up with someone else’s readiness score.

Notice that feeling. Four things that must always move together, with no mechanism keeping them together. In Phase VI you will bundle all four into one object, and this whole class of bug stops being possible. This exercise exists so that when that happens, you know exactly what was bought.

What to write

These exact signatures. The checks call them by name, so a different name or a different parameter type will not build.

class Roster {
    static String[] names()
    static int[] ids()
    static double[] readiness()
    static boolean[] active()
    static int indexOfHighestReadiness(double[] readiness)
    static double averageActiveReadiness(double[] readiness, boolean[] active)
    static int countDeployable(double[] readiness, boolean[] active)
    static String[] sortedByReadinessDescending(String[] names, int[] ids, double[] readiness, boolean[] active)
}

Position i in every array describes the same unit. The sort returns the names in order and must not disturb any of the arrays it is given. Deployable means active and readiness at least 60.

What your program must do

Find the highest readiness by index so the name still matches
Average only the active units
Count units that are active and at least 60
Sort by readiness keeping every row together, without changing the inputs

Roster.java

public class Roster {

    // Parallel arrays: position i in every array describes the same unit.
    static String[]  names()     { return new String[]{"Atlas", "Beacon", "Cipher", "Drift", "Ember"}; }
    static int[]     ids()       { return new int[]{101, 102, 103, 104, 105}; }
    static double[]  readiness() { return new double[]{88.5, 42.0, 95.5, 61.0, 73.5}; }
    static boolean[] active()    { return new boolean[]{true, true, false, true, true}; }

    static int indexOfHighestReadiness(double[] readiness) { return 0; }  // TODO
    static double averageActiveReadiness(double[] readiness, boolean[] active) { return 0; }  // TODO
    static int countDeployable(double[] readiness, boolean[] active) { return 0; }  // TODO

    // Sort by readiness, highest first, KEEPING THE ROWS TOGETHER.
    // Return the names in the new order. Do not change the arrays you were given.
    static String[] sortedByReadinessDescending(
            String[] names, int[] ids, double[] readiness, boolean[] active) {
        return new String[0];  // TODO
    }

    public static void main(String[] args) {
        // TODO: print a formatted roster table and all four answers
    }
}

Hint 1

Return the index rather than the value, or you cannot get back to the name. That is the weakness of parallel arrays in one line.

Hint 2

Guard the empty case in the average. No active units means dividing by zero.

Hint 3almost the answer

Every swap in the sort has to touch all four arrays. Miss one and the names no longer line up with the readiness, and nothing will tell you.

After the credits

This lesson gave the reference model an explicit name.

Section 6.3 applies pass-by-value to reference arguments. A method receives a copied reference value, so it can mutate the designated object but cannot replace the caller’s variable.

Section 8.3 distinguishes reference identity from value equality and defines the equals contract.

The array itself never goes away either. It goes underneath things.

In Phase X, ArrayList turns out to be an array that replaces itself with a bigger one when it fills up. It does exactly the copy you did by hand in this section. And HashMap turns out to be an array of buckets, using the bit trick from Section 3.1 to pick which bucket.

Later collections reuse arrays where indexed storage matches their requirements.

Threads you opened in this section

ReferenceTwo references, one object. This is where copying gets dangerous.6.3 - Objects in Memory: Size, Copying, Passing
Reference== compares references. equals() is what compares contents.8.3 - The Object Class: `equals`, `hashCode`, `toString`
ReferenceAn object with no reference left pointing at it is garbage.Phase XIII. Memory and the Garbage Collector
ArrayString[] args has been sitting in your main method since day one.6.4 - `static` and `final`
ArrayArrayList is an array that quietly replaces itself with a bigger one.Phase X. The Collections Framework
ArrayHashMap is an array of buckets. The array never went away.Phase X. The Collections Framework

Reference will return in 6.1 - Classes, Objects, and `new`