Before you begin
Why this matters
Java has a fixed-length array and a growable ArrayList, and it checks every index. Knowing what length, size, and the hidden capacity mean lets you predict when an add copies, where an index out of bounds exception comes from, and why a saved index can name the wrong element.
What this helps you reason about
- Find the last element without an index out of bounds exception.
- Explain what an ArrayList does when it runs out of space, and avoid needless copies.
- Spot a saved index that finds a different element after an add at the front.
At a station, taxis wait in a queue in the order they arrive, and the first taxi in the queue leaves first. This lesson keeps the taxis in a Java array or ArrayList, and asks how an index finds a taxi, which of the two can grow, and what an ArrayList does when its space runs out.
Already know this? The short version
- An array (int[]) has a fixed length, queue.length; an ArrayList grows (add, get, size()) and holds objects, so ArrayList<Integer> boxes each int.
- When an ArrayList’s inner array is full, add copies it into one about 1.5 times as large (OpenJDK 17), so add has a small amortized cost; new ArrayList<>(n) gives space for n at the start.
- An index outside 0 to length − 1 throws ArrayIndexOutOfBoundsException for an array and IndexOutOfBoundsException for a list.
- add(0, x) and remove(0) move every element, so a saved index can name a different element; remove with an int argument removes by index.
Words in this lesson (7)
- index
- The position of an element in an ordered collection, counted from 0. The first element has index 0, and the last has index length − 1.
- array
- An object that holds a fixed number of elements of one type, such as int[]. new int[5] makes one with 5 elements, and queue.length is that number.
- ArrayList
- A class from java.util whose objects hold a growable list. add puts an element at the end, get(i) reads index i, and size() gives the number of elements.
- capacity
- How many elements fit in the array inside an ArrayList before add must copy them into a larger one. Java code cannot read it.
- amortized cost
- The average cost of one operation over a long run of them. Adding to a growable list sometimes copies every element, but those copies become rarer as it grows, so the average cost of one addition stays small.
- exception
- An object that is thrown to stop the normal flow when an operation fails, such as the NumberFormatException from Integer.parseInt. A catch block can handle it.
- off-by-one error
- A mistake where a loop or a count goes one step too far or stops one step too early, such as a loop that never reaches the last element of an array.
Examples are focused snippets; imports, enclosing functions, or classes may be omitted. C examples use C11; Haskell examples use Haskell 2010. Expand the notes for language-specific depth.
01 / Positions
How does a collection find the element at a position?
An array keeps its elements in order. Each element has a position, its index, counted from 0. In {12, 7, 31}, taxi 12 is at index 0, taxi 7 at index 1, and taxi 31 at index 2. queue[i] reads the element at index i.
rank.length is the number of elements, 3 here; it is a field, written without parentheses. Because counting starts at 0, the last index is always one less than the length: queue[queue.length - 1] is the last taxi, however many there are.
Reading an element by its index takes one step, not a search. An int array keeps its elements side by side, so the program can work out where element i is from i alone.
int[] queue = {12, 7, 31};
System.out.println(queue[0]); // 12
System.out.println(queue.length); // 3
System.out.println(queue[queue.length - 1]); // 31Indexes run from 0 to length − 1; the last element is at length − 1.
Coming from Python: There are no negative indexes: queue[-1] throws an exception. Write queue[queue.length - 1].
Experiment
Read the first and the last taxi
The first element is at index 0. The length is 3, so the last index is 3 - 1 = 2. After a fourth taxi is added, the length is 4, and the same expression reads index 3.
Why it matters Compute the last index from the length, as length - 1, so it stays right when the number of elements changes.
Predict the three printed numbers. Then change the braces to {12, 7, 31, 25} and predict again.
class Main {
public static void main(String[] args) {
int[] queue = {12, 7, 31};
int first = queue[0];
int last = queue[queue.length - 1];
System.out.println(queue.length + " " + first + " " + last);
}
}
What to look for
queue shows int[]@ and a number, the debugger’s id for the array, then [12, 7, 31]; main also lists args, an empty array of command-line arguments. first shows 12, last shows 31, and the run prints 3 12 31. After the edit, queue shows [12, 7, 31, 25], last shows 25, and the run prints 4 12 25.
Expected output
3 12 3102 / Fixed or growable
What stays fixed, and what can grow?
Java has both kinds of indexed collection. An array has a fixed length, chosen when it is created: new int[3] makes three ints, all 0, and {12, 7, 31} makes three with those values.
An ArrayList can grow. add(25) puts 25 at the end, and remove(queue.size() - 1) removes the last element. List.of(12, 7, 31) makes a list that cannot change, and new ArrayList<>(…) copies it into one that can.
The two differ in four ways. Size: an array’s length is fixed, and an ArrayList grows. Length: an array has the field queue.length, and an ArrayList has the method queue.size(). Reading: an array uses queue[i], and an ArrayList uses queue.get(i). Elements: an int[] holds int values, and an ArrayList<Integer> holds each number as an Integer object. Java final, primitives, and boxing explains this boxing.
int[] bays = new int[3]; // always 3 ints, all 0
List<Integer> queue = new ArrayList<>(List.of(12, 7, 31));
queue.add(25);
System.out.println(bays.length + " " + queue.size()); // 3 4An array’s length is fixed when it is created; an ArrayList grows with add.
Coming from JavaScript: A Java array cannot grow: there is no push. Use an ArrayList when the number of elements changes.
03 / Growing
What does it cost to grow?
Inside, an ArrayList keeps its elements in an ordinary array with unused space; the length of that array is its capacity. add writes into the unused space. When the space runs out, add makes a new, larger array, copies every element into it, and from then on uses the new array. The old one is left for the garbage collector. Arrays.copyOf(queue, 6) does that copy by hand: it returns a new array of length 6 that starts with queue’s elements.
The new array is about 1.5 times as long as the old one, so the copies become rarer as the list grows. For example, a list that starts with space for 10 grows to 15, 22, 33, 49, 73, and 109 places. Over 100 adds, it copies 10 + 15 + 22 + 33 + 49 + 73 = 202 elements in all, about 2 copies per add. This average cost of one add, which stays small however long the list gets, is the amortized cost. When you know the size, new ArrayList<>(100) starts with space for 100 and avoids the copies.
int[] queue = {12, 7, 31};
int[] bigger = Arrays.copyOf(queue, 6); // [12, 7, 31, 0, 0, 0]
bigger[3] = 25;
queue = bigger; // what an ArrayList does insideAn ArrayList copies its elements only when its inner array is full; give it a capacity when you know the size.
Precisely: the growth rule
The JavaDoc promises only that add has constant amortized cost. The numbers above are those of OpenJDK 17, the stepper’s Java, where an ArrayList made with new ArrayList<>() gets space for 10 at its first add. ensureCapacity(n) makes space ahead of time.
Experiment
Grow an array by copying it
An array’s length never changes, so growing means a new, larger array and a copy of every element. An ArrayList does this inside: when its array is full, add copies the elements to a larger array and keeps that one.
Why it matters Every time an ArrayList runs out of space, one add copies all its elements. new ArrayList<>(n) gives space for n at the start when you know the size.
Predict both printed numbers. Then add the line queue = bigger; just before the println line, and predict again.
import java.util.Arrays;
class Main {
public static void main(String[] args) {
int[] queue = {12, 7, 31};
int[] bigger = Arrays.copyOf(queue, 6);
bigger[3] = 25;
System.out.println(queue.length + " " + bigger.length);
}
}
What to look for
After Arrays.copyOf, bigger shows a different id from queue and [12, 7, 31, 0, 0, 0]: a new array of length 6. After bigger[3] = 25, only bigger changes, and the run prints 3 6. After the edit, queue shows the same id as bigger, and the run prints 6 6; nothing refers to the three-element array any more.
Expected output
3 604 / Out of range
What happens at an index past the end?
Java checks every index. An index below 0, or at the length or beyond, throws an exception: an object that stops the normal flow. For an array, the stepper shows java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3. An ArrayList’s get throws java.lang.IndexOutOfBoundsException, with the same message. get checks the index against size(), not against the inner array: on a list of size 3, get(3) throws even when the inner array has space at index 3.
The usual cause is an off-by-one error: a loop that runs one step too far. for (int i = 0; i < queue.length; i++) starts i at 0, runs the block while i < queue.length, and adds 1 to i after each round. With <= in place of <, the last round asks for index 3.
int[] queue = {12, 7, 31};
for (int i = 0; i < queue.length; i++) {
System.out.println(i + " " + queue[i]);
}
// with i <= queue.length, the last round throwsAn index past the end throws an exception; loop with i < length.
Precisely: loops without indexes
for (int taxi : queue) visits each element in turn without an index, so it cannot go one step too far. It cannot tell you the index, and changing an ArrayList inside such a loop throws ConcurrentModificationException.
Experiment
Loop one step past the last index
With <=, the loop runs once more, with i equal to the length. Java checks every index, and index 3 is outside an array of length 3, so it throws an exception.
Why it matters Loop with i < length, never i <= length. The last index is length - 1.
Predict the printed lines. Then change i < queue.length to i <= queue.length and predict again.
class Main {
public static void main(String[] args) {
int[] queue = {12, 7, 31};
for (int i = 0; i < queue.length; i++) {
System.out.println(i + " " + queue[i]);
}
}
}
What to look for
Each round stops on the println line, with i showing the index about to be read, and again on the for line. The run prints 0 12, 1 7, and 2 31. After the edit, a fourth round stops on the println line with i at 3, and after the three lines the run ends with java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3.
Expected output
0 12
1 7
2 3105 / Front and end
What changes when you add or remove at the front?
add(x) and remove(queue.size() - 1) work at the end and move nothing. add(0, 40) puts 40 at index 0 and moves every other element one index later. remove(0) takes out index 0 and moves the rest one index earlier. Each costs one move per element that moves. On an ArrayList<Integer>, remove(0), with an int, removes the element at index 0, not the number 0.
A saved index does not move with its element. queue.indexOf(7) returns the index of the first element equal to 7, here 1. After queue.add(0, 40), queue.get(1) is 12, and taxi 7 is at index 2. Find the element again after a change at the front or in the middle.
List<Integer> queue = new ArrayList<>(List.of(12, 7, 31));
int spot = queue.indexOf(7); // 1
queue.add(0, 40); // [40, 12, 7, 31]
System.out.println(queue.get(spot)); // 12, not 7Changes at the front move every element; a saved index then finds a different element.
Precisely: ArrayDeque
java.util.ArrayDeque is a growable ring buffer: addFirst and pollFirst work at the front without moving the other elements. LinkedList also adds at the front cheaply, but reading by index walks the list.
Experiment
Save a position, then add at the front
Adding at the front moves 12, 7, and 31 one index later. spot still holds 1, and index 1 now holds 12. Adding at the end moves nothing, so index 1 still holds 7.
Why it matters A saved index is a place, not an element. After a change at the front or in the middle, find the element again.
Predict both printed numbers. Then change queue.add(0, 40); to queue.add(40); and predict again.
import java.util.ArrayList;
import java.util.List;
class Main {
public static void main(String[] args) {
List<Integer> queue = new ArrayList<>(List.of(12, 7, 31));
int spot = queue.indexOf(7);
queue.add(0, 40);
System.out.println(spot + " " + queue.get(spot));
}
}
What to look for
queue shows java.util.ArrayList@ and an id, and each element as java.lang.Integer@… {value: 12}: an Integer object for each number. After add(0, 40), the first element shows value 40, followed by 12, while spot still shows 1, and the run prints 1 12. After the edit, 40 is the last element, and the run prints 1 7.
Expected output
1 1206 / Try it
Can you predict a fresh example?
Decide which elements move, then read each index. The next lesson, Stack and heap, shows where the blocks that hold elements are stored.
import java.util.ArrayList;
import java.util.List;
class Main {
public static void main(String[] args) {
List<Integer> queue = new ArrayList<>(List.of(12, 7, 31, 25));
int spot = 2; // taxi 31
queue.remove(0);
System.out.println(queue.size() + " " + queue.get(0)
+ " " + queue.get(spot));
}
}
What is printed?
Reveal the reasoning
3 7 25. remove(0) takes taxi 12 out of index 0, so queue is [7, 31, 25] and its size is 3. Every taxi moved one index earlier, so index 2, saved for taxi 31, now holds taxi 25.
Practice tickets
- ARRAY-101 · The van screen shows the stop after the one the driver typed → Free
- ARRAY-102 · A cabin that needs inspection stays in service when the cabin before it also needs one → Sign in · Pro
- ARRAY-103 · New flights stop appearing in the logbook after the fifth → Sign in · Pro