Generic Arrays in Java

I have often found the need for a customized ArrayList. One reason is the inefficiency of Collections.sort(). The Sun implementation creates a temporary array to hold the collection. In the case of an ArrayList, this is unneeded overhead.

A dynamic array implementation seems simple enough, but generic arrays in Java are a tricky business. Your first attempt might look something like this:

class DArray<T> {
  T[] values;

  DArray(int size) {
    values = new T[size];
  }

  public static void main(String[] args) {
    DArray<String> a = new DArray<String>(10);
    a.values[0] = "test";
  }
}

To someone unfamiliar with Java generics the code looks ok, but a problem lurks. Compilation fails at new T[size].

Java implements generics with type erasure. A generic class is shared with all of its instances. The actual type of a parameterized type is not available to an instance at run time. Therefore Java forbids generic array creation. The consequences of type erasure are not always obvious.

A second attempt at DArray might try to allocate the array like so:
values = (T[]) new Object[size];

The modified DArray compiles, but throws a class cast exception when the test code is run. At first glance, a class cast exception seems like a strange error. After type erasure DArray.values is of type Object[]. Storing a String, a subtype of Object, in an Object[] array is allowed.

The exact exception thrown is java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast
to [Ljava.lang.String;. When run the test code tries to cast DArray.values to type String[] and fails.
You can disassemble the class with javap and see the checkcast. The compiler inserts type checking into
code which uses generics in order to guarantee type safety.

The solution:

import java.lang.reflect.Array;

class DArray<T> {
  T[] values;
  Class<T> type;

  DArray(Class<T> type, int size) {
    this.type = type;
    this.values = (T[]) Array.newInstance(type, size);
  }

  public static void main(String[] args) {
    DArray<String> a = new DArray<String>(String.class, 10);
    a.values[0] = "test";
  }
}

The key is using Array.newInstance. The code which uses DArray passes the element type to the
DArray constructor. Then Array.newInstance can create an array of the correct type at runtime.

For a full example of an ArrayList replacement, see ObjArray.java. For detailed information on generics, see this tutorial.