Array Indexing and Bounds

An array's length is fixed, so a counter variable is needed to track how many positions currently hold valid items.

Programming

Length Is Not the Same as Contents

When you declare an array of 100 integers, it is natural to assume that the program is storing 100 numbers. That assumption works well when you know ahead of time exactly how many values you will store. It breaks down the moment the number of values changes while the program runs.

Consider a program that reads positive integers from the user, stores each one in an array, and stops when it receives a zero. Suppose the array was created with room for 100 values, but the user enters only two numbers before typing zero. Before reading on, predict what the program should do with the remaining 98 positions. Does anything in the array's length tell the program where its real data stops?

The answer to that question is the subject of this article. The length of an array describes how many slots exist, not how many of them hold useful data. Keeping those two ideas separate is the first step toward writing programs that handle variable amounts of input safely.

Tracing Filled and Empty Slots

Imagine an array with 10 positions in which only the first four hold meaningful items. The other six positions were reserved when the array was created, but nothing has been stored in them. From the array's point of view all ten positions look the same. Only the program, through its own bookkeeping, knows which positions are filled.

The diagram shows the gap between the two numbers. The array has a length of 10, which is the number of slots it reserves. Only indexes 0 through 3 contain values the program should read. Indexes 4 through 9 are reserved space that holds nothing the program should use. The length alone cannot tell you where the boundary between these two regions sits.

The Counter as a Tally

An array's length is fixed. Once it is created it cannot grow or shrink, so the program cannot rely on the length to describe its contents. The fix is to keep a separate integer variable, usually called a counter, that records how many positions are in use.

Definition

A counter is an integer variable that records how many positions of an array contain valid items. It does not hold any of the stored values. It only keeps a tally of how many of the array's positions are occupied.

Key point

The counter is never used to decide whether a value is valid. It is updated only when a value is actually saved into the array.

The Counter Doubles as the Next Free Index

The counter has a second job that is easy to miss. If the count is three, then three items occupy indexes 0, 1, and 2. That same value, three, is also the index of the next open spot. The counter therefore answers two questions at once: how many items are stored, and where the next one should go. Whenever you see the counter in a program, read its value both ways.

The diagram shows the situation the counter is tracking. Slots 0 through 2 were filled in order, and the counter's value of 3 points at the first slot that is still free. Every slot at or beyond that point is reserved space that holds nothing the program should read yet.

The storing step follows a simple rhythm. The program places the new value at the position given by the counter, and then increments the counter by one so that the next value goes to the next free position.

java

public class Tally {
    public static void main(String[] args) {
        int[] values = new int[10];
        int count = 0;
        int[] incoming = {4, 8, 15, 16};

        for (int i = 0; i < incoming.length; i++) {
            values[count] = incoming[i];
            count++;
        }

        System.out.println("Length: " + values.length);
        System.out.println("Valid items: " + count);
    }
}

public class Tally {
    public static void main(String[] args) {
        int[] values = new int[10];
        int count = 0;
        int[] incoming = {4, 8, 15, 16};

        for (int i = 0; i < incoming.length; i++) {
            values[count] = incoming[i];
            count++;
        }

        System.out.println("Length: " + values.length);
        System.out.println("Valid items: " + count);
    }
}

Output

Length: 10
Valid items: 4

Notes on the code

values has a fixed length of 10 and never changes size
count starts at 0 because no positions are filled yet
values[count] stores each new item at the next free index
count++ moves the counter to the next free index after each save

Walking the Valid Items in Reverse

When it is time to output the stored values, the counter tells the program where the valid region ends. The last occupied position is always the counter minus one, because the counter points one past the final item. A loop that begins there and walks downward to zero visits every valid item exactly once, from last to first.

Code walkthrough

for (int i = count - 1; i >= 0; i--) {
    System.out.println(values[i]);
}

1
The loop starts at count minus one. With count equal to 4, the first index visited is 3, the last occupied slot.
2
The condition i greater than or equal to 0 keeps the loop running down to and including index 0.
3
Each pass prints values at the current index, and i decrements by one, so the loop visits indexes 3, 2, 1, 0 in that order.
4
Index 0 is the last index visited, so every stored item is printed exactly once, from last to first.

The start index is count minus one, not count
The condition keeps the loop running while the index is zero or greater
The decrement moves the index down by one on each pass

Output

Read the header carefully. The starting index is count minus one, not count itself, because the counter is already one past the last item. Starting from the counter, or stopping at one instead of zero, are the two most common ways this loop goes wrong.

Filling the Array Until It Overflows

Counting protects a program only if the count stays inside the array's bounds. Suppose an array was created with 4 positions and the input keeps arriving. The fifth value has no valid place to go. The program would attempt to store it at index 4, a position that does not exist in a 4-slot array.

The diagram traces the counter from 0 up to the array length of 4. After the fourth value is stored the counter equals 4, which is one past the last valid index of 3. The fifth insertion asks for index 4, and that request is the failure. Because arrays do not resize, the program has nowhere to put the value.

java

public class Overflow {
    public static void main(String[] args) {
        int[] values = new int[4];
        int count = 0;
        int[] incoming = {4, 8, 15, 16, 23};

        for (int i = 0; i < incoming.length; i++) {
            values[count] = incoming[i];
            count++;
        }
    }
}

public class Overflow {
    public static void main(String[] args) {
        int[] values = new int[4];
        int count = 0;
        int[] incoming = {4, 8, 15, 16, 23};

        for (int i = 0; i < incoming.length; i++) {
            values[count] = incoming[i];
            count++;
        }
    }
}

Output

java.lang.ArrayIndexOutOfBoundsException raised at run time when the fifth value is stored at index 4

Notes on the code

The fifth iteration uses count equal to 4
Index 4 does not exist in an array of length 4

Mistakes Beginners Make with Bounds

Common mistake
Treating the array length as the number of stored items
What it looks like
Printing all 10 positions of an array when only 4 values were entered
Why it fails
The length counts reserved slots, not filled slots, and the program has no way to tell valid from empty positions from length alone.
Do this instead
Keep a counter variable and loop only up to the counter.
Common mistake
Starting the reverse loop at the counter instead of counter minus one
What it looks like
```
for (int i = count; i >= 0; i--) with count equal to 4 reads index 4
```
Why it fails
The counter points one past the last item, so index count is the first free slot, not a stored item.
Do this instead
Start the reverse loop at count minus one.
Common mistake
Stopping the reverse loop at 1 instead of 0
What it looks like
```
for (int i = count - 1; i > 0; i--) skips the first stored item
```
Why it fails
Index 0 holds a valid item, so a loop that stops before it misses that item.
Do this instead
Keep the condition i greater than or equal to 0.
Common mistake
Storing without checking the counter against the array length
What it looks like
Inserting a fifth value into an array of length 4 without any check
Why it fails
Arrays do not resize, so index 4 does not exist and the program fails at run time.
Do this instead
Check that the counter is less than the array length before storing, or handle the full case explicitly.

Tracing an Input Sequence by Hand

MEDIUM

An array of length 3 receives the inputs 7, 2, 9, 5 in that order, with the counter starting at 0. After each store the counter is incremented. Trace the counter and the array contents after each insertion. At which insertion does the counter reach the array length, and which insertion would cause an ArrayIndexOutOfBoundsException?

Hints

Write down the counter value before each store, then the index it uses
The counter equals the array length after the third store
Ask which index the fourth insertion would need

Your attempt (not saved)

What do you think happens?

After the counter reaches 3 in a length-3 array, what happens on the next store?

Reveal answer

Answer:

The program tries to store at index 3, which does not exist, and an ArrayIndexOutOfBoundsException is thrown.

The last valid index is always one less than the length, so index 3 is outside the range 0 to 2.

Key Takeaways

An array's length is fixed and describes reserved slots, not how many of them hold meaningful items.
A counter variable tallies how many positions hold valid items and is updated only when a value is saved.
The counter doubles as the index of the next free position, so the last valid index is always counter minus one.
Reverse processing starts at counter minus one and runs down to index 0 so every stored item is visited once.
Storing at an index equal to the array length raises an ArrayIndexOutOfBoundsException because arrays do not resize.

Length Is Not the Same as Contents

Tracing Filled and Empty Slots

The Counter as a Tally

The Counter Doubles as the Next Free Index

Walking the Valid Items in Reverse

Filling the Array Until It Overflows

Mistakes Beginners Make with Bounds

Tracing an Input Sequence by Hand

Key Takeaways

Related Topics