The natural ordering of objects is specified by implementing the generic Comparable interface. A total ordering of objects can be specified by implementing a comparator that implements the generic Comparator interface.

We will look at the two generic interfaces Comparable and Comparator in turn.

The general contract for the Comparable interface is defined by its only method:

Many of the standard classes in the Java API, such as the primitive wrapper classes, String, Date, and File, implement the Comparable interface. Objects implementing this interface can be used as

The natural ordering for String objects (and Character objects) is lexicographical ordering, i.e., their comparison is based on the Unicode value of each character in the strings (see Section 10.4, p. 445). Objects of the String and Character classes will be lexicographically maintained as elements in a sorted set, or as keys in a sorted map that uses their natural ordering.

The natural ordering for objects of a numerical wrapper class is in ascending order of the values of the corresponding numerical primitive type (see Section 10.3, p. 428). As elements in a sorted set or as keys in a sorted map that uses their natural ordering, the objects will be maintained in ascending order.

According to the natural ordering for objects of the Boolean class, a Boolean object representing the value false is less than a Boolean object representing the value true.

An implementation of the compareTo() method for the objects of a class should meet the following criteria:

The magnitude of non-zero values returned by the method is immaterial; the sign indicates the result of the comparison. The general contract of the compareTo() method augments the general contract of the equals() method, providing a natural ordering of the compared objects. The equality test of the compareTo() method has the same provisions as that of the equals() method.

Implementing the compareTo() method is not much different from implementing the equals() method. In fact, given that the functionality of the equals() method is a subset of the functionality of the compareTo() method, the equals() implementation can call the compareTo() method. This guarantees that the two methods are always consistent with one another.

A compareTo() method is seldom implemented to interoperate with objects of other classes. For example, this is the case for primitive wrapper classes and the String class. The calls to the compareTo() method in the three assert statements below all result in a compile time error.

An implementation of the compareTo() method for version numbers is shown in Example 15.8. Note the specification of the implements clause in the class header. By parameterizing the Comparable interface with the VersionNumber type, the class declaration explicitly excludes comparison with objects of other types. Only VersionNumbers can be compared.

The signature of the compareTo() method is compareTo(VersionNumber). In order to maintain backward compatibility with non-generic code, the compiler inserts the following bridge method with the signature compareTo(Object) into the class.

In an implementation of the compareTo() method, the fields are compared with the most significant field first and the least significant field last. In the case of the version numbers, the release numbers are compared first, followed by the revision numbers, with the patch numbers being compared last. Note that the next least significant fields are only compared if the comparison of the previous higher significant fields yielded equality. Inequality between corresponding significant fields short-circuits the computation. If all significant fields are equal, a zero will be returned. This approach is shown in the implementation of the compareTo() method at (7) through (10) in Example 15.8.

Comparison of integer values in fields can be optimized. In the code for comparing the release numbers at (8) in Example 15.8, we have used the compareTo() method implemented by the Integer class and relied on autoboxing of the vno.release value:

The code above can be replaced by the following code for doing the comparison, which relies on the difference between int values:

However, this code can break if the difference is a value not in the range of the int type.

Significant fields with non-boolean primitive values are normally compared using the relational operators < and >. For comparing significant fields denoting constituent objects, the main options are to either invoke the compareTo() method on them or use a comparator.

Example 15.9 is a client that uses the class VersionNumber from Example 15.8. This client also runs the same tests as the clients in Example 15.7, Example 15.5, and Example 15.3. What is different about this implementation is that the class VersionNumber overrides both the equals() and hashCode() methods, and implements the compareTo() method. In addition, the compareTo() method is consistent with equals. Following general class design principles, the class has been declared final so that it cannot be extended. We have already seen the program output in Example 15.1 confirming that all the tests on objects of the VersionNumber class run as expected.

Unlike previous attempts, the following code from Example 15.9 demonstrates that VersionNumber objects can now be maintained in sorted sets and maps:

The output from executing this code shows that the elements in the set and the map are sorted in the natural ordering for version numbers:

By default, the class TreeSet relies on its elements to implement the compareTo() method. The output from the program in Example 15.9 shows that the TreeSet, created at (22), maintains its elements sorted in the natural ordering dictated by the compareTo() method. Analogously, the output from the program in Example 15.9 shows that the TreeMap, created at (23), maintains its entries sorted on the keys, which are in the natural ordering dictated by the compareTo() method.

We can run generic algorithms on collections of version numbers. Utility methods provided by the Collections and Arrays classes in the java.util package are discussed in Section 15.11, “15.11 Working with Collections.” The following code sorts the elements in the list that was created at (14) in Example 15.1, and referenced by the reference vnoList:

Since the comparator value is null, natural ordering is used. The output from executing this code shows that the elements in the list are indeed sorted in ascending order:

A binary search can be run on this sorted list to find the index of the version number (9.1.1), referenced by the reference searchKey in Example 15.9:

Since the comparator value is null, natural ordering is assumed for the elements in the list. Executing the code prints the correct index of the search key in the sorted list:

Specifying the comparator with the null value in the test() method in Example 15.9 was necessary to avoid compile time errors. We can readily use VersionNumber objects with the overloaded sort() and binarySearch() methods in the Collections class whose signature explicitly requires that the elements implement the Comparable interface:

Precise control of ordering can be achieved by creating a customized comparator that imposes a specific total ordering on the elements. All comparators implement the Comparator interface, which has the following single method:

An alternative ordering to the default natural ordering can be specified by passing a Comparator to the constructor when the sorted set or map is created. The Collections and Arrays classes provide utility methods for sorting, which also take a Comparator (see subsection Ordering Elements in Lists, p. 838, and subsection Sorting Arrays, p. 842).

Example 15.10 demonstrates the use of different comparators for strings. The program creates an empty sorted set using the TreeSet class. Each program argument is added to the sorted set in the loop at (2). A textual representation of the sorted set is then printed at (3). The output shows the sort ordering in which the elements are maintained in the set. The set is traversed according to the sort ordering.

The String class implements the Comparable interface, providing an implementation of the compareTo() method. The compareTo() method defines the natural ordering for strings, which is lexicographical. The natural ordering is used to maintain the program arguments sorted lexicographically when the sorted set at (1a) is used. If we wish to maintain the strings in a different ordering, we need to provide a customized comparator.

The String class provides a static field (CASE_INSENSITIVE_ORDER) that denotes a comparator object with a compare() method that ignores the case when comparing strings lexicographically. This particular total ordering is used to maintain the program arguments sorted when the sorted set at (1b) is used. The comparator is passed as argument to the set constructor. The output shows how the elements are maintained sorted in the set by this total ordering, which is a case-insensitive ordering.

We can create a string comparator that enforces rhyming ordering on the strings. In rhyming ordering, two strings are compared by examining their corresponding characters at each position in the two strings, starting with the characters in the last position. First the characters in the last position are compared, then those in the last but one position, and so on. For example, given the two strings "report" and "court", the last two characters in both the strings are the same. Continuing backward in the two strings, the character 'o' in the first string is less than the character 'u' in the second string. According to the rhyming ordering, the string "report" is less than the string "court".

Comparing two strings according to the rhyming ordering is equivalent to reversing the strings and comparing the reversed strings lexicographically. If we reverse the two strings, "report" and "court", the reversed string "troper" is lexicographically less than the reversed string "truoc".

A rhyming ordering comparator is implemented by the RhymingStringComparator class in Example 15.10. The compare() method at (4) first creates reversed versions of the strings passed as arguments. A reversed version of a string is created using a string builder, which is first reversed and then converted back to a string, as shown at (5). The compare() method then calls the compareTo() method at (6) to compare the reversed strings, as the lexicographical ordering for the reversed strings is equivalent to the rhyming ordering for the original strings. This particular total ordering is used to maintain the program arguments sorted when the sorted set at (1c) is used. The comparator is again passed as argument to the set constructor. The output shows how the elements are maintained sorted in the set by this total ordering, which is rhyming ordering.

Example 15.11 illustrates using a comparator that orders version numbers (Example 15.8) according to their reverse natural ordering. Such a comparator is implemented as an anonymous class by the method reverseComparatorVNO() at (1). The comparator leverages on the compareTo() method implemented by the VersionNumber class.

A list of version numbers is created at (3), that is backed by the array created at (2). This list is sorted using the comparator at (4). A binary search is done in this list at (5). We have used the same comparator for the search as we did for the sorting in order to obtain predictable results.

Review Questions

15.1 Which statements about the hashCode() and equals() methods are true?

Select the two correct answers.

(a) Two objects that are different according to the equals() method, must have different hash values.

(b) Two objects that are equal according to the equals() method, must have the same hash value.

(c) Two objects that have the same hash value, must be equal according to the equals() method.

(d) Two objects that have different hash values, must be unequal according to the equals() method.

15.2 Given that the objects referenced by the parameters override the equals() and the hashCode() methods appropriately, which return values are possible from the following method?

Select the four correct answers.

(a) "false false false"

(b) "false false true"

(c) "false true false"

(d) "false true true"

(e) "true false false"

(f) "true false true"

(g) "true true false"

(h) "true true true"

15.3 Which code, when inserted at (1), in the equalsImpl() method will provide a correct implementation of the equals() method?

Select the three correct answers.

(a) return a == o.a || b == o.b;

(b) return false;

(c) return a >= o.a;

(d) return a == o.a;

(e) return a == o.a && b == o.b;

15.4 Which code, when inserted at (1), will provide a correct implementation of the hashCode() method in the following program?

Select the two correct answers.

(a) return 31337;

(b) return accumulated / count;

(c) return (count << 16) ^ accumulated;

(d) return ~accumulated;

(e) return count == 0 ? 0 : average();

15.5 What will be the result of compiling and running the following program?

Select the one correct answer.

(a) The program will fail to compile.

(b) The program will compile but throw an exception when run.

(c) The program will compile and print true false, when run.

(d) The program will compile and print true true, when run.

(e) The program will compile and print false false, when run.

(f) The program will compile and print false true, when run.

A collection allows a group of objects to be treated as a single unit. Objects can be stored, retrieved, and manipulated as elements of a collection. Arrays are an example of one kind of collection.

Program design often requires the handling of collections of objects. The Java Collections Framework provides a set of standard utility classes for managing various kinds of collections. The core framework is provided in the java.util package and comprises three main parts:

• A set of implementations (i.e., concrete classes, listed in Table 15.1) that are specific implementations of the core interfaces, providing data structures that a program can readily use.

• An assortment of static utility methods found in the Collections and Arrays classes that can be used to perform various operations on collections and arrays, such as sorting and searching, or creating customized collections (see Section 15.11, “15.11 Working with Collections”).

The generic Collection interface is a generalized interface for maintaining collections and is the root of the interface inheritance hierarchy for collections shown in Figure 15.1a. These subinterfaces are summarized in Table 15.1. The Collection interface extends the Iterable interface that specifies an iterator to sequentially access the elements of an Iterable object (see subsection Iterators, p. 785).

The elements in a Set must be unique, that is, no two elements in the set can be equal. The order of elements in a List is positional, and individual elements can be accessed according to their position in the list.

Queues and deques, represented respectively by the Queue and the Deque interfaces, define collections whose elements can be processed according to various strategies.

As can be seen from Figure 15.1b, the Map interface does not extend the Collection interface because conceptually, a map is not a collection. A map does not contain elements. It contains mappings (also called entries) from a set of key objects to a set of value objects. A key can, at most, be associated with one value, i.e., it must be unique. As the name implies, the SortedMap interface extends the Map interface to maintain its mappings sorted in key order. It is superseded by the NavigableMap interface which should be the preferred choice in new code.

The java.util package provides implementations of a selection of well-known abstract data types, based on the core interfaces. Figures 15.2 and 15.3 show the inheritance relationship between the core interfaces and the corresponding implementations. None of the concrete implementations inherit directly from the Collection interface. The abstract classes that provide the basis on which concrete classes are implemented, are not shown in Figures 15.2 and 15.3.

By convention, each of the collection implementation classes provides a constructor for creating a collection based on the elements of another Collection object passed as argument. This allows the implementation of a collection to be changed by merely passing the collection to the constructor of the desired implementation. This interchangeability is also true between Map implementations. But collections and maps are not interchangeable. Note that a collection (or a map) only stores reference values of objects, and not the actual objects.

The collections framework is interface-based, meaning that collections are manipulated according to their interface types, rather than by the implementation types. By using these interfaces wherever collections of objects are used, various implementations can be used interchangeably.

All the concrete classes shown in Figures 15.2 and 15.3 implement the Serializable and the Cloneable interfaces; therefore, the objects of these classes can be serialized and also cloned.

A summary of collection and map implementations is given in Table 15.2. The contents of this table will be the focus as each core interface and its corresponding implementations are discussed in the subsequent sections.

The Collection interface specifies the contract that all collections should implement. Some of the operations in the interface are optional, meaning that a collection may choose to provide a stub implementation of such an operation that throws an UnsupportedOperationException when invoked. The implementations of collections from the java.util package support all the optional operations in the Collection interface (see Figure 15.2 and Table 15.2).

Many of the methods return a boolean value to indicate whether the collection was modified as a result of the operation.

The basic operations are used to query a collection about its contents and allow elements to be added to and removed from a collection. Many examples in this chapter make use of these operations.

These operations perform on a collection as a single unit. See Section 15.4 for an example.

These bulk operations can be used to perform the equivalent of set logic on arbitrary collections (i.e., also lists and not just sets). The containsAll() method returns true if all elements of the specified collection are also contained in the current collection.

The addAll(), removeAll(), and retainAll() methods are destructive in the sense that the collection on which they are invoked can be modified. The operations performed by these methods are visualized by Venn diagrams in Figure 15.4.

The addAll() requires that the element type of the other collection is the same as, or a subtype of, the element type of the current collection. The removeAll() and retainAll() operations can be performed with collections of any type.

A collection provides an iterator which allows sequential access to the elements of a collection. An iterator can be obtained by calling the following method of the Collection interface:

The generic interface Iterator is defined as follows:

After obtaining the iterator for a collection, the methods provided by the Iterator interface can be used to systematically traverse the elements of the underlying collection one by one. Example 15.12 illustrates the use of an iterator.

Example 15.12 creates a list of integers and then removes from the list all integers that are not between 1 and 10, inclusive. The example uses an ArrayList for the list of integers. First an empty ArrayList is created and elements of an int array are added to the list using a for(:) loop.

In Example 15.12, an iterator is obtained at (3) and used in the loop at (4) to traverse all the elements in the integer list. At (5) the current element is retrieved by the iterator from the list. No casts are necessary, as the compiler guarantees that the iterator will return an Integer object from the underlying list. Its value is automatically unboxed and assigned to an int variable. The call to the remove() method removes the current element from the underlying list if the criteria in the if statement at (6) is satisfied.

Note that the methods are invoked on the iterator, not the underlying collection. The three methods of the iterator should be used in step inside a loop, as shown in Example 15.12.

In Example 15.12, we used an iterator in a while loop at (4) for traversing the collection. It is quite common to use an iterator in a for(;;) loop for this purpose, where the iterator is obtained in the initialization part, and the increment part is left empty:

The majority of the iterators provided in the java.util package are said to be failfast. When an iterator has already been obtained, structurally modifying the underlying collection by other means will invalidate the iterator. Subsequent use of this iterator will throw a ConcurrentModificationException, as the iterator checks to see if the collection has been structurally modified every time it accesses the collection. The remove() method of an iterator is the only recommended way to delete elements from the underlying collection during traversal with an iterator.

The order in which the iterator will return the elements from an underlying collection depends on the traversal order supported by the collection. For example, an iterator for a list will traverse the elements in the sequential order they have in the list, whereas the traversal order for the elements in an ordinary set is not predetermined. An iterator for a sorted collection will make the elements available in a given sorted order. Traversal order will be discussed together with the individual concrete classes.

The concrete collection classes override the toString() method to provide a textual representation of their contents. The standard textual representation generated by the toString() method for a collection is

where each element_i is the textual representation generated by the toString() method of the individual elements in the collection. In Example 15.12 the toString() method of the collection class is used implicitly at (2) and at (7) to generate a textual representation for the collection.

In Section 6.3, p. 220, we showed how to traverse an array using a for(:) loop. A for(:) loop can also be used to traverse any data structure that implements the java.lang.Iterable interface:

The iterator() method returns an iterator that implements the Iterator interface we have seen earlier in this subsection. The Iterable interface implies that if a collection implements an iterator, we can traverse the collection with a for(:) loop.

In the loop construct

the value of expression can be a reference value that refers to a collection that implements the Iterable interface. From Figure 15.2 we see that the Collection interface extends the Iterable interface, therefore all collections that implement the Collection interface can be traversed using the for(:) loop. A collection that implements the Collection interface and thereby the Iterable interface, has the element type E. This element type E must be assignable to the type of the variable in the for(:) loop. The variable is assigned the reference value of a new element in the collection each time the body of the loop is executed.

The semantics of the for(:) loop discussed in Section 6.3, p. 220, also apply when traversing a collection. In particular, any structural change to the collection (adding or removing elements) in the for(:) loop will result in a ConcurrentModificationException.

Example 15.13 illustrates using a for(:) loop to traverse a collection. An empty collection of string builders is created at (1) and populated at (2) using a for(:) loop that traverses over an array of string builders. The collection is traversed in the for(:) loop at (3), reversing and printing the contents of each string builder in the collection. The output verifies that the state of each element in the collection was changed.

Behind the scenes, however, an appropriate iterator is used to traverse the collection, but the for(:) loop simplifies traversing a collection in the source code.

Note that if the collection is ordered or sorted, the iterator will traverse the collection in the ordering used to maintain the elements in the collection. For example, in the case of an ArrayList, the iterator will yield the elements in the same order as the insertion order. In the case of a TreeSet, the iterator will yield the elements in the sort ordering used to maintain the elements in the set. If the collection is unordered, the order in which the iterator will yield the elements is not predictable. Thus, we cannot be sure in which order a Hashset will be traversed.

These operations convert collections to arrays.

Example 15.13 illustrates converting collections to arrays. At (1) the call to the toArray() method returns an array of type Object. Since an array of type Object is not a subtype of an array of type String, the compiler reports an error at (2).

At (3), the call to the toArray() method returns an array of size 3, array type Object[], and element type String, when the method was passed a zero-length array of type Object. In other words, the method created a suitable-size array of type Object since the array passed in the argument was too small. This array was filled with the elements of the set, which are strings. Although the array returned is of type Object, the objects stored in it are of type String. The output from the program confirms these observations.

At (4), the call to the toArray() method returns an array of size 3, array type String[], and element type String, when the method was passed a zero-length array of type String. Now the method creates a new suitable-size array of type String and fills it with the elements of the set, which are strings. The output from the program shows that the array passed in the argument is not the same as the array returned by the method call.

At (5), the call to the toArray() method returns the same array it was passed in the argument, since it is of appropriate size and type. In other words, the array passed in the argument is filled with the elements of the list and returned. This is corroborated by the output from the program.

Lastly, the program throws an ArrayStoreException at (6), because String objects cannot be stored in an array of type Integer.

Review Questions

15.6 Which of these are core interfaces in the collections framework?

Select the three correct answers.

(a) Set<E>

(b) Bag<E>

(c) LinkedList<E>

(d) Collection<E>

(e) Map<K,V>

15.7 Which of these implementations are provided by the java.util package?

Select the two correct answers.

(a) HashList<E>

(b) HashMap<K,V>

(c) ArraySet<E>

(d) ArrayMap<K,V>

(e) TreeMap<K,V>

15.8 What is the name of the interface used to represent collections that maintain nonunique elements in order?

Select the one correct answer.

(a) Collection<E>

(b) Set<E>

(c) SortedSet<E>

(d) List<E>

(e) Sequence<E>

15.9 Which methods are specified by the Iterator<E> interface?

Select the three correct answers.

(a) hasNext()

(b) hasMore()

(c) remove()

(d) delete()

(e) more()

(f) next()

15.10 Which identifiers, when inserted in appropriate places in the program, will result in the output 911?

Select the five correct answers.

(a) hasNext

(b) myItems

(c) next

(d) Integer

(e) int

(f) Collection

(g) iterator

15.11 What will the program print when it is compiled and run?

Select the one correct answer.

(a) A collection coming up.

  60

(b) A collection coming up.
  A collection coming up.
  A collection coming up.

  60

(c) The program does not compile.

(d) None of the above.

15.12 Which statements are true about the for(:) loop:

Select the three correct answers.

(a) The variable is only visible in the for(:) loop body.

(b) The expression is only evaluated once.

(c) The type of the expression must be java.lang.Iterable or an array type.

(d) Changing the value of the variable in the loop body affects the data structure represented by the expression.

(e) The loop runs backwards if the expression is negated as follows: ! expression.

(f) We can iterate over several data structures simultaneously in a for(:) loop.

15.13 What will the program print when compiled and run?

Select the one correct answer.

(a) Before: [Don't, change, me!]
   DON'T_CHANGE_ME!_
   After: [DON'T, CHANGE, ME!]

(b) Before: [Don't, change, me!]
   DON'T_CHANGE_ME!_
   After: [Don't, change, me!]

(c) The program will throw a java.util.ConcurrentModificationException, when run.

(d) The program fails to compile.

15.14 Which code, when inserted at (1), will result in the following output:

from the program when compiled and run?

Select the two correct answers.

(a) for (Fruity f : list) {
  if (f.equals(apple))
    list.remove(f);
}

(b) int i = 0;
for (Fruity f : list) {
  if (f.equals(apple))
    list.remove(i);
  i++;
}

(c) for (int j = 0; j < list.size(); j++) {
  Fruity f = list.get(j);
  if (f.equals(apple))
    list.remove(j);
}

(d) Iterator<Fruity> itr = list.iterator();
while (itr.hasNext()) {
  Fruity f = itr.next();
  if (f.equals(apple))
    itr.remove();
}

15.15 Which statement, when inserted independently at (1), will cause either a compiletime or a runtime error?

Select the four correct answers.

(a) Object[] objArray1 = intList.toArray();

(b) Integer[] intArray1 = intList.toArray();

(c) Number[] numArray1 = intList.toArray();

(d) Object[] objArray2 = intList.toArray(new Object[0]);

(e) Integer[] intArray2 = intList.toArray(new Integer[0]);

(f) Integer[] intArray3 = intList.toArray(new Number[0]);

(g) Number[] numArray2 = intList.toArray(new Number[0]);

(h) Number[] numArray3 = intList.toArray(new Integer[0]);

(i) Number[] numArray4 = intList.toArray(new Long[0]);

Unlike other implementations of the Collection interface, implementations of the Set interface do not allow duplicate elements. This also means that a set can contain at most one null value. The Set interface does not define any new methods, and its add() and addAll() methods will not store duplicates. If an element is not currently in the set, two consecutive calls to the add() method to insert the element will first return true, then false. A Set models a mathematical set (see Table 15.3), that is, it is an unordered collection of distinct objects.

Multisets (also called bags) that allow duplicate elements cannot be implemented using the Set interface, since this interface requires that elements are unique in the collection.

Before reading this subsection, it is a good idea to review the subsection The Comparable<E> Interface, p. 765, on specifying the natural ordering for objects, and the subsection The Comparator<E> Interface, p. 771, on specifying a particular total ordering for objects.

The NavigableSet interface extends the SortedSet interface with navigation methods to find the closest matches for specific search targets. By navigation, we mean operations that require searching for elements in the navigable set. In the absence of elements, these operations return null rather than throw a NoSuchElementException.

The NavigableSet interface replaces the SortedSet interface and is the preferred choice when a sorted set is required. In addition to the methods of the SortedSet interface, the NavigableSet interface adds the following new methods:

The TreeSet class implements the NavigableSet interface and thereby the SortedSet interface. By default, operations on a sorted set rely on the natural ordering of the elements. However, a total ordering can be specified by passing a customized comparator to the constructor.

The TreeSet implementation uses balanced trees, which deliver excellent (logarithmic) performance for all operations. However, searching in a HashSet can be faster than in a TreeSet because hashing algorithms usually offer better performance than the search algorithms for balanced trees. The TreeSet class is preferred if elements are to be maintained in sorted order and fast insertion and retrieval of individual elements is desired.

The TreeSet class provides four constructors:

Example 15.17 illustrates some selected navigation operations on a TreeSet. The set is created at (1) and populated by calling the Collections.addAll() method at (2). The elements are maintained according to the natural ordering for Strings, i.e., the one defined by the compareTo() method of the Comparable interface implemented by the String class. The subset-view operations at (3) show how the bounds can be inclusive or exclusive. Note also how the closest-match methods at (4) behave. A sorted set with the reverse order corresponding to the natural ordering is created at (5). The methods pollFirst() and pollLast() remove the element that is retrieved, i.e., they change the set structurally.

The following code shows how we can create a sorted set with a specific total ordering by supplying a comparator in the constructor call:

Lists are collections that maintain their elements in order and can contain duplicates. The elements in a list are ordered. Each element, therefore, has a position in the list. A zero-based index can be used to access the element at the position designated by the index value. The position of an element can change as elements are inserted or deleted from the list, i.e., as the list is changed structurally.

In addition to the operations inherited from the Collection interface, the List interface also defines operations that work specifically on lists: position-based access of the list elements, searching in a list, operations on parts of a list (called open range-view operations), and creation of customized iterators. This additional functionality is provided by the following methods in the List interface:

The first method inserts the specified element at the specified index. If necessary, it shifts the element previously at this index and any subsequent elements one position toward the end of the list. The inherited method add(E) from the Collection interface will append the specified element to the end of the list.

The second method inserts the elements from the specified collection at the specified index, using an iterator of the specified collection, i.e. the method splices the elements of the specified collection into the list at the specified index. The method returns true if any elements were added.

E remove(int index)

Optional

Three implementations of the List interface are provided in the java.util package: ArrayList, LinkedList, and Vector.

The ArrayList class implements the List interface. The Vector class is a legacy class that has been retrofitted to implement the List interface, and will not be discussed in detail. The Vector and ArrayList classes are implemented using dynamically resizable arrays, providing fast random access (i.e., position-based access) and fast list traversal—very much like using an ordinary array. Unlike the ArrayList class, the Vector class is thread-safe, meaning that concurrent calls to the vector will not compromise its integrity. The LinkedList implementation uses a doubly-linked list. Insertions and deletions in a doubly-linked list are very efficient.

The ArrayList and Vector classes offer comparable performance, but Vectors suffer a slight performance penalty due to synchronization. Position-based access has constant-time performance for the ArrayList and Vector classes. However, positionbased access is in linear time for a LinkedList owing to traversal in a doubly-linked list. When frequent insertions and deletions occur inside a list, a LinkedList can be worth considering. In most cases, the ArrayList implementation is the overall best choice for implementing lists.

In addition to the List interface, the LinkedList class also implements two other interfaces that allow it to be used for stacks and different kinds of queues (see Section 15.7, p. 809).

The ArrayList class provides the following constructors:

Example 15.18 illustrates some basic operations on lists. The user gets one shot at guessing a five-digit code. The solution is hard-wired in the example as a list of five Integer objects. The secretSolution list is created at (1) and populated using the add() method. The guess specified at the command line is placed in a separate list, called guess, at (2).

The number of digits that are correctly guessed is determined at (3). The solution is first duplicated and each digit in the guess is removed from the duplicated solution. The number of deletions corresponds to the number of correct digits in the guess list. A digit at a particular index in the guess list is returned by the get() method. The remove() method returns true if the duplicate list was modified, that is, the digit from the guess was found and removed from the duplicated solution. Of course, one could use the retainAll() method, as shown below, but the idea in Example 15.18 is to use positional access on the guess list.

Finding the number of digits that are correctly placed is achieved by using two list iterators at (4), which allow digits in the same position in the guess and the secretSolution lists to be compared.

In this section we look at the different types of queues provided by the Java collections framework.

Both the PriorityQueue and LinkedList classes implement the Queue interface. Unless bi-directional traversal is necessary, other queue implementations should be considered, and not the LinkedList class. (The LinkedList class is also eclipsed by the introduction of the ArrayDeque class when it comes to implementing deques, as we will see shortly.)

As the name suggests, the PriorityQueue class is the obvious implementation for a queue with priority ordering. The implementation is based on a priority heap, a tree-like structure that yields an element at the head of the queue according to the priority ordering, which is defined either by the natural ordering of its elements or by a comparator. In the case of several elements having the same priority, one of them is chosen arbitrarily.

Elements of a PriorityQueue are not sorted. The queue only guarantees that elements can be removed in priority order, and any traversal using an iterator does not guarantee to abide by the priority order.

The PriorityQueue class provides the following constructors:

Example 15.19 illustrates using priority queues. The example shows how two priority queues maintain objects of the class Task. The equality of objects in this class is based on the task number (Integer), as is the natural ordering of the objects. The natural ordering implemented by the class Task will result in the priority queue yielding its elements in ascending order of the task numbers, i.e., tasks with smaller task numbers will have higher priority. The class Task also defines two comparators at (1) and (2). The first one defines a total ordering of tasks based on descending order of the task name (String), and the second one takes both task number and task name into consideration.

The main() method in the class TaskExecutor creates an array with some tasks at (3). Tasks from this array will be loaded into a priority queue. The method testPQ() at (5) uses the priority queue it receives as argument. It loads the queue at (6) from the array, which is also passed as argument. It calls the offer() method to insert a task in the priority queue.

The testPQ() method calls the peek() method at (7) to examine the task at the head of the queue. The tasks are executed by removing them one by one at (8) by calling the poll() method.

The priority queue pq1 at (3) has its priority ordering defined by the natural ordering of the tasks. Note that the textual representation of the queue in the output

does not show the tasks in priority order. It just shows what task there are in the queue. The textual representation of the queue is generated by the print method running an iterator over the queue. The iterator is under no obligation to take the priority order into consideration. The output also shows that the task with the highest priority (i.e., the smallest task number) is at the head of the queue:

The call to the poll() method in the while loop at (8) removes tasks in priority order, as verified by the output:

Since two of the tasks have the same priority, the queue chooses which one should be chosen first. The queue is empty when the peek() method returns null.

We leave it to the reader to verify that the output also conforms to the priority ordering of the pq2 priority queue at (4) that uses the supplied comparator to implement its priority ordering.

The Queue interface defines the contract for queues where the head element is always removed according to a processing order. The processing order is always defined by the natural ordering or a total ordering of the elements maintained by the queue. The Deque interface extends the Queue interface to allow double-ended queues. Such a queue is called a deque. It allows operations not just at its head, but also at its tail. It is a linear unbounded structure in which elements can be inserted at or removed from either end. Various synonyms are used in the literature for the head and tail of a deque: front and back, first and last, start and end.

A deque can be used as FIFO queue, where elements added at the tail are presented at the head for inspection or removal in the same order, thus implementing FIFO order. A deque can also be used as a stack, where elements are added to and removed from the same end, thus implementing LIFO ordering.

The Deque interface defines symmetrical operations at its head and tail. Which end is in question is made evident by the method name. Below, equivalent methods from the Queue are also identified. The push() and pop() methods are convenient for implementing stacks.

These methods remove an element from the deque. The pollFirst() and pollLast() methods return null if the deque is empty. The removeFirst() and removeLast() methods throw a NoSuchElementException if the deque is empty.

// Examine

E peekFirst()

Queue equivalent: peek()

E peekLast()

E getFirst()

Queue equivalent: element()

E getLast()

The ArrayDeque and LinkedList classes implement the Deque interface. The ArrayDeque class provides better performance than the LinkedList class for implementing FIFO queues, and is also a better choice than the java.util.Stack class for implementing stacks.

An ArrayDeque is also Iterable, and traversal is always from the head to the tail. The class provides the descendingIterator() method for iterating in reverse order. Since deques are not lists, positional access is not possible, nor can they be sorted.

Example 15.20 illustrates using an ArrayDeque both as a stack and as a FIFO queue. Elements from an array are pushed on to the stack at (3), and then popped from the stack at (5). The call to the isEmpty() method in the while loop at (4) determines whether the stack is empty. The output shows that the elements were popped in the reverse order to the order in which they were inserted, i.e., LIFO ordering.

Similarly, elements from an array are inserted at the tail of a FIFO queue at (8), and then removed from the head of the FIFO queue at (10). The call to the isEmpty() method in the while loop at (4) determines whether the FIFO queue is empty. The output shows that the elements were removed in the same order as they were inserted, i.e., FIFO ordering.

Note that in Example 15.20 the stack grows at the head of the deque, but the FIFO queue grows at the tail of the deque.