Chapter 11
The Collections Framework
When writing an object-oriented program, you often work with groups of objects, either objects of the same type or of different types. In Chapter 5, “Core Classes” you learned that arrays can be used to group objects of the same type. Unfortunately, arrays lack the flexibility you need to rapidly develop applications. They cannot be resized and they cannot hold objects of different types. Fortunately, Java comes with a set of interfaces and classes that make working with groups of objects easier: the Collections Framework. This chapter deals with the most important types in the Collections Framework that a Java beginner should know. Most of them are very easy to use and there's no need to provide extensive examples. More attention is paid to the last section of the chapter, “Making Your Objects Comparable and Sortable” where carefully designed examples are given because it is important for every Java programmer to know how to make objects comparable and sortable.
Note on Generics
Discussing the Collections Framework would be incomplete without generics. On the other hand, explaining generics without previous knowledge of the Collections Framework would be difficult. Therefore, there needs to be a compromise: The Collections Framework will be explained first in this chapter and will be revisited in Chapter 12, “Generics.” Since up to this point no knowledge of generics is assumed, the discussion of the Collections Framework in this chapter will have to use class and method signatures as they appear in pre-5 JDK—s, instead of signatures used in Java 5 or later that imply the presence of generics. As long as you read both this chapter and Chapter 12, you will have up-to date knowledge of both the Collections Framework and generics.
An Overview of the Collections Framework
A collection is an object that groups other objects. Also referred to as a container, a collection provides methods to store, retrieve, and manipulate its elements. Collections help Java programmers manage objects easily.
A Java programmer should be familiar with the most important types in the Collections Framework, all of which are part of the java.util package. The relationships between these types are shown in Figure 11.1.
/java%20book/images/java7_html_m6dfd926.jpg)
Figure 11.1: The Collections Framework
The main type in the Collections Framework is, unsurprisingly, the Collection interface. List, Set, and Queue are three main subinterfaces of Collection. In addition, there is a Mapinterface that can be used for storing key/value pairs. A subinterface of Map, SortedMap, guarantees that the keys are in ascending order. Other implementations of Map are AbstractMapand its concrete implementation HashMap. Other interfaces include Iterator and Comparator. The latter is used to make objects sortable and comparable.
Most of the interfaces in the Collections Frameworks come with implementation classes. Sometimes there are two versions of an implementation, the synchronized version and the unsynchronized version. For instance, the java.util.Vector class and the ArrayList class are implementations of the List interface. Both Vector and ArrayList provide similar functionality, however Vector is synchronized and ArrayList unsynchronized. Synchronized versions of an implementation were included in the first version of the JDK. Only later did Sun add the unsynchronized versions so that programmers could write better performing applications. The unsynchronized versions should thus be in preference to the synchronized ones. If you need to use an unsynchronized implementation in a multi-threaded environment, you can still synchronize it yourself.
Note
Working in a multi-threaded environment is discussed in Chapter 23, “Java Threads.”
The Collection Interface
The Collection interface groups objects together. Unlike arrays that cannot be resized and can only group objects of the same type, collections allow you to add any type of object and do not force you to specify an initial size.
Collection comes with methods that are easy to use. To add an element, you use the add method. To add members of another Collection, use addAll. To remove all elements, use clear. To inquire about the number of elements in a Collection, call its size method. To test if a Collection contains an element, use isEmpty. And, to move its elements to an array, use toArray.
An important point to note is that Collection extends the Iterable interface, from which Collection inherits the iterator method. This method returns an Iterator object that you can use to iterate over the collection's elements. Check the section, “Iterable and Iterator” later in this chapter.
In addition, you'll learn how to use the for statement to iterate over a Collection's elements.
List and ArrayList
List is the most popular subinterface of Collection, and ArrayList is the most commonly used implementation of List. Also known as a sequence, a List is an ordered collection. You can access its elements by using indices and you can insert an element into an exact location. Index 0 of a List references the first element, index 1 the second element, and so on.
The add method inherited from Collection appends the specified element to the end of the list. Here is its signature.
public boolean add(java.lang.Object element)
This method returns true if the addition is successful. Otherwise, it returns false. Some implementations of List, such as ArrayList, allow you to add null, some don—t.
List adds another add method with the following signature:
public void add(int index, java.lang.Object element)
With this add method you can insert an element at any position.
In addition, you can replace and remove an element by using the set and remove methods, respectively.
public java.lang.Object set(int index, java.lang.Object element) public java.lang.Object remove(int index)
The set method replaces the element at the position specified by index with element and returns the reference to the element inserted. The remove method removes the element at the specified position and returns a reference to the removed element.
To create a List, you normally assign an ArrayList object to a List reference variable.
List myList = new ArrayList();
The no-argument constructor of ArrayList creates an ArrayList object with an initial capacity of ten elements. The size will grow automatically as you add more elements than its capacity. If you know that the number of elements in your ArrayList will be more than its capacity, you can use the second constructor:
public ArrayList(int initialCapacity)
This will result in a slightly faster ArrayList because the instance does not have to grow in capacity.
List allows you to store duplicate elements in the sense that two or more references referencing the same object can be stored. Listing 11.1 demonstrates the use of List and some of its methods.
Listing 11.1: Using List
package app11;
import java.util.ArrayList;
import java.util.List;
public class ListTest {
public static void main(String[] args) {
List myList = new ArrayList();
String s1 = "Hello";
String s2 = "Hello";
myList.add(100);
myList.add(s1);
myList.add(s2);
myList.add(s1);
myList.add(1);
myList.add(2, "World");
myList.set(3, "Yes");
myList.add(null);
System.out.println("Size: " + myList.size());
for (Object object : myList) {
System.out.println(object);
}
}
}
When run, here is the result on the console.
Size: 6 100 Hello World Yes Hello 1 null
The java.util.Arrays class provides an asList method that lets you add multiple elements to a List in one go. For example, the following snippet adds multiple Strings in a single call.
List members = Arrays.asList("Chuck", "Harry", "Larry", "Wang");
List also adds methods to search the collection, indexOf and lastIndexOf:
public int indexOf(java.lang.Object obj) public int lastIndexOf(java.lang.Object obj)
indexOf compares the obj argument with its elements by using the equals method starting from the first element, and returns the index of the first match. lastIndexOf does the same thing but comparison is done from the last element to the first. Both indexOf and lastIndexOf return -1 if no match was found.
Note
List allows duplicate elements. By contrast, Set does not.
Iterating Over a Collection with Iterator and for
Iterating over a Collection is one of the most common tasks around when working with collections. There are two ways to do this: by using Iterator and by using for.
Recall that Collection extends Iterable, which has one method: iterator. This method returns a java.util.Iterator that you can use to iterate over the Collection. The Iterator interface has the following methods:
/java%20book/images/squf.jpg)
hasNext. Iterator employs an internal pointer that initially points to a place before the first element. hasNext returns true if there are more element(s) after the pointer. Calling nextmoves this pointer to the next element. Calling next for the first time on an Iterator causes its pointer to point to the first element. next. Moves the internal pointer to the next element and returns the element. Invoking next after the last element is returned throws a java.util.NoSuchElementException. Therefore, it is safest to call hasNext before invoking next to test if there is a next element. remove. Removes the element pointed by the internal pointer.
A common way to iterate over a Collection using an Iterator is either by employing while or for. Suppose myList is an ArrayList that you want to iterate over. The following snippet uses a while statement to iterate over a collection and print each element in the collection.
Iterator iterator = myList.iterator();
while (iterator.hasNext()) {
String element = (String) iterator.next();
System.out.println(element);
}
This is identical to:
for (Iterator iterator = myList.iterator(); iterator.hasNext(); ) {
String element = (String) iterator.next();
System.out.println(element);
}
The for statement can iterate over a Collection without the need to call the iterator method. The syntax is
for (Type identifier : expression) {
statement(s)
}
Here expression must be an Iterable. Since Collection extends Iterable, you can use enhanced for to iterate over any Collection. For example, this code shows how to use for.
for (Object object : myList) {
System.out.println(object);
}
Using for to iterate over a collection is a shortcut for using Iterator. In fact, the code that uses for above is translated into the following by the compiler.
for (Iterator iterator = myList.iterator(); iterator.hasNext(); ) {
String element = (String) iterator.next();
System.out.println(element);
}
Set and HashSet
A Set represents a mathematical set. Unlike List, Set does not allow duplicates. There must not be two elements of a Set, say e1 and e2, such that e1.equals(e2). The add method of Setreturns false if you try to add a duplicate element. For example, this code prints “addition failed.”
Set set = new HashSet();
set.add("Hello");
if (set.add("Hello")) {
System.out.println("addition successful");
} else {
System.out.println("addition failed");
}
The first time you called add, the string “Hello” was added. The second time around it failed because adding another “Hello” would result in duplicates in the Set.
Some implementations of Set allow at most one null element. Some do not allow nulls. For instance, HashSet, the most popular implementation of Set, allows at most one null element. When using HashSet, be warned that there is no guarantee the order of elements will remain unchanged. HashSet should be your first choice of Set because it is faster than other implementations of Set, TreeSet and LinkedHashSet.
Queue and LinkedList
Queue extends Collection by adding methods that support the ordering of elements in a first-in-first-out (FIFO) basis. FIFO means that the element first added will be the first you get when retrieving elements. This is in contrast to a List in which you can choose which element to retrieve by passing an index to its get method.
Queue adds the following methods.
offer. This method inserts an element just like the add method. However, offer should be used if adding an element may fail. This method returns false upon failing to add an element and does not throw an exception. On the other hand, a failed insertion with add throws an exception. remove. Removes and returns the element at the head of the Queue. If the Queue is empty, this method throws a java.util.NoSuchElementException. poll. This method is like the remove method. However, if the Queue is empty it returns null and does not throw an exception. element. Returns but does not remove the head of the Queue. If the Queue is empty, it throws a java.util.NoSuchElementException. peek. Also returns but does not remove the head of the Queue. However, peek returns null if the Queue is empty, instead of throwing an exception.
When you call the add or offer method on a Queue, the element is always added at the tail of the Queue. To retrieve an element, use the remove or poll method. remove and poll always remove and return the element at the head of the Queue.
For example, the following code creates a LinkedList (an implementation of Queue) to show the FIFO nature of Queue.
Queue queue = new LinkedList();
queue.add("one");
queue.add("two");
queue.add("three");
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
The code produces this result:
one two three
This demonstrates that remove always removes the element at the head of the Queue. In other words, you cannot remove “three” (the third element added to the Queue) before removing “one” and “two.”
Note
The java.util.Stack class is a Collection that behaves in a last-in-first-out (LIFO) manner.
Collection Conversion
Collection implementations normally have a constructor that accepts a Collection object. This enables you to convert a Collection to a different type of Collection. Here are the constructors of some implementations:
public ArrayList(Collection c) public HashSet(Collection c) public LinkedList(Collection c)
As an example, the following code converts a Queue to a List.
Queue queue = new LinkedList();
queue.add("Hello");
queue.add("World");
List list = new ArrayList(queue);
And this converts a List to a Set.
List myList = new ArrayList();
myList.add("Hello");
myList.add("World");
myList.add("World");
Set set = new HashSet(myList);
myList has three elements, two of which are duplicates. Since Set does not allow duplicate elements, only one of the duplicates will be accepted. The resulting Set in the above code only has two elements.
Map and HashMap
A Map holds key to value mappings. There cannot be duplicate keys in a Map and each key maps to at most one value.
To add a key/value pair to a Map, you use the put method. Its signature is as follows:
public void put(java.lang.Object key, java.lang.Object value)
Note that both the key and the value cannot be a primitive. However, the following code that passes primitives to both the key and the value is legal because boxing is performed before theput method is invoked.
map.put(1, 3000);
Alternatively, you can use putAll and pass a Map.
public void putAll(Map map)
You can remove a mapping by passing the key to the remove method.
public void remove(java.lang.Object key)
To remove all mappings, use clear. To find out the number of mappings, use the size method. In addition, isEmpty returns true if the size is zero.
To obtain a value, you can pass a key to the get method:
public java.lang.Object get(java.lang.Object key)
In addition to the methods discussed so far, there are three no-argument methods that provide a view to a Map.
keySet. Returns a Set containing all keys in the Map. values. Returns a Collection containing all values in the Map. entrySet. Returns a Set containing Map.Entry objects, each of which represents a key/value pair. The Map.Entry interface provides the getKey method that returns the key part and the getValue method that returns the value.
There are several implementations of Map in the java.util package. The most commonly used are HashMap and Hashtable. HashMap is unsynchronized and Hashtable is synchronized. Therefore, HashMap is the faster one between the two.
The following code demonstrates the use of Map and HashMap.
Map map = new HashMap();
map.put("1", "one");
map.put("2", "two");
System.out.println(map.size()); //print 2
System.out.println(map.get("1")); //print "one"
Set keys = map.keySet();
// print the keys
for (Object object : keys) {
System.out.println(object);
}
Making Objects Comparable and Sortable
In real life, objects are comparable. Dad's car is more expensive than Mom—s, this dictionary is thicker than those books, Granny is older than Auntie Mollie (well, yeah, living objects too are comparable), and so forth. In object-oriented programming there are often needs to compare instances of the same class. And, if instances are comparable, they can be sorted. As an example, given two Employee objects, you may want to know which one has been staying in the organization longer. Or, in a search method for Person instances whose first name is Larry, you may want to display search results sorted by age in descending or ascending order. You can make objects comparable by implementing the java.lang.Comparable andjava.util.Comparator interfaces. You'll learn to use these interfaces in the following sections.
Using java.lang.Comparable
The java.util.Arrays class provides the static method sort that can sort any array of objects. Here is its signature.
public static void sort(java.lang.Object[] a)
Because all Java classes derive from java.lang.Object, all Java objects are a type of java.lang.Object. This means you can pass an array of any objects to the sort method.
However, how does the sort method know how to sort arbitrary objects? It's easy to sort numbers or strings, but how do you sort an array of Elephant objects, for example?
First, examine the Elephant class in Listing 11.2.
Listing 11.2: The Elephant class
public class Elephant {
public float weight;
public int age;
public float tuskLength; // in centimeters
}
Since you are the author of the Elephant class, you get to decide how you want Elephant objects to be sorted. Let's say you want to sort them by their weights and ages. Now, how do you tell Arrays.sort of your decision?
Arrays.sort has defined a contract between itself and objects that needs its sorting service. The contract takes the form of the java.lang.Comparable interface. (See Listing 11.3)
Listing 11.3: The java.lang.Comparable method
package java.lang;
public interface Comparable {
public int compareTo(Object obj);
}
Any class that needs to support sorting by Arrays.sort must implement the Comparable interface. In Listing 11.3, the argument obj in the compareTo method refers to the object being compared with this object. The code implementation for this method in the implementing class must return a positive number if this object is greater than the argument object, zero if both are equal, and a negative number if this object is less than the argument object.
Listing 11.4 presents a modified Elephant class that implements Comparable.
Listing 11.4: The Elephant class implementing Comparable
package app11;
public class Elephant implements Comparable {
public float weight;
public int age;
public float tuskLength;
public int compareTo(Object obj) {
Elephant anotherElephant = (Elephant) obj;
if (this.weight > anotherElephant.weight) {
return 1;
} else if (this.weight < anotherElephant.weight) {
return -1;
} else {
// both elephants have the same weight, now
// compare their age
return (this.age - anotherElephant.age);
}
}
}
Now that Elephant implements Comparable, you can use Arrays.sort to sort an array of Elephant objects. The sort method will treat each Elephant object as a Comparable object (because Elephant implements Comparable, an Elephant object can be considered a type of Comparable) and call the compareTo method on the object. The sort method does this repeatedly until the Elephant objects in the array have been organized correctly by their weights and ages. Listing 11.5 provides a class that tests the sort method on Elephant objects.
Listing 11.5: Sorting elephants
package app11;
import java.util.Arrays;
public class ElephantTest {
public static void main(String[] args) {
Elephant elephant1 = new Elephant();
elephant1.weight = 100.12F;
elephant1.age = 20;
Elephant elephant2 = new Elephant();
elephant2.weight = 120.12F;
elephant2.age = 20;
Elephant elephant3 = new Elephant();
elephant3.weight = 100.12F;
elephant3.age = 25;
Elephant[] elephants = new Elephant[3];
elephants[0] = elephant1;
elephants[1] = elephant2;
elephants[2] = elephant3;
System.out.println("Before sorting");
for (Elephant elephant : elephants) {
System.out.println(elephant.weight + ":" +
elephant.age);
}
Arrays.sort(elephants);
System.out.println("After sorting");
for (Elephant elephant : elephants) {
System.out.println(elephant.weight + ":" +
elephant.age);
}
}
}
If you run the ElephantTest class, you'll see this on your console.
Before sorting 100.12:20 120.12:20 100.12:25 After sorting 100.12:20 100.12:25 120.12:20
Classes such as java.lang.String, java.util.Date, and primitive wrapper classes all implement java.lang.Comparable.
Using Comparable and Comparator
Implementing java.lang.Comparable enables you to define one way to compare instances of your class. However, objects sometimes are comparable in more ways. For example, twoPerson objects may need to be compared by age or by last/first name. In cases like this, you need to create a Comparator that defines how two objects should be compared. To make objects comparable in two ways, you need two comparators.
To create a comparator, you write a class that implements the Comparator interface. You then provide the implementation for its compare method. This method has the following signature.
public int compare(java.lang.Object o1, java.lang.Object o2)
compare returns zero if o1 and o2 are equal, a negative integer if o1 is less than o2, and a positive integer if o1 is greater than o2.
As an example, the Person class in Listing 11.6 implements Comparable. Listings 11.7 and 11.8 present two comparators of Person objects (by last name and by first name), andListing 11.9 offers the class that instantiates the Person class and the two comparators.
Listing 11.6: The Person class implementing Comparable.
package app11;
public class Person implements Comparable {
private String firstName;
private String lastName;
private int age;
public String getFirstName() {
return firstName;
}
public void setFirstName(String firstName) {
this.firstName = firstName;
}
public String getLastName() {
return lastName;
}
public void setLastName(String lastName) {
this.lastName = lastName;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public int compareTo(Object anotherPerson)
throws ClassCastException {
if (!(anotherPerson instanceof Person)) {
throw new ClassCastException(
"A Person object expected.");
}
int anotherPersonAge = ((Person) anotherPerson).getAge();
return this.age - anotherPersonAge;
}
}
Listing 11.7: The LastNameComparator class
package app11;
import java.util.Comparator;
public class LastNameComparator implements Comparator {
public int compare(Object person, Object anotherPerson) {
String lastName1 = ((Person)
person).getLastName().toUpperCase();
String firstName1 =
((Person) person).getFirstName().toUpperCase();
String lastName2 = ((Person)
anotherPerson).getLastName().toUpperCase();
String firstName2 = ((Person) anotherPerson).getFirstName()
.toUpperCase();
if (lastName1.equals(lastName2)) {
return firstName1.compareTo(firstName2);
} else {
return lastName1.compareTo(lastName2);
}
}
}
Listing 11.8: The FirstNameComparator class
package app11;
import java.util.Comparator;
public class FirstNameComparator implements Comparator {
public int compare(Object person, Object anotherPerson) {
String lastName1 = ((Person)
person).getLastName().toUpperCase();
String firstName1 = ((Person)
person).getFirstName().toUpperCase();
String lastName2 = ((Person)
anotherPerson).getLastName().toUpperCase();
String firstName2 = ((Person) anotherPerson).getFirstName()
.toUpperCase();
if (firstName1.equals(firstName2)) {
return lastName1.compareTo(lastName2);
} else {
return firstName1.compareTo(firstName2);
}
}
}
Listing 11.9: The PersonTest class
package app11;
import java.util.Arrays;
public class PersonTest {
public static void main(String[] args) {
Person[] persons = new Person[4];
persons[0] = new Person();
persons[0].setFirstName("Elvis");
persons[0].setLastName("Goodyear");
persons[0].setAge(56);
persons[1] = new Person();
persons[1].setFirstName("Stanley");
persons[1].setLastName("Clark");
persons[1].setAge(8);
persons[2] = new Person();
persons[2].setFirstName("Jane");
persons[2].setLastName("Graff");
persons[2].setAge(16);
persons[3] = new Person();
persons[3].setFirstName("Nancy");
persons[3].setLastName("Goodyear");
persons[3].setAge(69);
System.out.println("Natural Order");
for (int i = 0; i < 4; i++) {
Person person = persons[i];
String lastName = person.getLastName();
String firstName = person.getFirstName();
int age = person.getAge();
System.out.println(lastName + ", " + firstName +
". Age:" + age);
}
Arrays.sort(persons, new LastNameComparator());
System.out.println();
System.out.println("Sorted by last name");
for (int i = 0; i < 4; i++) {
Person person = persons[i];
String lastName = person.getLastName();
String firstName = person.getFirstName();
int age = person.getAge();
System.out.println(lastName + ", " + firstName +
". Age:" + age);
}
Arrays.sort(persons, new FirstNameComparator());
System.out.println();
System.out.println("Sorted by first name");
for (int i = 0; i < 4; i++) {
Person person = persons[i];
String lastName = person.getLastName();
tSring firstName = person.getFirstName();
int age = person.getAge();
System.out.println(lastName + ", " + firstName +
". Age:" + age);
}
Arrays.sort(persons);
System.out.println();
System.out.println("Sorted by age");
for (int i = 0; i < 4; i++) {
Person person = persons[i];
String lastName = person.getLastName();
String firstName = person.getFirstName();
int age = person.getAge();
System.out.println(lastName + ", " + firstName +
". Age:" + age);
}
}
}
If you run the PersonTest class, you will get the following result.
Natural Order Goodyear, Elvis. Age:56 Clark, Stanley. Age:8 Graff, Jane. Age:16 Goodyear, Nancy. Age:69 Sorted by last name Clark, Stanley. Age:8 Goodyear, Elvis. Age:56 Goodyear, Nancy. Age:69 Graff, Jane. Age:16 Sorted by first name Goodyear, Elvis. Age:56 Graff, Jane. Age:16 Goodyear, Nancy. Age:69 Clark, Stanley. Age:8 Sorted by age Clark, Stanley. Age:8 Graff, Jane. Age:16 Goodyear, Elvis. Age:56 Goodyear, Nancy. Age:69
Summary
In this chapter you have learned to use the core types in the Collections Framework. The main type is the java.util.Collection interface, which has three direct subinterfaces: List, Set, andQueue. Each subtype comes with several implementations. There are synchronized implementations and there are unsynchronized ones. The latter are usually preferable because they are faster.
There is also a Map interface for storing key/value pairs. Two main implementations of Map are HashMap and Hashtable. HashMap is faster than Hashtable because the former is unsynchronized and the latter is synchronized.
Lastly, you have also learned the java.lang.Comparable and java.util.Comparator interfaces. Both are important because they can make objects comparable and sortable.
Questions
1. Name at least seven types of the Collections Framework.
2. What is the different between ArrayList and Vector?
3. Why is Comparator more powerful than Comparable?
0 comments:
Post a Comment