Array Index Bounds and Exceptions

Imagine a game that keeps a roster of the players currently taking part in a match. Players join partway through, and leave when they are eliminated. The roster has to reflect those changes at every moment. An ordinary array can hold the players, but its length is fixed when it is created. If you choose a length that is too small, you run out of room. If you choose one that is too large, you waste space and still have to keep track of which slots are actually in use.

A dynamic array solves this by letting the collection itself grow and shrink, so the programmer does not have to guess a size in advance. This article builds a growable collection of ints, a Java class named DynamicArrayOfInt that stores its items in a plain array and wraps that array in operations a caller can use safely. Its central question is what happens when someone asks for a position that does not hold a value.

The class holds two different numbers, and most early bugs come from mixing them up. The first is the length of the internal array, which is the number of slots that exist. The second is the item count, which records how many of those slots currently hold meaningful values. This article calls the first the capacity and the second the size. In the class, the array is stored in a field named items, and the count is stored in a field named itemCt. Because the array is usually only partly full, items.length and itemCt are usually different numbers.

The diagram shows a capacity of 8 and a size of 3. Slots 0 through 2 hold real values, and the remaining five slots are spare room. The class relies on itemCt, not on items.length, to know how much of the array is meaningful. The capacity is the storage that exists; the size is the part of that storage the collection is using.

A useful dynamic array needs a small, fixed set of operations. Each one is an instance method of the class, so a caller writes something like roster.add(7) rather than manipulating the internal array directly. The five essential operations are add, remove, get, set, and size. Their roles are these: add places a new value at the end of the collection, remove deletes the value at a position, get reads the value at a position, set replaces the value at a position, and size reports how many items the collection holds.

Only add and remove change how many items the collection holds. get, set, and size leave the count alone. This split is useful when reading the class: any method that touches itemCt is a method whose effect on the collection's shape you need to think about carefully.

The best way to see how these operations interact is to trace them one at a time. Follow the state after each call: the size, the values in the positions that hold items, and the capacity. This example starts with an empty collection whose capacity is 8.

The before and after columns show what remove does. Every later value moved one position toward the front, and the count dropped by one. The position that used to hold the last value is no longer part of the collection, even though the storage slot is still there.

Every operation that names a position has to decide what to do with a position that holds no value. The class throws an ArrayIndexOutOfBoundsException. The check is the same in get, set, and remove: the index is rejected if it is negative, or if it is greater than or equal to itemCt. The important detail is the upper limit. Because itemCt counts the items, the valid positions run from 0 through itemCt minus 1.

With a size of 5, the valid indices are 0, 1, 2, 3, and 4. Index 5 is rejected. The slot at position 5 may physically exist in the internal array, especially when the capacity is larger than the size, but it holds no item. The class checks the count, not the storage length, so that slot is treated as illegal.

The class behaves as if it can hold any number of items, but its internal array has a fixed length. The growth happens inside add. Before writing a new value, add checks whether itemCt has reached items.length. If it has, the array is full. The method then asks Arrays.copyOf for a new array with twice the length, copies the existing values into it, and makes items refer to the new array. Only after that does add store the new value at position itemCt and increase itemCt by one.

Because every add that finds a full array doubles the capacity, the storage grows as needed and the caller never has to resize anything. Suppose the capacity is 8 and all 8 slots hold values. A ninth call to add first copies the eight old values into a new array of length 16, places the ninth value at position 8, and sets the size to 9. The eight old values survive the move, the new value lands in the first free position, and the remaining slots of the larger array wait to be used. The doubling rule is the one the class applies; the sizes in this example are illustrative values chosen to show it.

Removal works in the opposite direction, and it is worth noticing what it does not do. The remove method slides every later value one position toward the front, then decreases itemCt by one. It never shrinks the internal array. The capacity stays what it was, and only the count changes. A dynamic array can therefore grow its storage, but the code in this class does not give that storage back after items are removed.

Writing a separate class for every element type would be tedious. A DynamicArrayOfString would be needed for strings, a DynamicArrayOfPlayer for players, and so on. Java avoids that repetition with a built-in standard class, ArrayList, which implements dynamic arrays and can hold any type of data. It follows the same design ideas developed in this article: a growable collection with operations to add, remove, get, and set items.