Partially Full Arrays

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

This article builds a growable collection from the ground up. The design is a Java class called DynamicArrayOfInt. It stores its items in a plain array and wraps that array in a small set of operations, so a caller can add, remove, read, and change items without ever touching the internal array directly. Along the way we will answer three concrete questions: what operations the collection must support, how it keeps track of its contents, and what should happen when someone asks for a position that holds no value.

Many beginners look at an array and assume that every position inside it means something. If you declare an array of 100 integers, it seems natural to think that the program is storing 100 numbers. That assumption works 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. The array's length is still 100, and the array itself cannot change size. Something else has to record where the real data stops.

The fix is to stop relying on the array's length to describe its contents. The program keeps a separate integer variable, usually called a counter, that records how many positions are in use. The counter does not hold any of the numbers. It only keeps a tally of how many of the array's positions contain valid items.

Because the array is only partially full most of the time, capacity and size are usually different numbers. The class is written so that these two values are never confused. Every operation that deals with the contents of the collection is written in terms of the count, while the array length is used only when the class needs to know whether there is physical room left for a new value.

The diagram shows the situation the class has to manage. The first three slots hold items, and the count of 3 is the only thing that marks them as valid. The remaining five slots exist in the array and are reserved, but the class never reads them as data. The starting capacity of 8 is an arbitrary choice used for this example. Any positive integer would make the class work. A very large starting array would waste memory on programs that only ever hold a few items, which is why the design relies on growth rather than a big initial array.

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, it is worth reading its value both ways.

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. The counter is never used to decide whether a stored value is valid. It is updated only when a value is actually saved.

Every operation that names a position has to decide what to do with a position that does not hold a value. The class decides to throw 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 valid positions run from 0 through itemCt minus 1. With a size of 4, that means indexes 0 to 3. The slot at position 4 exists in the internal array, because the array has length 8, but it holds no item. The class treats it as illegal anyway. This is the detail that catches most readers: the upper limit is the size, not the length.

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. Only add and remove change how many items the collection holds. get, set, and size leave the count alone. That split is useful when reading the class: any method that touches itemCt is a method whose effect on the collection's shape needs careful thought.

Notice that set and get never move the count. Only add and remove do, and remove does so by shifting values rather than by shrinking storage. When you trace a sequence, the count is the number you should check first, because it tells you which indexes are legal at the next call.

The class behaves as if it can hold any number of items, but the internal array has a fixed length. The trick happens in 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. In the example from earlier, starting at capacity 8, the first eight adds need no growth. A ninth add would find the array full, double it to 16, copy the eight old values across, and then place the new value in the first free position.

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.

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.

Counting protects a program only if the count stays inside the array's bounds. A plain array does not resize. Suppose it was created with a fixed number of positions and the program keeps storing values. Once the count reaches the array's length, the next value has no valid place to go. The program would attempt to store it in a position that does not exist, and Java raises an ArrayIndexOutOfBoundsException at run time.