Previous | Next | Trail Map | Collections | Contents

Custom Implementations

Many programmers will never need to implement their own collections classes. You can go pretty far using the implementations described in the previous sections of this lesson. Someday, however, you might find yourself wanting to write your own implementation of a core collection interface. It turns out that it's easy to do with the abstract implementations provided by the Java platform. But before we discuss how to write an implementation, let's discuss why you might want to do such a thing.

Reasons to Write Your Own Implementation

This list enumerates several kinds of 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 with the aid of the abstract implementations furnished by the Java platform. Abstract implementations are skeletal implementations of the core collection interfaces designed expressly to facilitate custom implementations. We'll start with an example. Here's an implementation of Arrays.asList(in the API reference documentation).
    public static List asList(Object[] a) {
	return new ArrayList(a);
    }

    private static class ArrayList extends AbstractList
    				   implements java.io.Serializable
    {
	private Object[] a;

	ArrayList(Object[] array) {
	    a = array;
	}

	public Object get(int index) {
	    return a[index];
	}

	public Object set(int index, Object element) {
	    Object oldValue = a[index];
	    a[index] = element;
	    return oldValue;
	}

	public int size() {
	    return a.length;
	}
    }
Believe it or not, this is almost exactly the implementation contained in the JDK. It's that simple! You provide a constructor, 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 the abstract implementations describes precisely how each method is implemented so you'll know which methods to override in order to get the performance that you want. The performance of the implementation above 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 similar one for toArray(Object[]), this implementation is exactly the one found in the JDK. In the interests of full disclosure, it's a bit tougher to use the other abstract implementations because they require you to write your own iterator, but it's still not that hard.

The abstract implementations are summarized below:

The process of writing a custom implementation is summarized below:
  1. Choose the appropriate abstract implementation class from the list above.

  2. Provide implementations for all of the class's abstract methods. If your custom collection is to be modifiable, you'll have to override one or more 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're concerned about performance, read the abstract implementation class's API documentation for all of the methods whose implementations you're inheriting. If any of them 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 the performance should be a function of how much use the implementation will get, and how performance-critical the use. (Often, this step is best omitted.)


Previous | Next | Trail Map | Collections | Contents