Bag Implementations That Use Arrays - Data Structures and Abstractions with Java - page 48

2.34

The code. While we could simply translate the previous pseudocode into Java, much of the work
can be done by using the method Arrays.copyOf , which is in the Java Class Library. For example,
let's work with a simple array of integers:
int [] myArray = {10, 20, 30, 40, 50};
At this point, myArray references the array, as Figure 2-10a shows. Next, we'll call Arrays.copyOf .
The method's first parameter, sourceArray , is assigned the reference in the variable myArray , as
Figure 2-10b implies. Next the method creates a new, larger array and copies the entries in the argument
array to it (Figure 2-10c). Finally, the method returns a reference (Figure 2-10d) to the new array, and we
assign this reference to myArray (Figure 2-10e). The following statement performs these steps:
myArray = Arrays.copyOf(myArray, 2 * myArray.length);

FIGURE 2-10

The effect of the statement
myArray = Arrays.copyOf(myArray, 2 * myArray.length);
(a) The argument array; (b) the parameter that references the
argument array; (c) a new, larger array that gets the contents of the
argument array; (d) the return value that references the new array;
(e) the argument variable is assigned the return value

(a)

myArray 10 20 30 40 50

sourceArray

(b)

10 20 30 40 50

newArray

0 0 0 0 0

(c)

The method Arrays.copyOf

(d)

myArray (e)

2.35

Resizing an array is not as attractive as it might first seem. Each time you expand the size of
an array, you must copy its contents. If you were to expand an array by one element each
time you needed additional space in the array, the process would be expensive in terms of
computing time. For example, if a 50-element array is full, accommodating another entry
would require you to copy the array to a 51-element array. Adding yet another entry would
require that you copy the 51-element array to a 52-element array, and so on. Each addition
would cause the array to be copied. If you added 100 entries to the original 50-entry array,
you would copy the array 100 times.
However, expanding the array by m elements spreads the copying cost over m additions
instead of just one. Doubling the size of an array each time it becomes full is a typical approach.
For example, when you add an entry to a full array of 50 entries, you copy the 50-element array
to a 100-element array before completing the addition. The next 49 additions then can be made
quickly without copying the array. Thus, you will have copied the array only once.