Collection Interfaces

As you saw in Chapter 9, "Interfaces," Java interfaces provide a way to reduce dependencies, or coupling, between classes. When you code to an interface rather than a specific class implementation, you allow for the possibility of multiple classes being available to implement the behavior you need. The collection framework is built on a set of fundamental interfaces. This allows you to choose the proper data structure based on its performance characteristics, without having to worry about the implementation details. The collection framework includes at least one implementation for each of its interfaces, but it also allows you to create your own special purpose collection classes if the need arises.

Note

An interface cannot enforce any requirements on the constructors defined by the classes that implement it, only on the overridden methods . However, classes that implement the collection framework interfaces should, at a minimum, declare a no-argument constructor and a "copy" constructor that accepts another collection as an argument. This copy constructor should build a new collection that contains the same objects as its argument.

Collection

The Collection and Map interfaces sit at the root of the collection framework. Collection focuses on groups of objects, whereas Map, which is discussed later, focuses on groups of associations between objects. The goal of the Collection interface is to identify the common set of methods applicable to any type of object collection. This interface is generic in that it does not dictate whether the contained objects are held in a particular order. It also does not prevent a collection from containing multiple references to the same object. These details are deferred to the sub-interfaces of Collection.

Note

The java.util interfaces and classes that make up the collection framework apply only to objects, not the primitive types. If you need to store a primitive in a collection, you must first wrap it in one of the classes introduced in "Wrapping the Primitive Types in Classes" in Chapter 7, "Classes." For example, to create a collection of int variables , you would wrap each one in an instance of Integer.

It is possible for a class that implements Collection (or Map ) to not support every method defined in the interface. A collection class is allowed to choose to not support a method and instead throw an UnsupportedOperationException if the method is ever called. Although the Collection methods are general, there might be cases where one of the methods does not make sense for a specific implementation. Not supporting an interface method is not the same as not providing an implementation. Remember that a concrete class that implements an interface must implement every method of the interface or the compiler will reject it. However, there are no restrictions on what a method implementation does. To the compiler, an implementation that does nothing but throw an exception is perfectly valid. Of course, certain methods must be supported for a collection to be of any use. The API documentation for the collection framework interfaces clearly identifies each method that is not mandatory as an "optional operation."

As you might expect, the Collection interface defines methods for inserting objects into a collection. There are two such methods in the interface. The first allows you to insert a single element, and the second allows you to add all the elements in another collection:

 boolean add(Object o) boolean addAll(Collection c) 

Each of these methods returns true if the collection changes as a result of the call. Some collections do not allow duplicate objects, so a request to add an object that is already contained is ignored and false is returned. When you call one of these methods and it returns true without throwing an exception, you are guaranteed that the object is included in the collection. Some implementations might place restrictions on the objects allowed in the collection, such as not supporting null entries or only allowing objects of a certain type. In these cases, the method implementations are required to throw an exception when an insert is refused rather than returning false because the collection will not include the object after the call completes.

You also have several options for removing objects from a collection. A call to clear will empty a collection entirely. You can also remove a single object with the remove method, which will only remove one occurrence of an object even if it is held multiple times by the collection. Multiple objects can be removed selectively using removeAll and retainAll, which both accept a collection as a parameter. After calling removeAll, a collection will not contain any of the objects specified by the parameter. The retainAll method will instead remove all objects that are not found in the specified collection. The following signatures define the set of object removal methods:

 void clear() boolean remove(Object o) boolean removeAll(Collection c) boolean retainAll(Collection c) 

The primary reason you build a collection is to access its elements and use them either individually or as a set. To access what you've placed in a collection, you can choose from three methods. Two of these return the elements of a collection as an array of objects. This points out an important issue with collections in Java. The generic nature of the collection framework requires that the elements held by a collection be treated as references to the ultimate superclass Object. When you retrieve the contents of a collection, you will typically have to cast it to its actual type before using it. This is unlike some languages that implement collections using templates that handle any typing issues. The remaining retrieval method returns an Iterator for a collection, which is the most used access mechanism. You'll see how Iterator works later in this chapter. The following signatures define the collection access methods:

 Object[] toArray() Object[] toArray(Object[] a) Iterator iterator() 

Notice that the second version of toArray accepts an array as a parameter. This parameter determines the type of the resulting array. Also, if the input array is long enough to hold the output of the method, it is used for that purpose as well.

The final set of Collection methods allows you to query a collection in several ways. When you need to determine if a collection holds one or more objects, you can find out by calling either contains or containsAll. The isEmpty and size methods allow you to query the collection regarding the number of objects it currently contains. Calling isEmpty is equivalent to calling size and comparing the result to zero, but it makes your code a little more readable. These query methods are declared as follows :

 boolean contains(Object o) boolean containsAll(Collection c) boolean isEmpty() int size() 

The Collection interface is implemented by several classes described throughout this chapter, so you'll find examples of how to use each of these methods later.

List

The Collection interface is extended and specialized with two direct sub-interfaces: List and Set. The List interface represents a collection that stores its objects in order. Like Collection, List places no restriction on allowing duplicate objects in a collection.

Note

The introduction of the java.util.List interface created a name conflict with java.awt.List. If you import both java.awt.* and java.util.* into a single source file, you will have to do some extra work to differentiate the use of the name List when working with collections. You can do this in two ways: by importing java.util.List specifically , or by using the fully qualified name java.util.List wherever the interface is referenced.

The primary extension that List adds to Collection is the concept of an index. The fact that the objects in a List are ordered allows you to access an element by referring to its position in the collection using an integer index. List adds several methods that deal with this concept.

List includes overloaded versions of add and addAll that allow you to specify the index at which objects are inserted into a collection. Like arrays, index values for a List are zero-based . When you call add with an index, the specified object is inserted into the position given by the index, and any element currently at that position is shifted down by one position, along with any subsequent elements. Similarly, the overloaded addAll method inserts the elements of a collection in the order given by their iterator at the specified index. In addition, you can replace an object at a particular index in a List using the set method. This method returns a reference to the object that is replaced . The following signatures define the object insertion methods unique to List:

 void add(int index, Object element) boolean addAll(int index, Collection c) Object set(int index, Object element) 

Caution

The ability to specify indexes when working with a List places an additional burden on you as a programmer. You must always ensure that any index you pass to a List method is greater than or equal to zero, and less than or equal to the size of the collection minus one. Each List method that accepts an index throws an IndexOutOfBoundsException at runtime when this is not the case.

List also provides a new way to remove an object from a collection. An overloaded version of remove that accepts an integer index instead of an object reference allows you to remove an object based solely on its position in the collection. This method shifts any subsequent elements up one position and returns a reference to the removed object:

 Object remove(int index) 

The ordering inherent in a List allows you to access its members in several additional ways. First, you can retrieve a single object by calling get with the desired index. The other two additional methods return a new iterator called a ListIterator , which supports bidirectional movement through a collection. These two methods provide you with either an iterator for an entire collection or one that includes only the elements beginning with a specified index. The following signatures define the element access methods unique to List:

 Object get(int index) ListIterator listIterator() ListIterator listIterator(int index) 

The querying methods added in List provide information on the index where an element is positioned within a collection. These two methods will return either the index where the element is stored, or, if the element is not found, a “1. The first of these methods returns the first index where a specified object is found within the collection; the second returns the last index where the object can be found:

 int indexOf(Object o) int lastIndexOf(Object o) 

There are situations where you might want to work only with a portion of a list. The subList method returns a view of a portion of a list as determined by a beginning and an ending index:

 List subList(int fromIndex, int toIndex) 

The toIndex parameter to this method is treated as exclusive, so the returned list consists of the objects with indexes fromIndex through toIndex “1.

Describing the List returned by subList as a view is an important distinction. This method does not create a new List that holds references to the same objects; it simply provides a convenient way to work with the underlying list. If you modify the List reference returned by subList, any changes you make are reflected in the original list. For example, the following code removes a range of elements from mainList:

 public static void removeRange( List mainList, int startIndex,  int endIndex ) {   List killList = mainList.subList( startIndex, endIndex );   // remove all the elements in the specified range   killList.clear(); } 

Troubleshooting Tip

If you experience runtime exceptions when accessing a List, see " IndexOutOfBoundsException, " in the "Troubleshooting" section at the end of this chapter.

Set and SortedSet

Just like List, Set extends directly from Collection to refine the interface for more specific use. From a mathematical standpoint, a set is a group of unordered values that does not contain any duplicates. The Set interface imposes these same characteristics on a collection of objects. The objects held in a Set are unordered, so there is no concept of an index as in the case of List. In fact, Set adds only restrictions to a collection and not any additional functionality, so it defines no methods beyond those already found in the Collection interface.

Given that Set does not add any methods to its parent interface, what does it do? Previously, in Chapter 9, an interface was described as a contract that defines a set of behavior that one class can expect from another. What the Set interface does is add stipulations to the contract defined by Collection. Any class that implements Set must agree to disallow duplicate objects within its collection. In practice, this means the constructors and the add and addAll methods for a class that implements Set must check for duplicates and reject them.

SortedSet is an extension of the Set interface that adds another stipulation to the Set contract and several more methods. A class that implements SortedSet guarantees that its iterator method returns an Iterator that traverses the elements of the collection in order. It is intended that the order used by a SortedSet be determined in one of two ways. First, the elements in the collection can be sorted in their natural ordering if they implement the java.lang.Comparable interface. Alternatively, a SortedSet implementation should provide a constructor that accepts a Comparator that defines the sort mechanism for the collection. Both the Comparable and Comparator interfaces are discussed later in this chapter in the "Sorting a Collection" section.

Map and SortedMap

The Map interface represents a different concept from the collection types covered so far. It is a root-level interface, like Collection, that holds key-value pairs. You have encountered this type of association before if you have ever dealt with hash tables. Basically, a Map allows you to insert an object into a collection using an associated key, and then use that key as your means of retrieving the object later. For example, you might store Employee objects in a Map using an Integer or String key that holds the value of the corresponding employee's Social Security Number.

Not unlike the other collection framework interfaces, Map places restrictions on the classes that implement it. Chief among these is that a key object in a Map must not be duplicated . This restriction guarantees that each key maps to only a single value object. There is no such restriction on the value objects. In addition, it is strongly advised, although not required, that you use immutable objects for keys. The behavior of a Map when its keys change is not defined by the interface.

To insert an association into a Map, you must provide both the key and the value. For a single association, you accomplish this using the put method. If the key you specify is already mapped, the put method returns the value object from the previous mapping. A Map can also insert multiple associations with a single method call, but, unlike the other collections, this cannot be done using a Collection as a parameter. This isn't possible because a Map must have a key to associate with each object. Therefore, the putAll method is declared to instead accept a reference to another Map. The two methods for inserting associations into a Map are declared as follows:

 Object put(Object key, Object value) void putAll(Map t) 

Troubleshooting Tip

If you experience runtime exceptions when inserting elements into a Map, see " NullPointerException. " in the "Troubleshooting" section at the end of this chapter.

Like inserting a new element into a Map, the removal of a single element is done via the key value, not the element itself. The remove method extracts a single object from a Map and returns the associated value object as the method's return value. A return value of null indicates that either the specified key was not found in the Map, or the key was mapped to a value of null. Just as with Collection, Map also declares a clear method that removes all its elements with a single call. The following signatures declare Map 's element removal methods:

 Object remove(Object key) void clear() 

You retrieve an object from a Map using its key. The get method accepts a key object as a parameter and returns the corresponding value object, or null if the key is not mapped:

 Object get(Object key) 

Map also provides access to three views of its contents. Again, the term "view" here implies that any changes made to the objects or mappings retrieved in this manner affect the underlying Map. The keySet method returns the key objects as a Set. A Set is used here because, by definition, the collection of keys in a Map cannot contain duplicates. The interface's values method returns the value objects held by a Map as a Collection. A generic Collection is used here because the value objects can be duplicated. The third view provided by a Map is returned by the entrySet method. The Set returned by this method represents each element in the Map using a Map.Entry. Map.Entry is a nested interface of Map that allows you to query the key and value for each association and replace the value object if desired. The following signatures declare the three view methods:

 Set keySet() Collection values() Set entrySet() 

Note

Chapter 9 focused on the methods and fields declared within interfaces, but Map.Entry illustrates that an interface can also declare another interface as a member. A nested interface is useful when a set of methods has meaning only within a particular context. The methods declared by Map.Entry relate to a single association, but this association is only meaningful as part of a Map.

The remaining Map methods allow you to query information from the collection. These methods include the same isEmpty and size methods found in Collection. In addition, containsKey and containsValue allow you to determine if a Map holds a particular key or value object. The following signatures define the query methods:

 boolean isEmpty() int size() boolean containsKey(Object key) boolean containsValue(Object value) 

The SortedMap interface extends Map to identify implementations that return the results of entrySet, keySet, and values sorted based on the keys. As with SortedSet, the sort order of a SortedMap is determined either by a Comparator provided when the map is constructed , or by the natural ordering of key objects that implement java.lang.Comparable.

You can access the lowest and highest keys of a SortedMap using the firstKey and lastKey methods:

 public Object firstKey() public Object lastKey() 

SortedMap also provides the headMap, tailMap, and subMap methods that return views of portions of the underlying map. The headMap method returns a view of that part of the map that is less than the specified key. Conversely, tailMap returns a view of the elements with keys greater than its argument. You can retrieve any arbitrary portion of the map using subMap. The following signatures declare the three view methods:

 public SortedMap headMap(Object toKey) public SortedMap tailMap(Object fromKey) public SortedMap subMap(Object fromKey, Object toKey)