Linear Search in Arrays

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. This article follows a Java class called PhoneDirectory that handles both jobs using only an array and a few integer counters. Nothing in it is exotic. The interest lies in how a handful of simple decisions combine into a working data structure: where to look for a name, what to do when the name is already present, and what to do when storage runs out.

Keep the two public operations in mind as you read: one gets a number and one puts a number. Each takes a name as input. The rest of the article shows how the class carries out both jobs and why it sometimes returns null, sometimes replaces a value, and sometimes grows its storage.

The directory stores each association as a single object that holds both halves of the pair. The class has a nested type with a name field and a number field, so each stored element carries its own key and its own value together. Because the pair travels as one unit, the array only needs to hold one kind of element. The alternative would be two parallel arrays, one of names and one of numbers, which must be kept in step with each other on every insertion and replacement.

The name is the only thing a caller needs in order to retrieve the number. The structure only has to preserve which number belongs with which name. Its meaning does not depend on any ordering of the names.

The class keeps two pieces of state. The first is an array of pairs. The second is an integer, dataCount, that counts how many pairs are actually stored. These are different quantities. The array has a length, which is its capacity, and dataCount 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 class, because both getNumber and putNumber depend on it. Its job is to search the array for a name and report where that name sits. It walks through the filled positions one at a time, starting from index zero, and compares each stored name with the requested name. This is a linear search: it visits positions in order until it finds a match or runs out of filled positions.

In the diagram, the directory holds two pairs, so dataCount is 2. The scan compares Cy with Ana at index zero, then with Ben at index one. Neither matches. Index two is outside the filled positions, so the scan does not look at it. The search is restricted to the filled positions and does not examine unused slots.

find has two possible outcomes. If a stored name matches, it returns the index of that pair as soon as the match is found. If the loop finishes without a match, find returns -1. That value is a signal, not a position. No valid index is negative, so -1 can never be confused with a real location.

The two public methods interpret the signal differently. getNumber turns -1 into a null return value. putNumber uses -1 to decide that a new pair must be added. The same internal result therefore leads to two different behaviors depending on the caller's purpose.

putNumber begins with a guard. If either argument is null, it throws an IllegalArgumentException saying that the name and number cannot be null. After the guard, it calls find. If find returns a non-negative index, the name already exists, and the method replaces the old number at that position with the new one. The count does not change, because no new pair was created. If find returns -1, the method adds a new pair at the position indicated by dataCount and then increases dataCount by one.

In the before and after views, only index zero changed. The number was overwritten in place, and dataCount stayed at 2. Replacing a value and adding a value leave different traces in the state, which is why counting carefully matters when you debug.

Appending a new pair needs a free slot. When dataCount equals the array length, every position is occupied, and the method cannot store the new pair. The source's approach is to create a larger array with twice the length, copy the existing pairs into it, and then continue. The copy is performed by the Arrays.copyOf library method, which takes the old array and the new length. Because the array can keep doubling, the directory has no fixed size limit.

A program using the directory may return something unexpected. The useful question is where in the sequence of calls the actual result departed from the expected one. Work through the operations in order and check the state after each one. For a getNumber call, ask whether find returned the index you expected. For a putNumber call, ask whether find returned -1 or a non-negative index, since that decides whether the count grows.

Divergence usually shows up first in the count or in a single stored number. Tracing forward from the last point where expected and actual results still agreed identifies the step responsible. If the count is higher than you predicted, check whether a put call treated an existing name as new. If a lookup returns null for a name you believed was stored, check whether the name was spelled differently, since find compares characters with equals.