Implementing a Collection Class - Building Java Programs: A Back to Basics Approach - page 908

copy 1000 values from the old array to the new array. But you won't need to copy
again for a while. You can add another 999 values before you'd need extra space. As
a result, we think of the expense as being spread out or amortized over all 1000 calls
on add . When the cost is spread out over 1000 adds, it is fairly low (a constant).
The built-in ArrayList class does something similar. The documentation is a
little coy about this: “The details of the growth policy are not specified beyond the
fact that adding an element has constant amortized time cost.” If you look at the
actual code, you'll find that it increases the capacity by 50% each time (a multi-
plier of 1.5).
So how do you add this functionality to your ArrayIntList class? You included a
method called checkCapacity that throws an exception if the array isn't big enough.
You can simply replace this method with a new method that makes the array larger if
necessary:
public void ensureCapacity(int capacity) {
if (capacity > elementData.length) {
int newCapacity = elementData.length * 2 + 1;
if (capacity > newCapacity) {
newCapacity = capacity;
}
int[] newList = new int[newCapacity];
for (int i = 0; i < size; i++) {
newList[i] = elementData[i];
}
elementData = newList;
}
}
This version of the method works, but you can get a slight improvement by calling
a built-in method called Arrays.copyOf that returns a copy of an array. It has the
same functionality as the preceding code, but it is likely to run faster because this
operation is what is known as a block copy operation that can be optimized to run
faster. Thus, the method can be rewritten as follows:
public void ensureCapacity(int capacity) {
if (capacity > elementData.length) {
int newCapacity = elementData.length * 2 + 1;
if (capacity > newCapacity) {
newCapacity = capacity;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
}