Dynamic Array Implementation

A phone directory stores a list of names, each paired with a phone number. Given a name, you can look up its number. Given a name and a number, you can record that pairing, and if the name is already present, the new number replaces the old one. The Java class PhoneDirectory implements exactly these operations, and it does so with only one array and one counter. Because the state is that small, you can follow every change to it line by line.

The problem this article addresses is how the array can hold an unknown number of entries when Java arrays have a fixed length. The answer is a dynamic array: an array that is replaced by a larger copy when it runs out of room. The same idea appears in the DynamicArrayOfInt class, which applies it to a plain list of int values. Working through both classes gives you two views of one mechanism.

A dynamic array in this source is built from two pieces of state. The first is a backing array, a plain int array called items. The second is a count called itemCt. The two are kept separate on purpose, so that the capacity of the array and the number of meaningful values can differ. The array's length is the space that has been reserved. The item count says how much of that space is actually holding values that belong to the list.

PhoneDirectory uses the same split with different names. Its private array is called data, and its private integer dataCount records how many slots are in use. The pair type, PhoneEntry, is a private static nested class with a name field and a number field. Keeping both the array and the entry type private is an example of encapsulation: code outside the class never touches data directly and only calls the public methods getNumber and putNumber.

In this picture the backing array has eight slots, which matches the source's initialization of items to new int[8]. Three values have been added, so itemCt is 3. Slots 0 through 2 are the list. Slots 3 through 7 exist and have memory reserved for them, but they are not yet part of the list. The source calls the items array partially full, and that phrase is the key to the whole design. Two numbers describe the array at any moment: items.length says how many values can be stored before the array must grow, and itemCt says how many values are currently part of the list.

Every lookup and every update in PhoneDirectory depends on the private find method. It takes a name and scans the used part of the array, from index 0 up to but not including dataCount, comparing each stored name with the one it was given. If it finds a match, it returns that index. If the loop ends without a match, it returns -1. The loop bound is dataCount rather than data.length, so slots that have not been filled yet are never examined.

The same loop handles a successful search. If find(Ben) were called on that directory, the comparison at index 0 would fail, the comparison at index 1 would succeed, and find would return 1 immediately without checking the remaining positions. The search is a single left-to-right scan, and its stopping points are the first match or the bound dataCount, whichever comes first.

getNumber calls find. If find returns -1, getNumber turns that result into null, which signals that the name is absent. Otherwise it returns the number stored at the index find reported. The update method putNumber is more involved. Its first step is to check both arguments. If either the name or the number is null, it throws an IllegalArgumentException with the message name and number cannot be null. This check happens before find is called, so a null argument never reaches the search and never changes the directory.

After the null check, putNumber calls find. If the name is already present, the method replaces the number stored at that index and adds no new pair. If the name is absent, it adds a new pair in the next free slot and increases dataCount. This is the difference between replacement and insertion, and the directory's contents show which one happened.

In the diagram, Ann was previously stored with 555-0101. Because Ann is already present, putNumber finds index 0 and replaces the number there, so dataCount stays at 2. The two entries are still the only entries. A call to getNumber(Carl) would find no match, find would return -1, and getNumber would return null.

The constructor creates the PhoneDirectory array with a length of 1 and sets dataCount to 0. The resize happens inside putNumber, and only when a name is not already present. The code checks whether dataCount has reached data.length. If it has, the array is full, and the code replaces it with a copy that is twice as long. The doubling is performed with Arrays.copyOf, and it occurs only during an insert of a new name.

Because the constructor starts with length 1, the first insert does not trigger a copy. dataCount is 0 and data.length is 1, so the array has room. The second insert finds dataCount equal to data.length, so the array is doubled to length 2 before the new pair is stored. The existing entry is carried across into the larger array, and the new entry occupies the next free slot.

The DynamicArrayOfInt class follows the same pattern in its add method. Its first line checks whether itemCt has reached the length of the backing array. If it is full, the method creates a new array twice as large and copies the old values into it, using Arrays.copyOf(items, 2*items.length). Then it stores the new item at position itemCt and increases itemCt by one. The doubling happens only when the backing array is full. On most calls to add, the copy is skipped, and the new item is stored directly into the existing array.

The get and set methods let a caller read or change an element by its position. Both begin with the same guard. If the index is negative or 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 remove method uses the same guard, so an invalid index throws an exception there too.

The remove method deletes the item at a given index. After the guard passes, a loop moves every later item one position toward the front, overwriting the removed value. The loop runs from index plus one up to the last item in use. Each pass copies items[j] into items[j-1]. After the loop, itemCt decreases by one. The loop stops at itemCt, not at items.length, so slots beyond the list are never shifted. remove does not reallocate or shrink the backing array.

When a trace disagrees with your prediction, do not start by rereading the whole class. Compare your predicted state step by step with the recorded state, and find the first call where they differ. That call is the place to examine. When a dynamic array returns something unexpected, the fastest way to locate the problem is to ask three questions in order.

In the PhoneDirectory class, the usual suspects are the loop bound in find, the dataCount comparison that decides whether a resize happens, and the early null check in putNumber. In DynamicArrayOfInt, they are the itemCt guard in get, set, add, and remove, and the shifting loop in remove. A call that fails with an exception has its origin at the guard, because that is the first place the bad index or count is used.