Arrays and Index Bounds

A dynamic array in this source is a backing int array called items plus a count called itemCt, and the two are kept separate so capacity and size can differ.

Programming

Why a List Needs Two Numbers

A plain array has one size, fixed when it is created. A list that can grow and shrink needs more than that. This article follows a Java class named DynamicArrayOfInt, which represents a list of int values that can grow and shrink. Its source code is short, but nearly every line matters, and the key to understanding it is a single question you should keep in mind as you read: where does the class decide whether an operation is allowed, and what information does it use to make that decision?

The answer to that question explains most of the class's behavior. The class does not rely on the length of its internal array to decide what is part of the list. It relies on a second number, and the difference between the two numbers is the whole design. By the end of this article you should be able to predict what each method does to those two numbers, and to say exactly where a surprising result comes from.

The Backing Array and the Item Count

Definition

A dynamic array in this source is a backing int array called items plus a count called itemCt. The two are kept separate so that capacity and size can differ. The length of items is the space that has been reserved. The value of itemCt is how many of those slots are actually holding meaningful values.

The class begins with an array of size 8. Its constructor sets items to a new int array of length 8, and nothing else in the class sets the array's length at construction. The item count starts with the default value of an int field, which is 0. So a freshly created list has eight reserved slots and zero meaningful values. The source's own comment describes items as partially full, and that phrase is the key to the design.

How do the items array and itemCt relate, and why does the array's length differ from the number of valid elements? Here the backing array has eight reserved slots, but itemCt is 3, so only the first three slots belong to the list.

Two numbers therefore describe the structure at any moment. The length of the backing array says how many values can be stored before the array must grow. The item count says how many values are currently part of the list. The size method returns itemCt, so a caller who asks for the size receives the count of meaningful items, not the reserved space. In the picture above, the list has size 3 even though the array has length 8.

Where the Guard Looks in get and set

The get and set methods let a caller read or change an element by its position. Both methods begin with the same guard. If the index is negative, or if it is not less than itemCt, the method throws an ArrayIndexOutOfBoundsException with a message that names the bad index. Only after the guard passes does the method touch the backing array. The guard is the first place to look when get or set behaves unexpectedly.

java

public int get(int index) {
    if (index < 0 || index >= itemCt) {
        throw new ArrayIndexOutOfBoundsException("Index: " + index);
    }
    return items[index];
}

public void set(int index, int value) {
    if (index < 0 || index >= itemCt) {
        throw new ArrayIndexOutOfBoundsException("Index: " + index);
    }
    items[index] = value;
}

public int get(int index) {
    if (index < 0 || index >= itemCt) {
        throw new ArrayIndexOutOfBoundsException("Index: " + index);
    }
    return items[index];
}

public void set(int index, int value) {
    if (index < 0 || index >= itemCt) {
        throw new ArrayIndexOutOfBoundsException("Index: " + index);
    }
    items[index] = value;
}

Notes on the code

The guard compares index against itemCt, not items.length.
Both methods use the same guard before touching items.
The exception message names the bad index.

Which positions are valid indices, and how does itemCt mark the boundary between valid slots and unused capacity? Indices 0 through 2 pass the guard; indices 3 through 7 exist in the backing array but are rejected.

Notice what the guard does not compare against. It does not use items.length. This means a slot in the backing array can exist and still be off limits. In the example above, items[3] through items[7] are real storage, but they are not yet part of the list. A caller cannot read or overwrite a value at an index beyond the last item that was added, even though the backing array has room there.

What do you think happens?

The list has three items and the backing array has length 8. What does get(3) do?

It returns 0, the default value in the unused slot
It throws ArrayIndexOutOfBoundsException
It returns the value stored in items[3]

Reveal answer

Answer:

It throws ArrayIndexOutOfBoundsException

The guard checks index against itemCt, which is 3. Index 3 is not less than 3, so the guard throws before items is read. The slot exists in the backing array, but it is not part of the list.

Growing the Backing Array Inside add

The add method appends a value to the end of the list. Its first line checks whether the list is full, which means itemCt has reached the length of the backing array. Only in that case does the method create a new array twice as large and copy the old values into it. Then it stores the new item at position itemCt and increases itemCt by one. The source describes the growth as a doubling performed with Arrays.copyOf(items, 2*items.length).

java

public void add(int value) {
    if (itemCt == items.length) {
        items = Arrays.copyOf(items, 2 * items.length);
    }
    items[itemCt] = value;
    itemCt++;
}

public void add(int value) {
    if (itemCt == items.length) {
        items = Arrays.copyOf(items, 2 * items.length);
    }
    items[itemCt] = value;
    itemCt++;
}

Notes on the code

The copy happens only when itemCt equals items.length.
The new item goes to position itemCt, the first unused slot.
itemCt grows by one on every successful add.

What does the array look like before and after growth, and what changes in the items reference and count when the array is full? Before the call the array has length 4 and is full; after the call the array has length 8, holds five items, and itemCt is 5.

On most calls to add the copy is skipped. The new item is stored directly into the existing array, and only the count changes. The doubling is therefore an occasional event that happens when the reserved space runs out, not something that happens on every add. Because the items reference is reassigned to the new array, the old array is no longer used by the list after the call.

Removing an Item and Shifting Left

The remove method deletes the item at a given index. It uses the same guard as get and set, so an invalid index throws an exception before anything changes. For a valid index, a loop moves every later item one position toward the front, overwriting the removed value. After the loop, itemCt decreases by one. The loop runs from index plus one up to the last item in use, and it stops at itemCt rather than at items.length, so slots beyond the list are never shifted.

java

public void remove(int index) {
    if (index < 0 || index >= itemCt) {
        throw new ArrayIndexOutOfBoundsException("Index: " + index);
    }
    for (int j = index + 1; j < itemCt; j++) {
        items[j - 1] = items[j];
    }
    itemCt--;
}

public void remove(int index) {
    if (index < 0 || index >= itemCt) {
        throw new ArrayIndexOutOfBoundsException("Index: " + index);
    }
    for (int j = index + 1; j < itemCt; j++) {
        items[j - 1] = items[j];
    }
    itemCt--;
}

Notes on the code

The guard runs first, so a bad index changes nothing.
The loop copies each later item one slot to the left.
The array is not reallocated or shrunk; only itemCt goes down.

Before

items: [10, 20, 30, 40, 0, 0, 0, 0]
itemCt: 4

Four items in use. remove(1) is called to delete the value 20.

After

items: [10, 30, 40, 40, 0, 0, 0, 0]
itemCt: 3

The values 30 and 40 each moved one slot left. The last slot still holds 40, but itemCt is 3, so that slot is no longer part of the list.

The stale value 40 left behind in items[3] is a useful thing to notice. It is still physically present in the backing array, but the guard treats it as off limits, and the next add will overwrite it. This is the same boundary logic described earlier: only the slots below itemCt belong to the list.

Tracing a Call from Start to Finish

Worked example

Adding two values, then reading past the end

Starting from a new DynamicArrayOfInt, call add(10), add(20), then get(2). Track items.length and itemCt at each step, and say where the result comes from.

1
Construction
items is a new int array of length 8 and itemCt is 0. The list is empty even though eight slots exist.
2
add(10)
The check itemCt == items.length asks whether 0 equals 8. It does not, so no copy happens. items[0] becomes 10 and itemCt becomes 1.
3
add(20)
Again 1 is not equal to 8, so no copy happens. items[1] becomes 20 and itemCt becomes 2.
4
get(2)
The guard checks whether 2 is less than 0 or not less than itemCt. Since 2 is not less than 2, the guard throws ArrayIndexOutOfBoundsException. The value in items[2] is never read, even though that slot exists in the array.

Result

After two adds, items.length is 8 and itemCt is 2. get(2) throws. The exception originates in the guard at the top of get, because the check uses itemCt, which has not yet reached index 2.

Finding Where an Unexpected Result Begins

When a dynamic array returns something unexpected, the fastest way to locate the problem is to ask three questions in order. The source frames these as a practical checklist, and each one corresponds to a part of the class you have already read.

1
What is itemCt at the moment of the call? Most index-related surprises come from a wrong belief about how many items the list holds.
2
Which guard was evaluated, and did it pass or throw? For get, set, and remove the guard is the first line of the method, so an exception always originates there.
3
If the call changed the list, did the change happen in items, in itemCt, or in both? An add that stores a value but leaves itemCt unchanged would be one example of a partial change to check for.

Mistakes Beginners Make with Indices and Capacity

Common mistake
Treating items.length as the size of the list
What it looks like
After two adds to a fresh list, assuming size() returns 8 because the array has length 8.
Why it fails
size() returns itemCt, which counts only the meaningful values. The length of items is the reserved space.
Do this instead
Read the size from itemCt, and read the capacity from items.length.
Common mistake
Expecting get to read a reserved but unused slot
What it looks like
Calling get(3) on a list with three items, expecting the default 0 from items[3].
Why it fails
The guard rejects any index that is not less than itemCt, so the method throws before the array is read.
Do this instead
Only indices from 0 through itemCt minus 1 are valid for get and set.
Common mistake
Assuming remove shrinks the backing array
What it looks like
Expecting items.length to drop after removing an element from a full array.
Why it fails
remove shifts items left and decreases itemCt, but it does not reallocate or shrink the backing array.
Do this instead
Expect items.length to stay the same after remove; only itemCt changes.
Common mistake
Believing add copies the array on every call
What it looks like
Thinking every add creates a new array, which would make each call expensive.
Why it fails
The copy happens only when itemCt equals items.length, so most adds store the item directly.
Do this instead
Check whether the reserved space is full; only then does the doubling occur.

Practice Tracing the Count

MEDIUM

Start from a new DynamicArrayOfInt. Call add(5), add(6), add(7), then remove(0). After the remove, what is itemCt, what value does get(0) return, and what happens if you call get(2)? Explain your answer by naming the guard that decides each result.

Hints

Track itemCt after each call; it starts at 0.
remove(0) shifts items[1] and items[2] left by one slot.
The guard for get compares the index with itemCt, not items.length.

Your attempt (not saved)

Key Takeaways

A dynamic array here is a backing int array called items plus a separate count called itemCt, so reserved capacity and meaningful size can differ.
get, set, and remove check the index against itemCt rather than items.length, so only values that are part of the list can be read or changed.
add doubles the backing array with Arrays.copyOf(items, 2*items.length) only when itemCt equals the array length, then stores the item and increases itemCt.
remove shifts later items left by one slot and decreases itemCt without reallocating or shrinking the backing array.
When a result is unexpected, check itemCt first, then the guard that was evaluated, then whether items, itemCt, or both changed.

Why a List Needs Two Numbers

The Backing Array and the Item Count

Where the Guard Looks in get and set

Growing the Backing Array Inside add

Removing an Item and Shifting Left

Tracing a Call from Start to Finish

Finding Where an Unexpected Result Begins

Mistakes Beginners Make with Indices and Capacity

Practice Tracing the Count

Key Takeaways

Related Topics