Tutorial: Custom Collection Implementations

Many programmers will never need to implement their own Collections classes. You can go pretty far using the implementations described in the preceding sections of this chapter. However, someday you might want to write your own implementation. It is fairly easy to do this with the aid of the abstract implementations provided by the Java platform. Before we discuss how to write an implementation, let's discuss why you might want to write one.

Reasons to Write an Implementation

The following list illustrates the sort of custom Collections you might want to implement. It is not intended to be exhaustive:

How to Write a Custom Implementation

Writing a custom implementation is surprisingly easy. The Java Collections Framework provides abstract implementations designed expressly to facilitate custom implementations. We'll start with the following example of an implementation of Arrays.asList.

public static <T> List<T> asList(T[] a) {
 return new MyArrayList<T>(a);
}
private static class MyArrayList<T> extends AbstractList<T> {
 private final T[] a;
 MyArrayList(T[] array) {
 a = array;
 }
 public T get(int index) {
 return a[index];
 }
 public T set(int index, T element) {
 T oldValue = a[index];
 a[index] = element;
 return oldValue;
 }
 public int size() {
 return a.length;
 }
}

Believe it or not, this is very close to the implementation that is contained in java.util.Arrays. It's that simple! You provide a constructor and the get, set, and size methods, and AbstractList does all the rest. You get the ListIterator, bulk operations, search operations, hash code computation, comparison, and string representation for free.

Suppose you want to make the implementation a bit faster. The API documentation for abstract implementations describes precisely how each method is implemented, so you'll know which methods to override to get the performance you want. The preceding implementation's performance is fine, but it can be improved a bit. In particular, the toArray method iterates over the List, copying one element at a time. Given the internal representation, it's a lot faster and more sensible just to clone the array.

public Object[] toArray() {
 return (Object[]) a.clone();
}

With the addition of this override and a few more like it, this implementation is exactly the one found in java.util.Arrays. In the interest of full disclosure, it's a bit tougher to use the other abstract implementations because you will have to write your own iterator, but it's still not that difficult.

The following list summarizes the abstract implementations:

The process of writing a custom implementation follows:

  1. Choose the appropriate abstract implementation class from the preceding list.
  2. Provide implementations for all the abstract methods of the class. If your custom collection is to be modifiable, you will have to override one or more of the concrete methods as well. The API documentation for the abstract implementation class will tell you which methods to override.
  3. Test and, if necessary, debug the implementation. You now have a working custom collection implementation.
  4. If you are concerned about performance, read the API documentation of the abstract implementation class for all the methods whose implementations you're inheriting. If any seem too slow, override them. If you override any methods, be sure to measure the performance of the method before and after the override. How much effort you put into tweaking performance should be a function of how much use the implementation will get and how critical to performance its use is. (Often this step is best omitted.)