Section 6.7. How to Define ArrayList

6.7. How to Define ArrayList

We have argued elsewhere that it is usually preferable to use a list than to use an array. There are a few places where this is not appropriate. In rare circumstances, you will need to use an array for reasons of efficiency or compatibility. Also, of course, you need to use arrays to implement ArrayList itself. Here we present the implementation of ArrayList as a model of what to do in the rare circumstance where you do need to use an array. Such implementations need to be written with care, as they necessarily involve use of unchecked casts. We will see how the Principles of Indecent Exposure and of Truth in Advertising figure in the implementation.

Example 6.2 shows the implementation. We have derived ArrayList by subclassing from AbstractList. Classes derived from this class need to define only four methods, namely get, set, add, and remove; the other methods are defined in terms of these. We also indicate that the class implements RandomAccess, indicating that clients of the class will have more efficient access using get than using the list iterator.

Example 6-2. How to define ArrayList

 import java.util.*; class ArrayList<E> extends AbstractList<E> implements RandomAccess {   private E[] arr;   private int size = 0;   public ArrayList(int cap) {     if (cap < 0)       throw new IllegalArgumentException("Illegal Capacity: "+cap);     arr = (E[])new Object[cap];  // unchecked cast   }   public ArrayList() { this(10); }   public ArrayList(Collection<? extends E> c) { this(c.size()); addAll(c); }   public void ensureCapacity(int mincap) {     int oldcap = arr.length;     if (mincap > oldcap) {       int newcap = Math.max(mincap, (oldcap*3)/2+1);       E[] oldarr = arr;       arr = (E[])new Object[newcap];  // unchecked cast       System.arraycopy(oldarr,0,arr,0,size);     }   }   public int size() { return size; }   private void checkBounds(int i, int size) {     if (i < 0 || i >= size)       throw new IndexOutOfBoundsException("Index: "+i+", Size: "+size);   }   public E get(int i) { checkBounds(i,size); return arr[i]; }   public E set(int i, E elt) {     checkBounds(i,size); E old = arr[i]; arr[i] = elt; return old;   }   public void add(int i, E elt) {     checkBounds(i,size+1); ensureCapacity(size+1);     System.arraycopy(arr,i,arr,i+1,size-i); arr[i] = elt;  size++;   }   public E remove(int i) {     checkBounds(i,size); E old = arr[i];  arr[i] = null;  size--;     System.arraycopy(arr,i+1,arr,i,size-i); return old;   }   public <T> T[] toArray(T[] a) {     if (a.length < size)       a = (T[])java.lang.reflect.Array.  // unchecked cast                newInstance(a.getClass().getComponentType(), c.size());     System.arraycopy(arr,0,a,0,size);     if (size < a.length) a[size] = null;     return a;   }   public Object[] toArray() { return toArray(new Object[0]); } } 

The class represents a list with elements of type E by two private fields: size of type int containing the length of the list, and arr of type E[] containing the elements of the list. The array must have a length at least equal to size, but it may have additional unused elements at the end.

There are two places where new instances of the array are allocated, one in the initializer for the class and one in the method that increases the array capacity (which in turn is called from the add method). In both places, the array is allocated as an Object[] and an unchecked cast is made to type E[].

It is essential that the field containing the array is private; otherwise, it would violate both the Principle of Truth in Advertising and the Principle of Indecent Exposure. It would violate the Principle of Truth in Advertising because E might be bound to a type (such as String) other than Object. It would violate the Principle of Indecent Exposure because E might be bound to a type (such as List<Integer>) that is not a reifiable type. However, neither of these principles is violated because the array is not public: it is stored in a private field, and no pointer to the array escapes from the class. We might call this the Principle of Anything Goes Behind Closed Doors.

The way we've defined ArrayList here is close to the actual definition in the source released by Sun. Recently, Neal Gafter, the coauthor of that library, has argued that he used bad stylethat it would have been better to declare the private array to have type Object[] and use casts to type (E) when retrieving elements from the array. There is something to be said for this point, although there is also something to be said for the style we have used here, which minimizes the need for unchecked casts.

The method toArray does return an array in public, but it uses the techniques described in Section 6.5 in accordance with the Principle of Truth in Advertising. As before, there is an argument array, and if it is not big enough to hold the collection, then reflection is used to allocate a new array with the same reified type. The implementation is similar to the one we saw earlier, except that the more efficient arraycopy routine can be used to copy the private array into the public array to be returned.