Reference types - Data Structures and Problem Solving Using Java - page 41

figure 2.5
Array expansion,
internally: (a) At the
starting point, arr
represents 10
integers; (b) after
step 1, original
represents the same
10 integers; (c) after
steps 2 and 3, arr
represents 12
integers, the first 10
of which are copied
from original ; and
(d) after step 4, the
10 integers are
available for
reclamation.

arr

(a)

arr

original

(b)

arr

original

(c)

arr

original

(d)

int [ ] original = arr; // 1. Save reference to arr
arr = new int [ 12 ]; // 2. Have arr reference more memory
for( int i = 0; i < 10; i++ ) // 3. Copy the old data over
arr[ i ] = original[ i ];
original = null; // 4. Unreference original array

A moment's thought will convince you that this is an expensive opera-
tion. This is because we copy all of the elements from original back to arr .
If, for instance, this array expansion is in response to reading input, it
would be inefficient to reexpand every time we read a few elements. Thus
when array expansion is implemented, we always make it some multiplica-
tive constant times as large. For instance, we might expand it to be twice as
large. In this way, when we expand the array from N items to 2 N items, the
cost of the N copies can be apportioned over the next N items that can be
inserted into the array without an expansion.
To make things more concrete, Figures 2.6 and 2.7 show a program that
reads an unlimited number of strings from the standard input and stores the
result in a dynamically expanding array. An empty line is used to signal the
end of input. (The minimal I/O details used here are not important for this
example and are discussed in Section 2.6.) The resize routine performs the
array expansion (or shrinking), returning a reference to the new array. Simi-
larly, the method getStrings returns (a reference to) the array where it will
reside.

Always expand the
array to a size that
is some multiplica-
tive constant times
as large. Doubling
is a good choice.