Section 15.2. Implementing List

15.2. Implementing List

There are three concrete implementations of List in the Collections Framework (see Figure 15.3), differing in how fast they perform the various operations defined by the interface and how they behave in the face of concurrent modification; unlike Set and Queue, however, List has no subinterfaces to specify differences in functional behavior. In this and the following section we look at each implementation in turn and provide a performance comparison.

Figure 15-3. Implementations of the List interface

15.2.1. ArrayList

Arrays are provided as part of the Java language and have a very convenient syntax, but their key disadvantagethat, once created, they cannot be resizedmakes them increasingly less popular than List implementations, which (if resizable at all) are indefinitely extensible. The most commonly used implementation of List is, in fact, ArrayListthat is, a List backed by an array.

The standard implementation of ArrayList stores the List elements in contiguous array locations, with the first element always stored at index 0 in the array. It requires an array at least large enough (with sufficient capacity) to contain the elements, together with a way of keeping track of the number of "occupied" locations (the size of the List). If an ArrayList has grown to the point where its size is equal to its capacity, attempting to add another element will require it to replace the backing array with a larger one capable of holding the old contents and the new element, and with a margin for further expansion (the standard implementation actually uses a new array that is double the length of the old one). As we explained in Section 11.3, this leads to an amortized cost of O(1).

The performance of ArrayList reflects array performance for "random-access" operations: set and get take constant time. The downside of an array implementation is in inserting or removing elements at arbitrary positions, because that may require adjusting the position of other elements. (We have already met this problem with the remove method of the iterators of array-based queuesfor example, ArrayBlockingQueue (see Section 14.3.2). But the performance of positional add and remove methods are much more important for lists than iterator.remove is for queues.)

For example, Figure 15.4(a) shows a new ArrayList after three elements have been added by means of the following statements:

Figure 15-4. Removing an element from an ArrayList

 List<Character> charList = new ArrayList<Character>(); Collections.addAll(charList, 'a', 'b', 'c'); 

If we now want to remove the element at index 1 of an array, the implementation must preserve the order of the remaining elements and ensure that the occupied region of the array is still to start at index 0. So the element at index 2 must be moved to index 1, that at index 3 to index 2, and so on. Figure 15.4(b) shows our sample ArrayList after this operation has been carried out. Since every element must be moved in turn, the time complexity of this operation is proportional to the size of the list (even though, because this operation can usually be implemented in hardware, the constant factor is low).

Even so, the alert reader, recalling the discussion of the circular arrays used to implement ArrayBlockingQueue and ArrayDeque (see Section 14.4.1) may wonder why a circular array was not chosen for the implementation of ArrayList, too. It is true that the add and remove methods of a circular array show much better performance only when they are called with an index argument of 0, but this is such a common case and the overhead of using a circular array is so small, that the question remains.

Indeed, an outline implementation of a circular array list was presented by Heinz Kabutz in http://www.javaspecialists.co.za/archive/Issue027.html). In principle it is still possible that ArrayList may be reimplemented in this way, possibly leading to real performance gains in many existing Java applications. A possible alternative is that the circular ArrayDeque may be retrofitted to implement the methods of List. In the meantime, if your application is using a List in which the performance of element insertion and removal from the beginning of a list is more important than that of random-access operations, consider writing to the Deque interface and taking advantage of its very efficient ArrayDeque implementation.

As we mentioned in the discussion of ArrayBlockingQueue (Section 14.2), variable-size array-backed collection classes can have one configuration parameter: the initial length of the array. So besides the standard Collections Framework constructors, ArrayList has one that allows you to choose the value of the initial capacity to be large enough to accommodate the elements of the collection without frequent create-copy operations. The initial capacity of an ArrayList created by the default constructor is 10, and that of one initialized with the elements of another collection is 110% of the size of that collection.

The iterators of ArrayList are fail-fast.

15.2.2. LinkedList

We discussed LinkedList as a Deque implementation in Section 14.4.1. You will avoid it as a List implementation if your application makes much use of random access; since the list must iterate internally to reach the required position, positional add and remove have linear time complexity, on average. Where LinkedList does have a performance advantage over ArrayList is in adding and removing elements anywhere other than at the end of the list; for LinkedList this takes constant time, against the linear time required for noncircular array implementations.

15.2.3. CopyOnWriteArrayList

In Section 13.1 we met CopyOnWriteArraySet, a set implementation designed to provide thread safety together with very fast read access. CopyOnWriteArrayList is a List implementation with the same design aims. This combination of thread safety with fast read access is useful in some concurrent programs, especially when a collection of observer objects needs to receive frequent event notifications. The cost is that the array which backs the collection has to be treated as immutable, so a new copy is created whenever any changes are made to the collection. This cost may not be too high to pay if changes in the set of observers occur only rarely.

The class CopyOnWriteArraySet in fact delegates all of its operations to an instance of CopyOnWriteArrayList, taking advantage of the atomic operations addIfAbsent and addAllAbsent provided by the latter to enable the Set methods add and addAll to avoid introducing duplicates to the set. In addition to the two standard constructors (see Section 12.3), CopyOnWriteArrayList has an extra one that allows it to be created using the elements of a supplied array as its initial contents. Its iterators are snapshot iterators, reflecting the state of the list at the time of their creation.