List Implementations That Use Arrays - Data Structures and Abstractions with Java - page 323

method has an implementation much like the one you saw in Segment 2.37 of Chapter 2 for the
class ResizableArrayBag . Moreover, the definition of ensureCapacity , which appears at the end
of Listing 13-1, as well as the definition of the method toArray are analogous to the correspond-
ing methods in ResizableArrayBag .

13.7

Testing the partial implementation. You should now write a main method to test what you have
completed at this point. Testing a class should begin well before its implementation is complete. To
avoid syntax errors in the incomplete class in Listing 13-1, make the incomplete methods stubs by
adding to each one a return statement that returns a dummy value. For example, methods that
return a boolean value could return true. Methods that return an object could return null . You can
provide the actual definitions of methods, such as getLength and isEmpty , as they are just as sim-
ple as their stubs would be.
As you define more methods, test them by adding statements to main . As Appendix B notes,
you can include your method main in the definition of AList for future use and reference.

13.8

The second add method. Adding a new entry at an arbitrary position within the list is like adding a
student to room A in our example in Segment 13.2. Although that example positions students
alphabetically by their names, remember that the list's client—not the list itself—determines the
desired position of each entry. Thus, if that position is before the end of the list, we need to shift
existing entries to vacate the desired location so that it can accommodate the new entry. If the addi-
tion is to the end of the list, no such shift is necessary. In either case, space must be available in the
array to accommodate a new entry.
The following implementation of add uses a private method makeRoom to handle the details of
moving data within the array. Remember that we can add to the list at positions that range from 1 to
the length of the list plus 1. According to the method's specifications given in Segment 12.7 of the
previous chapter, we must return false if the given position is invalid.

public boolean add( int newPosition, T newEntry)
{

boolean isSuccessful = true ;
if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1))
{

ensureCapacity();
makeRoom(newPosition);
list[newPosition - 1] = newEntry;
numberOfEntries++;

}
else
isSuccessful = false ;
return isSuccessful;
} // end add

13.9

The private method makeRoom . Now we must implement the private method makeRoom . Typically,
the method shifts list entries toward the end of the array, beginning with the last entry, as Figure 13-4
illustrates. However, if newPosition is numberOfEntries + 1, the addition is at the end of the list, so
no shift is necessary. In this case, makeRoom does nothing, since its for statement exits immediately.

// Makes room for a new entry at newPosition.
// Precondition: 1 <= newPosition <= numberOfEntries+1;
// numberOfEntries is list's length before addition.
private void makeRoom( int newPosition)
{

assert (newPosition >= 1) && (newPosition <= numberOfEntries + 1);