Dynamic 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. 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 making the collection itself grow and shrink while the program runs, so the programmer does not have to guess a size in advance. The design hides the internal array behind a small set of operations such as add, remove, get, set, and size. In this article we follow two concrete examples. The first is a phone directory that pairs names with numbers, which shows how a key leads to a value. The second is a growable integer collection, DynamicArrayOfInt, which shows how the count, the capacity, and the valid positions interact.

A phone directory answers one question over and over: given a person's name, what is their number? It also has to accept new entries and changes to existing ones. The directory stores each association as a single object that holds both halves of the pair. The name is the key, and the number is the value. Because the pair travels as one unit, the storage only needs to hold one kind of element. There is no need to keep two parallel arrays, one for names and one for numbers, and manually keep them in step.

The source's PhoneDirectory class places this idea in a nested class with a name field and a number field. Each stored element therefore carries its own key and its own value together. The ordering of the pairs does not carry meaning. The only thing the structure must preserve is which number belongs with which name. A caller who knows the name needs nothing else to retrieve the number.

The class keeps exactly two pieces of state. The first is an array of pairs. The second is an integer that counts how many pairs are actually stored. These are different quantities. The array has a length, which is its capacity, and the count records how many of those positions are filled. A constructor creates an initially empty directory by allocating a one-element array and setting the count to zero.

The find method is the heart of the directory, because both getNumber and putNumber depend on it. Its job is to search for a name and report where that name sits. It walks through the filled positions one at a time, starting from zero, and compares each stored name with the requested name. The comparison uses the equals method of the String class rather than the == operator. Two names therefore match when their characters are equal, not merely when they refer to the same object.

find has two possible outcomes. If a stored name matches, it returns the index of that pair as soon as the match is found, and the search stops there. If the loop finishes without a match, find returns -1. That value is a signal rather than a position. The two public methods interpret it differently. getNumber turns it into a null return value. putNumber uses it to decide that a new pair must be added. Because find is private, callers never invoke it directly. They only see its effects through getNumber and putNumber.

putNumber begins with a guard. If either argument is null, it throws an IllegalArgumentException with a message saying the name and number cannot be null. After the guard, it calls find. The result decides what happens next. If find returns a non-negative index, the name already exists. The method replaces the old number at that position with the new one, and the count does not change, because no new pair was created.

If find returns -1, the name is new. The method checks whether the array is full. If it is, the method doubles the array. It then creates a new pair, stores it at the position indicated by the count, and increases the count by one. Because the array doubles when it becomes full, the directory has no fixed size limit. The copy into the larger array is performed by the Arrays.copyOf library method, which takes the old array and the new length.

The DynamicArrayOfInt 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 source calls this the capacity. The second is the item count, which records how many of those slots hold meaningful values. The source calls this the size. The class stores the array in a field named items and the count in a field named itemCt. Because the array is usually only partly full, the length of items and the value of itemCt are usually different numbers.

The starting capacity of 8 is an arbitrary choice. Any positive integer would make the class work. Starting with a very large array would waste memory on programs that only ever hold a few items. The design relies on growth instead. When the array fills up, the class makes a bigger one, so the starting capacity affects only how often growth happens, not whether the class is correct.

The diagram shows the two numbers and the slots they describe. The count is 5, so five slots are meaningful. The length is 8, so the internal array has eight slots in total. The three unused slots at the end exist in memory but hold no item. Any operation that names a position must consult the count, not the length, to know which slots are meaningful.

Only add and remove change how many items the collection holds. get, set, and size leave the count alone. The state of the collection is therefore best followed call by call. The sequence below starts from an empty dynamic array and tracks the contents and the size after every step. Each step is generated for this article to show the rules the source describes. Read the sequence slowly and predict the state before checking the next row.

Notice what each call does to the count. Each add increases the size by one. set replaces a value at a valid position and leaves the size alone. remove slides every later value one position toward the front and decreases the size by one. get returns the value at a position without changing anything. In the trace, remove(0) moved the value 5 from position 1 forward into position 0, and the value 7 moved from position 2 forward into position 1. The final get(1) returns 7, the value now sitting at position 1.

The Python listing above is a generated mirror of the Java design described in the source, not the source's own code. It is included so you can see the count-based checks in a concrete form. Add is omitted here because its growth step is discussed in the section on growth and removal.

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. The slot at position itemCt exists inside the internal array, but it holds no item, so the class treats it as illegal.

The class behaves as if it can hold any number of items, but its 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 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 then 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 caller never has to resize anything.

Consider a full array of eight values. Adding a ninth value makes the class create a new array of length 16, copy the eight old values into the first eight slots, place the new value in slot 8, and leave the remaining seven slots free for later additions. The sizes in this example are illustrative, but the doubling rule is the one the class applies.

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 this class does not give that storage back after items are removed.