Collections (sometimes called containers) are holders that let you store and organize objects in useful ways for efficient access. What will be efficient depends on how you need to use the collection, so collections come in many flavors. Most programming environments provide some collection types, ranging from impoverished up through gargantuan.

In the package java.util you will find interfaces and classes that provide a generic collection framework. This framework gives you a consistent and flexible set of collection interfaces and several useful implementations of these interfaces. You've already been briefly introduced to some of these, such as the interfaces List, Set, Map, and Iterator, and implementations ArrayList and HashMap.

The collection framework is designed to be concise. The principle is to have a core set of valuable collection abstractions and implementations that are broadly useful, rather than an exhaustive set that is complete but conceptually complex and unwieldy.

One way to keep the size down is to represent broad abstractions in the interfaces rather than fine-grained differences. Notions such as immutability and resizability are not represented by different interface types. The core collection interfaces provide methods that allow all common operations, leaving it to specific implementations to refuse to execute particular improper operations by throwing the unchecked java.lang.UnsupportedOperationException.

Figure 21-1 shows the collections interfaces and the concrete implementations provided directly in java.util.^[1] The collections interfaces are

Figure 21-1. Type Trees for Concrete Collections in java.util

The interfaces SortedSet and SortedMap guarantee that iteration through the elements is done in sorted order. You will learn how to define an order for objects later in this chapter.

The java.util package also provides several useful concrete implementations of these interfaces that will suffice for most of your needs. For example:

Nearly all the implementation classes in java.util are both Cloneable and Serializable. The exceptions are PriorityQueue which is not Cloneable, and WeakHashMap which is neither.

In this chapter you first learn about iteration because it is useful with all the collection classes. We then cover ordering since it is used by many of the collection types. We then present the details of the Collection-based types, followed by the Map-based types. After that we look at the various utilities available, and we show you how to make unmodifiable and type-safe versions of your collections. Next we show you the synchronized and concurrent collections. You will then learn how to write your own iteration and collection types in case you have a need that the provided classes do not fill. Finally, we cover the “legacy collections” in java.util that predate the overall collection system, but which you will find in some existing code. One of these legacy collection types—Properties—continues in common use.

For simplicity, we usually refer to the various interfaces without mentioning their type parameters—for example, Iterator or Collection—except where it is necessary to show that the same type parameter is being used—for example, that iterator has a return type Iterator<E> for a Collection<E>.

You've encountered iteration several times already during the course of this book—particularly in the discussion of the enhanced for loop in Chapter 10. This section reviews the basic operation of an iterator and covers its additional capabilities and the additional iterator types.

Collection<E> extends Iterable<E>, which defines an iterator method that returns an object that implements the Iterator<E> interface:

The following code uses all three methods of Iterator to remove all long strings from a collection:

public void removeLongStrings
    (Collection<? extends String> coll, int maxLen) {
    Iterator<? extends String> it = coll.iterator();
    while (it.hasNext()) {
        String str = it.next();
        if (str.length() > maxLen)
            it.remove();
    }
}

First we use iterator to get an Iterator object that steps through the contents of the collection one element at a time (recall that the enhanced for loop can't be used when you want to remove elements using the iterator). Then we loop as long as hasNext returns true to indicate that there is at least one more element left in the iteration. Each time through the loop we get the next element of the list using next. If any string is longer than the maximum allowed length, we use the iterator's remove method to remove the most recent element returned by next. When you use an iterator's remove method you modify the underlying collection safely for that iterator—the iterator will properly move through the subsequent elements of the collection. Removing elements from the collection any other way (using operations on the collection or through a different iterator on the same collection) is unsafe.

The ListIterator<E> interface extends Iterator<E>, adding methods you can use to manipulate an ordered List object during iteration. You can iterate forward using hasNext and next, backward using hasPrevious and previous, or back and forth by intermixing the calls as you please. The following code loops backward through a list of strings:

ListIterator<String> it = list.listIterator(list.size());
while (it.hasPrevious()) {
    String obj = it.previous();
    System.out.println(obj);
    // ... use obj ...
}

This gets a ListIterator positioned one beyond the end of the list, and then backs up through the list one element at a time, printing each element. List elements are indexed by position, just like array elements, from 0 to list.size()-1. The methods nextIndex or previousIndex get the index of the element that a subsequent invocation of next or previous will return. The next index when the iterator is at the end of the list is returned as list.size(). The previous index when the iterator is at the first element in the list (index 0) is returned as –1.

The remove method on a ListIterator removes the last value returned by either next or previous. In addition to remove, you can use two additional methods to modify the list's contents:

The contract of remove is extended such that an IllegalStateException is thrown if remove is invoked and either set or add has been invoked since the last call to next or previous.

The contracts for Iterator and ListIterator do not include a snapshot guarantee. In other words, changing the contents of the collection while the iterator is in use can affect the values returned by the methods. For example, if the implementation of next uses the contents of the original collection for its list, it is dangerous to remove elements from the list as you step through it except through the iterator's own methods. A snapshot would return the elements as they were when the Iterator or ListIterator object was created, immune from future changes. You can rely on having a snapshot of the contents only if the method that returns an iterator object explicitly makes a snapshot guarantee. If you need a snapshot but don't have such a guarantee, you can create a snapshot by making a simple copy of the collection, such as with an ArrayList:

public <T> Iterator<T>
    snapshotIterator(Collection<? extends T> coll) {
    return new ArrayList<T>(coll).iterator();
}

Any utility method that returns a collection will invariably be a generic method. We introduce the type variable T to represent the unknown type of the collection being passed in. The snapshotIterator method can accept any collection of T or a subtype of T, but only guarantees that it returns an Iterator<T>.^[2]

Many of the iterators defined in the java.util package are what is known as fail-fast iterators. Such iterators detect when a collection has been modified other than through the iterator itself, and fail quickly and cleanly by throwing an exception—a ConcurrentModificationException—rather than risk performing an action whose behavior may be unsafe.

The interface java.lang.Comparable<T> can be implemented by any class whose objects can be sorted. The interface has a single method:

The ordering defined by compareTo is a class's natural ordering, that is, the ordering that is most natural to objects of the class. It is also a total ordering, meaning that any two objects of the same type must be mutually comparable—that is, you must be able to compare them in either order and always get the same result as to which is the larger. Similarly, the equals method defines a natural equivalence.

Many existing classes are Comparable, including String, java.io.File, java.util.Date, and all the primitive wrapper class types.

If a given class does not implement Comparable or if its natural ordering is wrong for some purpose, you can often provide a java.util.Comparator object instead. The Comparator<T> interface has the method

You can use Comparable and Comparator objects to sort and search List objects with the Collections class's static methods sort and binarySearch. The Collections class (see page 594) also provides static methods min and max to return the smallest and largest element in a Collection.

Comparing strings ignoring case is a common requirement, so the String class defines a Comparator object for this purpose, available from the field String.CASE_INSENSITIVE_ORDER.

As you have seen, most collection types are subtypes of the Collection interface. The only exceptions are those that are subtypes of Map. In this section we cover the Collection interface. The following sections describe the interfaces that extend Collection and the specific collection implementations provided in java.util. We leave Map and its related types for later. We also defer talking about implementing your own collection types.

The basis of much of the collection system is the Collection interface. As you saw in Figure 21-1, most of the actual collection types implement this interface, usually by implementing an extended interface such as Set or List. So Collection is a good place to start understanding collections. It has the following primary methods for working with an individual collection:

All methods that need the notion of equivalence (such as contains and remove) use the equals method on the relevant objects.

The toArray method that has no parameters returns an array of Object. You can use toArray(T[]) to create arrays of other types. For example, if your collection contains String objects, you may want to create a String array. The following code will do that:

String[] strings = new String[collection.size()];
strings = collection.toArray(strings);

Notice that strings is assigned the return value of toArray. This is to be safe in case the size of the collection has increased since the array was allocated, in which case the returned array will not be the one originally allocated. You can also use an empty String array to pass in the desired type and let toArray allocate an array of exactly the right size:

String[] strings = collection.toArray(new String[0]);

Several methods of Collection operate in bulk from another collection. The methods are provided for convenience; also, a collection can often operate more efficiently in bulk.

This Collection interface is purposely very general. Each specific collection type can define restrictions on its parameters or other related behavior. A collection may or may not accept null elements, may be restricted to certain types of elements, may retain elements in a sorted order, and so on. Each collection that makes a restriction should state those restrictions in its documentation so that users can understand the contract for that collection.

The Set<E> interface extends Collection<E>, providing a more specific contract for its methods, but adds no new methods of its own. A collection that is a Set contains no duplicate elements. If you add the same element twice to a set (in other words, if you add two objects that are equal), the first invocation will return true, while the second will return false. If after this, remove is similarly invoked twice, the first remove of the element will return true since the set was changed by removing the element, while the second will return false since the element was no longer present. A set may also contain at most one null element.

The SortedSet<E> interface extends Set<E> to specify an additional contract—iterators on such a set will always return the elements in a specified order. By default this will be the element's natural order. In the implementations of SortedSet provided in java.util you can also specify a Comparator object that will be used to order the elements instead of the natural order.

SortedSet adds some methods that make sense in an ordered set:

The notion of being backed by a collection is important in many methods. The sets returned by the subsetting methods are not snapshots of the matching contents. Rather, they are views onto the underlying collection that filter out certain elements, returning an empty collection if all elements are filtered out. Because the subsets are backed by the original collection, the views remain current no matter which set you use—the subset or the original set. You can create snapshots by making copies of the view, as in

public <T> SortedSet<T> copyHead(SortedSet<T> set, T max) {
    SortedSet<T> head = set.headSet(max);
    return new TreeSet<T>(head); // contents from head
}

This utilizes the copy constructor provided by most of the concrete collection implementations to create a new collection whose initial members are the same as the collection passed to the constructor.

The java.util package gives you two general-purpose Set implementations—HashSet and LinkedHashSet—and one SortedSet implementation, TreeSet.

The List<E> interface extends Collection<E> to define a collection whose elements have a defined order—each element exists in a particular position in the collection, indexed from 0 to list.size()-1. Or, in other words, a List defines a sequence of elements. This requires a refinement of the contracts of several methods inherited from Collection: when you add an element, it is placed at the end of the list; When you remove the n^th element from the list, the element that was after it is shifted over, becoming the new n^th element; and the toArray methods fill in the array in the list's order.

List also adds several methods that make sense in an ordered collection:

All the methods that take an index will throw IndexOutOfBoundsException if index is less than zero or greater than or equal to the list's size.

The java.util package provides two implementations of List—ArrayList and LinkedList.

import java.util.List;
import java.util.ArrayList;

public class Polygon {
    private List<Point> vertices = 
        new ArrayList<Point>();

    public void add(Point p) {
        vertices.add(p);
    }

    public void remove(Point p) {
        vertices.remove(p);
    }

    public int numVertices() {
        return vertices.size();
    }

    // ... other methods ...
}

for (int i = 0; i < list.size(); i++)
    process(list.get(i));

Iterator it = list.iterator();
while (it.hasNext())
    process(it.next());

The Queue<E> interface extends Collection<E> to add some structure to the internal organization of the collection. A queue defines a head position, which is the next element that would be removed. Queues often operate on a first-in-first-out ordering, but it is also possible to have last-in-first-out ordering (commonly known as a stack) or to have a specific ordering defined by a comparator or by comparable elements. Each implementation must specify its ordering properties. The Queue interface adds several methods that work specifically with the head:

There is also a method for inserting into a queue:

Queues in general should not accept null elements because null is used as a sentinel value for poll and peek to indicate an empty queue.

The LinkedList class provides the simplest implementation of Queue. For historical reasons the LinkedList class accepts null elements, but you should avoid inserting null elements when using a LinkedList instance as a queue.

The interface Map<K,V> does not extend Collection because it has a contract that is different in important ways. The primary difference is that you do not add an element to a Map—you add a key/value pair. A Map allows you to look up the value stored under a key. A given key (as defined by the equals method of the key) maps to one value or no values. A value can be mapped to by as many keys as you like. For example, you might use a map to store a mapping of a person's name to their address. If you have an address listed under a name, there will be exactly one in the map. If you have no mapping, there will be no address value for that name. Multiple people might share a single address, so the map might return the same value for two or more names.

The basic methods of the Map interface are

Methods that take keys as parameters may throw ClassCastException if the key is not of the appropriate type for this map, or NullPointerException if the key is null and this map does not accept null keys.

You can see that, though Map does not extend Collection, methods with the same meaning have the same names, and analogous methods have analogous names. This helps you remember the methods and what they do.

Generally, you can expect a Map to be optimized for finding values listed under keys. For example, the method containsKey will usually be much more efficient than containsValue on larger maps. In a HashMap, for example, containsKey is 0(1), whereas containsValue is 0(n) —the key is found by hashing, but the value must be found by searching through each element until a match is found.

Map is not a collection, but there are methods that let you view the map using collections:

The collections returned by these methods are backed by the Map, so removing an element from one of these collections removes the corresponding key/value pair from the map. You cannot add elements to these collections—they do not support the optional methods for adding to a collection. If you iterate through the key and value sets in parallel you cannot rely on getting key/value pairs—they may return values from their respective sets in any order. If you need such pairing, you should use entrySet.

The interface Map.Entry<K,V> defines methods for manipulating the entries in the map, as returned from the Map interface's entrySet method:

Note that there is no setKey method—you change the key by removing the existing mapping for the original key and adding another mapping under the new key.

The SortedMap interface extends Map refining the contract to require that the keys be sorted. This ordering requirement affects the collections returned by keySet, values, and entrySet. SortedMap also adds methods that make sense in an ordered map:

Any returned map is backed by the original map so changes made to either are visible to the other.

A SortedMap is to Map what SortedSet is to Set and provides almost identical functionality except that SortedMap works with keys. The exceptions thrown by the SortedMap methods mirror those thrown by its SortedSet counterparts.

The java.util package gives you four general-purpose Map implementations—HashMap, LinkedHashMap, IdentityHashMap, and WeakHashMap—and one SortedMap implementation, TreeMap.

Two collections, EnumSet and EnumMap, are specifically designed for working efficiently with enum constants.

enum FieldModifiers { STATIC, FINAL, VOLATILE, TRANSIENT }

public class Field {
    public EnumSet<FieldModifiers> getModifiers() {
        // ...
    }
    // ... rest of Field methods ...
}

enum FormElements { NAME, STREET, CITY, ZIP }

The Collections class defines a range of static utility methods that operate on collections. The utility methods can be broadly classified into two groups: those that provide wrapped collections and those that don't. The wrapped collections allow you to present a different view of an underlying collection. There are three different views: a read-only view, a type-safe view, and a synchronized view. The first two are discussed in this section, synchronized wrappers are discussed later with the concurrent collections. First we discuss the general utility methods.

public static <T extends Comparable<? super T>>
    void ensureKnown(List<T> known, T value)
{
    int indexAt = Collections.binarySearch(known, value);
    if (indexAt < 0)        // not in the list -- insert it
        known.add(-(indexAt + 1), value);
}

public Collection<Attr> attrs() {
    return Collections.
        unmodifiableCollection(attrTable.values());
}

All the collection implementations provided in java.util are unsynchronized (except the legacy collections you will soon see). You must ensure any necessary synchronization for concurrent access from multiple threads. You can do this explicitly with synchronized methods or statements, or algorithmically by designing your code to use a given collection from only one thread. These techniques are how collections are often naturally used—as local variables in methods or as private fields of classes with synchronized code.

Thread-safety for collection classes themselves takes two main forms: lock-based synchronization to ensure that concurrent access is precluded, and the use of sophisticated data structures that allow (to varying degrees) truly concurrent use of a collection. The former is provided through the synchronized wrappers, while the latter are provided in the java.util.concurrent subpackage.

The Synchronized Wrappers

A synchronized wrapper passes through all method calls to the wrapped collection after adding any necessary synchronization. You can get a synchronized wrapper for a collection from one of the following static methods of Collections: synchronizedCollection, synchronizedSet, synchronizedSortedSet, synchronizedList, synchronizedMap, or synchronizedSortedMap. These factory methods return wrappers whose methods are fully synchronized and so are safe to use from multiple threads. For example, the following code creates a new HashMap that can be safely modified concurrently:

Map<String, String> unsyncMap =
    new HashMap<String, String>();
Map<String, String> syncMap =
    Collections.synchronizedMap(unsyncMap);

The map referred to by unsyncMap is a full, but unsynchronized, implementation of the Map interface. The Map returned by synchronizedMap has all relevant methods synchronized, passing all calls through to the wrapped map (that is, to unsyncMap). Modifications made through either map are visible to the other—there is really only one map with two different views: the unwrapped, unsynchronized view referenced by unsyncMap, and the wrapping, synchronized view referenced by syncMap:

Because the underlying collection is unsynchronized, you must be very careful what you do with unsyncMap. The safest alternative is to drop the reference and do all work through syncMap. If you do not, you must be sure that you carefully control concurrency. The wrapper synchronizes on itself, so you could use syncMap to synchronize access on the collection and then use unsyncMap safely inside such code:

// add a lot of elements but grab the lock only once
synchronized (syncMap) {
    for (int i = 0; i < keys.length; i++)
        unsyncMap.put(keys[i], values[i]);
}

Iterators returned by synchronized wrappers are not synchronized but must be manually synchronized in a similar manner when needed:

synchronized (syncMap) {
    System.out.println("--- map contents:");
    for (String key : syncMap.keySet())
        System.out.println(key + ": " + syncMap.get(key));
}

If you use an unsynchronized collection concurrently the result is undefined—if you are lucky the error will be detected by the collection and you will get a ConcurrentModificationException. If you are unlucky the collection will quietly become corrupt.

The class Arrays provides useful static methods for dealing with arrays. Most of these methods have a full complement of overloads: one for arrays of each primitive type (except boolean for searching and sorting) and one for Object arrays. There are also two variants of some methods: one acting on the whole array and one acting on the subarray specified by two supplied indices. The methods are

The methods sort and binarySearch have two overloads for Object arrays. One assumes that its elements are comparable (implement the Comparable interface). The second uses a provided Comparator object instead, so you can manipulate arrays of objects that are not comparable or for which you do not want to use the natural ordering.

You can view an array of objects as a List by using the object returned by the asList method.

public static <T> List<T> asList(T... elems)

This can take an actual array reference, or it can conveniently create an array from the given sequence of elements. The list is backed by the underlying array, so changes made to the array are visible to the list and vice versa. The returned list allows you to set elements, but not to add or remove them—it is a modifiable list, but not a resizable list. Using a List for access to an underlying array can give you useful features of List, such as using synchronized wrappers to synchronize access to the underlying array.

Iterators are generally useful, and you may want to write your own, even if you are not implementing a collection type. The following code demonstrates the basics of writing your own Iterator implementation, in this case for an iterator that will filter out strings longer than a given length:

public class ShortStrings implements Iterator<String> {
    private Iterator<String> strings;  // source for strings
    private String nextShort;      // null if next not known
    private final int maxLen;      // only return strings <=

    public ShortStrings(Iterator<String> strings,
                        int maxLen) {
        this.strings = strings;
        this.maxLen = maxLen;
        nextShort = null;
    }

    public boolean hasNext() {
        if (nextShort != null)  // found it already
            return true;
        while (strings.hasNext()) {
            nextShort = strings.next();
            if (nextShort.length() <= maxLen)
                return true;
        }
        nextShort = null;       // didn't find one
        return false;
    }

    public String next() {
        if (nextShort == null && !hasNext())
            throw new NoSuchElementException();
        String n = nextShort;   // remember nextShort
        nextShort = null;       // consume nextShort
        return n;               // return nextShort
    }
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

The class ShortStrings is a type of iterator that will read String objects from another iterator, returning only those that are no longer than a specified length. The constructor takes the iterator that will provide the strings and the maximum length, storing those in the object's fields. The field nextShort will hold the next short string, or null when there isn't one. If nextShort is null, the hasNext method searches for the next short string, remembering it in nextShort. If hasNext reaches the end of its source iteration without finding a short string it returns false.

The method next checks to see if there is a next short string, either returning it if there is one or throwing NoSuchElementException if there are none to return. Notice that hasNext does all the real work of finding the short strings, and next just returns the results, setting nextShort to null to indicate that the next short string, if any, is as yet undiscovered.

Finally, remove is not supported by this iterator implementation, so remove throws UnsupportedOperationException.

A few things to notice. First, hasNext is carefully written so that it will work if invoked multiple times before a next. This is required—the calling code may invoke hasNext as many times as it wants between invocations of next. Second, next is carefully written so that it works even if programmer using it has never invoked hasNext. Although generally a poor practice, you could never invoke hasNext and simply loop invoking next until an exception is generated.

Third, remove is not allowed because it cannot work correctly. Imagine, for example, if remove invoked remove on the underlying iterator. The following legal (although odd) code can cause incorrect behavior:

it.next();
it.hasNext();
it.remove();

Imagine that this were to happen when there was one more short string left in the iteration followed by some long ones. The invocation of next would return the last short string. Then hasNext would iterate through the list of strings, and finding no more short ones, return false. When remove was invoked, it would invoke remove on the underlying iterator, thereby removing the last (long) string that hasNext rejected. That would be incorrect. Since the above code is valid, you cannot fix the problem by forbidding the sequence of methods. You are effectively stuck. Because of this, you cannot build a filtering iterator on top of another Iterator object. You can build one on top of a ListIterator though, since it allows you to back up to the previously returned short string.

The methods of ListIterator have contracts similar to those of Iterator, as you have learned earlier in this chapter. You can provide ListIterator objects in some circumstances where you might otherwise write an Iterator. If you are writing a general utility class for others to use, you should implement ListIterator instead of Iterator if possible.

Exercise 21.4: Write a version of ShortStrings that implements ListIterator to filter a ListIterator object. Should your class extend ShortStrings?

You will usually find that at least one of the collection implementations will satisfy your needs. If not, you can implement relevant collection interfaces yourself to provide collections that satisfy your particular needs. You will find skeletal implementations in the abstract classes AbstractCollection, AbstractSet, AbstractList, AbstractSequentialList, AbstractQueue, and AbstractMap. You can extend these classes to create your own collections, often with less work than starting from the interfaces directly. The concrete collections shown in Figure 21-1 on page 568 each extend the appropriate abstract collection type, as shown in the concrete type tree in Figure 21-1.

These abstract collection classes are designed to be helpful superclasses for your own collection implementations. They are not required—in some cases you will find it easier or more efficient to directly implement the interfaces.

Each abstract collection class declares a few abstract methods and uses them in default implementations of other methods of the collection type. For example, AbstractList has two abstract methods: size and get. All other querying methods of AbstractList, including its iterators, are implemented by using these methods. You need only write your own implementation of the other methods if you want to, typically to either increase efficiency or to allow something disallowed by default. For example, if your list is modifiable, your subclass of AbstractList will have to provide an overriding implementation of the set method, which by default throws UnsupportedOperationException.

The root of the abstract collection types is AbstractCollection. If you need a collection that isn't a set, list, or map you can subclass this directly. Otherwise, you will probably find it more useful to subclass one of the more specific abstract collections classes.

If the Collection class you are creating is unmodifiable (if the modification methods of your collection should throw UnsupportedOperationException), your subclass of AbstractCollection need only provide an implementation of the size and iterator methods. This means you must at least write an implementation of Iterator for your collection. If your collection is modifiable, you must also override the default implementation of the add method (which throws UnsupportedOperationException) and your iterator must support remove.

AbstractSet extends AbstractCollection, and the methods you must implement and can override are the same, with the additional constraint that a subclass of AbstractSet must conform to the contract of the Set interface. It also overrides the implemention of equals and hashCode from Object.

AbstractQueue has the same requirements as AbstractCollection, with the additional requirements that you must implement offer, poll, and peek.

AbstractList requires you to implement only size and get(int) to define an unmodifiable list class. If you also override set(int,Object) you will get a modifiable list, but one whose size cannot change. Your list can change size if you also override the methods add(int,Object) and remove(int).

For example, suppose you need to view a bunch of arrays as a single list. You could use one of the existing List implementations, but at the cost of copying the information each time from the arrays into a new collection. You could instead subclass AbstractList to create an ArrayBunchList type that lets you do this without copying:

public class ArrayBunchList<E> extends AbstractList<E> {
    private final E[][] arrays;
    private final int size;

    public ArrayBunchList(E[][] arrays) {
        this.arrays = arrays.clone();
        int s = 0;
        for (E[] array : arrays)
            s += array.length;
        size = s;
    }

    public int size() {
        return size;
    }

    public E get(int index) {
        int off = 0;    // offset from start of collection
        for (int i = 0; i < arrays.length; i++) {
            if (index < off + arrays[i].length)
                return arrays[i][index - off];
            off += arrays[i].length;
        }
        throw new ArrayIndexOutOfBoundsException(index);
    }

    public E set(int index, E value) {
        int off = 0;    // offset from start of collection
        for (int i = 0; i < arrays.length; i++) {
            if (index < off + arrays[i].length) {
                E ret = arrays[i][index - off];
                arrays[i][index - off] = value;
                return ret;
            }
            off += arrays[i].length;
        }
        throw new ArrayIndexOutOfBoundsException(index);
    }
}

When an ArrayBunchList is created, all the constituent arrays are remembered internally in the arrays field, and the total size of the collection in size. ArrayBunchList implements size, get, and set, but not add or remove. This means that the class provides a modifiable list, but one whose size cannot be changed. Any call that needs values from the underlying arrays will go through get. Any action that modifies the value of the ArrayBunchList will go through set, which modifies the appropriate underlying array.

AbstractList provides Iterator and ListIterator implementations on top of the other methods of the class. Because the iteration implementations use the methods of your underlying subclass of AbstractList, the modifying methods of the iteration will properly reflect the modifiability of your class.

The Iterator implementations of AbstractList use get to read values. As you will note, ArrayBunchList has a get that can do some significant work if the value is stored in one of the later arrays. We can make get smarter than shown here to help with this work, but we can be even more efficient for iteration because it accesses the data sequentially. Here is an optimized Iterator:

private class ABLIterator implements Iterator<E> {
    private int off;        // offset from start of list
    private int array;      // array we are currently in
    private int pos;        // position in current array

    ABLIterator() {
        off = 0;
        array = 0;
        pos = 0;
        // skip any initial empty arrays (or to end)
        for (array = 0; array < arrays.length; array++)
            if (arrays[array].length > 0)
                break;
    }

    public boolean hasNext() {
        return off + pos < size();
    }

    public E next() {
        if (!hasNext())
            throw new NoSuchElementException();
        E ret = arrays[array][pos++];

        // advance to the next element (or to end)
        while (pos >= arrays[array].length) {
            off += arrays[array++].length;
            pos = 0;
            if (array >= arrays.length)
                break;
        }
        return ret;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}

This implementation uses our knowledge of the underlying data structures to know exactly where the next element is coming from. This is more efficient than invoking get to implement the iterator's next. (It is also written to handle empty arrays and an empty ArrayBunchList.)

You can often substantially increase the performance of a resizable list by overriding the protected removeRange method, which takes two int parameters, min and max, and removes the elements starting at min, up to but not including max. The clear method uses remove Range to remove elements from lists and sublists. The default implementation is to invoke remove on each element one at a time. Many data structures can do bulk removes much more efficiently.

AbstractSequentialList extends AbstractList to make it easier to implement lists that are backed by a sequential access data store where moving from one element of the data to another requires examining each element of the data. In such a store, random access requires work since you must traverse each element to get to the next. A linked list is a sequential access data store. By contrast, an array can be randomly accessed directly. This is why ArrayList extends AbstractList, while LinkedList extends AbstractSequentialList.

Where AbstractList implements its iterators via the random access method get, AbstractSequentialList implements the random access methods via an iterator you provide by implementing the listIterator method. You must also implement size. Your class will be modifiable in whatever ways your list iterator's methods allow. For example, if your iterator allows set but not add or remove, you will have a modifiable but non-resizable list.

To use the AbstractMap class you must implement the entrySet method to return an unmodifiable set of entries that contains the mappings of the map. This will implement an unmodifiable map. To make a modifiable map, you must override put, and the iterator your entrySet object returns must allow remove.

The abstract implementations provided in these classes are designed to be easy to extend, but efficiency is not always a consequence. You can often make your subclass of an abstract collection type much faster by judicious overriding of other methods, as shown for the ArrayBunchList iterator. As another example, the implementation of get in AbstractMap, having only a set of entries, must search through that set one at a time until it finds an appropriate entry. This is an O(n)implementation. To get its O(1) performance, HashMap overrides get and all other key-based methods to use its own hash buckets. However, HashMap does not override the implementation of equals because that requires iteration anyway and the implementation in AbstractMap is reasonably efficient.

Exercise 21.5: Implement a more efficient ListIterator for ArrayBunchList. Be careful of the specific contracts of ListIterator methods, such as set not being valid until either next or previous is invoked.

The collection framework—the interfaces and classes described in this chapter, and shown in Figure 21-1 on page 568—has not always been a part of the package java.util, but that package has always contained some other collections. Most are superseded by the new collection types. Even so, they are not deprecated because they are in widespread use in existing code and will continue to be used until programs shift over to the new types. You are therefore likely to encounter these legacy collections so you should learn about them, including their relationship to the newer collection types. The legacy collections consist of the following types:

Of these types, only Properties is in active use—it is used to contain system properties, as described in “System Properties” on page 663 and by some applications to store configuration data. We describe the other legacy collections by contrasting them with their analogous types. We then describe Properties in more detail since you are more likely to actually need to write code that uses it.

A Properties object is used to store string keys and associated string elements. This kind of hashtable often has a default Properties object in which to look for properties that are not specified in the table itself. The Properties class extends Hashtable<Object,Object>. Standard Hashtable methods are used for almost all manipulation of a Properties object, but to get and set properties, you can use string-based methods. In addition to inherited methods, the following methods and constructors are provided:

The default Properties object cannot be changed after the object is created. To change the default Properties object, you can subclass the Properties class and modify the protected field named defaults that contains the default Properties object.