SCJP : Collections and Generics

Given a design scenario, determine which collection classes and/or interfaces should be used to properly implement that design, including the use of the Comparable interface.

Summary of collections interfaces

Summary of general-purpose implementations

Summary of legacy implementations

Ordering

When you take an element out of a Collection, you must cast it to the type of element that is stored in the collection. Besides being inconvenient, this is unsafe. The compiler does not check that your cast is the same as the collection's type, so the cast can fail at run time.

Generics provides a way for you to communicate the type of a collection to the compiler, so that it can be checked. Once the compiler knows the element type of the collection, the compiler can check that you have used the collection consistently and can insert the correct casts on values being taken out of the collection.

Without generics:

static void expurgate(Collection c) {
	for (Iterator i = c.iterator(); i.hasNext(); ) {
		if (((String) i.next()).length() == 4) {
			i.remove();
		}
	}
}
					

Here is the same example modified to use generics:

					
static void expurgate(Collection<String> c) {
	for (Iterator<String> i = c.iterator(); i.hasNext(); ) {
		if (i.next().length() == 4) {
			i.remove();
		}
	}
}

					

When you see the code <Type>, read it as "of Type"; the declaration above reads as "Collection of String c". The code using generics is clearer and safer. We have eliminated an unsafe cast and a number of extra parentheses. The compiler can verify at compile time that the type constraints are not violated at run time. Because the program compiles without warnings, we can state with certainty that it will not throw a ClassCastException at run time. The net effect of using generics, especially in large programs, is improved readability and robustness.

public interface Queue<E> extends Collection<E>

A collection designed for holding elements prior to processing. Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations.

Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator, or the elements' natural ordering, and LIFO queues (or stacks) which order the elements LIFO (last-in-first-out). Whatever the ordering used, the head of the queue is that element which would be removed by a call to remove() or poll(). In a FIFO queue, all new elements are inserted at the tail of the queue. Other kinds of queues may use different placement rules. Every Queue implementation must specify its ordering properties.

The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or "bounded") queues.

The remove() and poll() methods remove and return the head of the queue. Exactly which element is removed from the queue is a function of the queue's ordering policy, which differs from implementation to implementation. The remove() and poll() methods differ only in their behavior when the queue is empty: the remove() method throws an exception, while the poll() method returns null.

The element() and peek() methods return, but do not remove, the head of the queue.

The Queue interface does not define the blocking queue methods, which are common in concurrent programming. These methods, which wait for elements to appear or for space to become available, are defined in the BlockingQueue interface, which extends this interface.

Queue implementations generally do not allow insertion of null elements, although some implementations, such as LinkedList, do not prohibit insertion of null. Even in the implementations that permit it, null should not be inserted into a Queue, as null is also used as a special return value by the poll method to indicate that the queue contains no elements.

Queue implementations generally do not define element-based versions of methods equals and hashCode but instead inherit the identity based versions from class Object, because element-based equality is not always well-defined for queues with the same elements but different ordering properties.

public boolean offer(E element)

public E remove()      // removes !
public E poll()        // removes !

public E element()     // DOES NOT remove !
public E peek()        // DOES NOT remove !
					

PriorityQueue<E>

An unbounded priority queue based on a priority heap. This queue orders elements according to an order specified at construction time, which is specified either according to their natural order (see Comparable), or according to a Comparator, depending on which constructor is used. A priority queue DOES NOT permit null elements. A priority queue relying on natural ordering also DOES NOT permit insertion of non-comparable objects (doing so may result in ClassCastException).

NOTE, java.lang.String implements Comparable.

The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements - ties are broken arbitrarily. The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.

Example:

PriorityQueue queue = new PriorityQueue();
queue.offer("CCC-1");
queue.offer("BBB");
queue.offer("AAA");
queue.offer("CCC-2");
		
out.println("1. " + queue.poll()); // removes
out.println("2. " + queue.poll()); // removes
out.println("3. " + queue.peek());
out.println("4. " + queue.peek());
out.println("5. " + queue.remove()); // removes
out.println("6. " + queue.remove()); // removes
out.println("7. " + queue.peek());
out.println("8. " + queue.element()); // Throws NoSuchElementException !
					

1. AAA
2. BBB
3. CCC-1
4. CCC-1
5. CCC-1
6. CCC-2
7. null
Exception in thread "main" java.util.NoSuchElementException
	at java.util.AbstractQueue.element(Unknown Source)
	at regex.Replacement.main(Replacement.java:28)
					

Non-generic collections

Example of using raw (non-parameterized) collections with generics (parameterized) collections:

ArrayList list = new ArrayList(); // OK 
ArrayList<String> listStr = list; // WARNING, but OK
ArrayList<StringBuffer> listBuf = list; // WARNING, but OK
listStr.add(0, "Hello"); // OK
StringBuffer buff = listBuf.get(0); // Runtime Exception !
					
					

Exception in thread "main" java.lang.ClassCastException: java.lang.String
	at Client.main(Client1.java:28)
					

Parameters and arguments

In Java 5.0 code, generics will manifest itself in two forms, as type parameters and as type arguments. You will be familiar with the distinction between parameters and arguments in methods:

void foo(int aaa, int bbb) {
	...
}

void bar(int ccc) {
	foo(ccc, 142);
}
					
					

Also note that ccc is both a parameter of bar(...) and an argument to foo(...) (this will also happen in generics with type parameters and arguments).

Reading generics is a matter of working out where a type parameter is being declared, and where a type argument is being passed.

Type parameters

Type parameters can appear in two locations, class (or interface) declarations, and method declarations. When type parameters are used, we are saying that this class/interface/method body is parameterized over those types. We can use those type parameters in the body as if they were a real classname we had imported, but we don't care what actual class it is.

A generic class/interface is declared by putting type parameters after the name of the class/interface. Type parameters begin and end with angle brackets and are separated by commas. You can specify more than one type parameter, and each type parameter can have a bound (constraint):

					
public class Foo <TypeParam1, TypeParam2> {
	...
	// type parameters used here
	...
}

					

					
public interface I<T> {
	public T getData();
	public void releaseData(T data);
}

					

A type bound places a constraint on the type arguments that can be passed to the type parameter.

No bound, any type argument can be used:

					
<T>

					

T can be any subclass of InputStream:

					
<T extends InputStream>

					

T must implement the Serializable interface (NOTE, that extends is used here, even when talking about implementing interfaces):

					
<T extends Serializable>

					

T must be a subclass of InputStream and implement Serializable:

					
<T extends InputStream & Serializable>

					

T must implement three interfaces:

<T extends Serializable & Runnable & Cloneable>

					

Two type parameters (such as the type of the keys, and type of the values, in a Map):

<K, V>

					

Two type parameters; the second bound is defined in terms of the first. Type bounds can be mutually- or even self-recursive:

<T, C extends Comparator<T>> 

					

Lets define our own immutable "pair" class. Notice how we have declared fields and methods in terms of the type parameters. getFirst() is a method in a generic class and uses one of the generic type parameters, but that is different to a generic method:

public class Pair <X, Y> {
	private final X a;
	private final Y b;
    
	public Pair(X a, Y b) {
		this.a = a;
		this.b = b;
	}
   
	public X getFirst() {
		return a;
	}
	public Y getSecond() {
		return b;
	}
}
					
					

Methods can have their own type parameters, independent of the type parameters of the enclosing class (or even if the enclosing class is not generic). The type parameters go just before the return type of the method declaration:

class PairUtil {
	
	public static <A extends Number, B extends Number> double add(Pair<A, B> p) {
		return p.getFirst().doubleValue() + p.getSecond().doubleValue();
	}

	public static <A, B> Pair<B, A> swap(Pair<A, B> p) {
		A first = p.getFirst();
		B second = p.getSecond();
		return new Pair<B, A>(second, first);
	}
}
					
					

We have done a few things in the add(...) method:

The second method, swap(...), is even more interesting:

Type arguments

Type parameters are for defining generic classes; type arguments are for using generic classes. And you will be using generic classes far more often than you write them.

Wherever you use a generic classname, you need to supply the appropriate type arguments. These arguments go straight after the classname, surrounded by angle brackets. The arguments you supply must satisfy any type bounds on the type parameters. There are 5 main contexts where you can use type arguments, shown here.

Declaring instance variables

public class Basket<E> {
	...
}

class Fruit {
}

class Apple extends Fruit {
}

class Orange extends Fruit {
}
					
					

					
Basket b = new Basket(); // OK !
Basket b1 = new Basket<Fruit>();  // OK !
Basket<Fruit> b2 = new Basket<Fruit>(); // OK !

// Type mismatch: cannot convert from Basket<Fruit> to Basket<Apple>
Basket<Apple> b3 = new Basket<Fruit>(); // WRONG !!! 

// Type mismatch: cannot convert from Basket<Apple> to Basket<Fruit>
Basket<Fruit> b4 = new Basket<Apple>();  // WRONG !!!

Basket<?> b5 = new Basket<Apple>(); // OK !

// 1. Cannot instantiate the type Basket<?>
// 2. Type mismatch: cannot convert from Basket<?> to Basket<Apple>
Basket<Apple> b6 = new Basket<?>(); // WRONG !!!

					

Implementing generic types

In addition to using generic types, you can implement your own. A generic type has one or more type parameters. Here is an example with only one type parameter called E. A parameterized type must be a reference type, and therefore primitive types are NOT allowed to be parameterized types.

					
interface List<E> {
	void add(E x);
	Iterator<E> iterator();
}

interface Iterator<E> {
	E next();
	boolean hasNext();
}


class LinkedList<E> implements List<E> {
	// implementation   
}

					

Here, E represents the type of elements contained in the collection. Think of E as a placeholder that will be replaced by a concrete type. For example, if you write LinkedList<String> then E will be replaced by String.

In some of your code you may need to invoke methods of the element type, such as Object's hashCode() and equals(). Here is an example that takes two type parameters:

					
class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V> {
	...
	public V get(Object k) {
		...
		int hash = k.hashCode();  
		...
	}
}

					

Generic methods

Genericity is not limited to classes and interfaces, you can define generic methods. Static methods, nonstatic methods, and constructors can all be parameterized in almost the same way as for classes and interfaces, but the syntax is a bit different. Generic methods are also invoked in the same way as non-generic methods.

Before we see an example of a generics method, consider the following segment of code that prints out all the elements in a collection:

public void printCollection(Collection c) {
	Iterator i = c.iterator();
	for(int k = 0; k < c.size() ; k++) {
		out.printn(i.next());
	}
}
					

Using generics, this can be re-written as follows. Note that the Collection<?> is the collection of an unknown type:

void printCollection(Collection<?> c) {
	for(Object o:c) {
		out.println(e);
	}
}

					

Some more generics examples:

public class Basket<E> {
	private E element;
	
	public void setElement(E x) {
		element = x;
	}
	
	public E getElement() {
		return element;		
	}
}

class Fruit {
}

class Apple extends Fruit {
}

class Orange extends Fruit {
}
						
					

Basket<Fruit> basket = new Basket<Fruit>();
basket.setElement(new Apple()); // OK, can assign Apple reference to Fruit variable

// Type mismatch: cannot convert from Fruit to Apple !!!
Apple apple = basket.getElement(); // WRONG ! Compilation error ! 

Apple apple = (Apple) basket.getElement(); // OK ! Compiles and runs fine.

					

A client code (runtime exception):

Basket<Fruit> basket = new Basket<Fruit>();
basket.setElement(new Apple());
Orange orange = (Orange) basket.getElement(); // Runtime exception !!!
					
					

Exception in thread "main" java.lang.ClassCastException: Apple
	at Client.main(Client1.java:8)
					

Wildcards

There are three types of wildcards:

As an example of using wildcards, consider a draw() method that should be capable of drawing any shape such as circle, rectangle, and triangle. The implementation may look something like this. Here Shape is an abstract class with three subclasses: Circle, Rectangle, and Triangle:

public void draw(List<Shape> shape) {
	for(Shape s: shape) {
		s.draw(this);
	}
}

					

It is worth noting that the draw(...) method can only be called on lists of Shape and cannot be called on a list of Circle, Rectangle, and Triangle for example. In order to have the method accept any kind of shape, it should be written as follows:

public void draw(List<? extends Shape> shape) {
	for(Shape s: shape) {
		s.draw(this);
	}
}

					
					
					

public static <T extends Comparable<? super T>> void sort(List<T> list) {
	Object a[] = list.toArray();
	Arrays.sort(a);
	ListIterator<T> i = list.listIterator();
	for (int j = 0; j < a.length; j++) {
		...
	}
}

					

Another example of unbounded wildcards:

Basket<?> basket = new Basket<Apple>();
basket.setElement(new Apple()); // WRONG !!!
Apple apple = (Apple) basket.getElement();
					
					

If we have some subclasses of the Apple class:

class GoldenDelicious extends Apple {}
class Jonagold extends Apple {}
					
					

					
public static boolean isRipeInBasket(Basket<? extends Apple> basket) {
	Apple apple = basket.getElement();
	...
}	

					

public static <A extends Apple> boolean isRipeInBasket(Basket<A> basket) {
	Apple apple = basket.getElement();
	...
}

					

If we want to add some sort of apples to basket, the following generic method is required:

public static <A extends Apple> void insert(A apple, Basket<? super A> basket) {
	basket.setElement(apple);
}
					
					

public static <A extends Apple> void insert(Apple apple, Basket<? super A> basket) {
	basket.setElement(apple);
}

					

Wild-cards in type arguments

Java 5.0 allows the use of a wild-card in a type argument, in order to simplify the use of generics (easier to type, and to read).

For example, you may want to use a generic class, but you don't particularly care what the type argument is. What you could do is specify a "dummy" type parameter T, as in the generic method count_0() below:

public static <T> int count_0(List<T> list) {
    int count = 0;
    for (T n : list) {
        count++;
    }
    return count;
}
					
					

Alternatively, you can avoid creating a generic method, and just use a ? wild-card as in count_1(). You should read List<?> as "a list of whatever":

public static int count_1(List<?> list) {
    int count = 0;
    for (Object n : list) {
        count++;
    }
    return count;
}
					
					

Wild-cards with upper and lower bounds

The next two methods use a bounded wild-card to express the required subclass/superclass relationship. You should read List<? extends T> as "A list of T, or any subclass of T". You can read List<? super T> as "A list of T, or any T's super-classes":

List<Number> listOfNumbers = new ArrayList<Number>();
listOfNumbers.add(new Integer(3));
listOfNumbers.add(new Double(4.0));

List<Integer> listOfIntegers = new ArrayList<Integer>();
listOfIntegers.add(new Integer(3));
listOfIntegers.add(new Integer(4));		

		
addAll_1(listOfIntegers, listOfNumbers);
addAll_2(listOfIntegers, listOfNumbers);
...

/**
 * Append src to dest, so long as "whatever the types of things in src are",
 * they extend "the types of things in dest".
 */
public static <T> void addAll_1(List<? extends T> src, List<T> dest) {
	for (T o : src) {
		dest.add(o);
	}
}

/**
 * Append src to dest, so long as "whatever the types of things dest can hold",
 * they are a superclass of "the types of things in src".
 */
public static <T> void addAll_2(List<T> src, List<? super T> dest) {
	for (T o : src) {
		dest.add(o);
	}
}
					
					

Erasure

Generics are implemented by the Java compiler as a front-end conversion called erasure, which is the process of translating or rewriting code that uses generics into non-generic code (that is, maps the new syntax to the current JVM specification). In other words, this conversion erases all generic type information; all information between angle brackets is erased. For example, LinkedList<Integer> will become LinkedList. Uses of other type variables are replaced by the upper bound of the type variable (for example, Object), and when the resulting code is not type correct, a cast to the appropriate type is inserted.

Let's take a look at the following code:

public class Basket<E> {
	private E element;
	
	public void setElement(E x) {
		element = x;
	}
	
	public E getElement() {
		return element;		
	}
}

class Fruit {
}

class Apple extends Fruit {
}

class Orange extends Fruit {
}
					
					

Basket basket = new Basket<Orange>();
basket.setElement(new Apple());
Apple apple = (Apple) basket.getElement();
					
					

The following example gives compile time error:

public <A extends Fruit> void erasureTest(A a) {}
public <B extends Fruit> void erasureTest(B b) {} // WRONG !!!
					
					

public void erasureTest(Fruit a) {}
public void erasureTest(Fruit b) {} // WRONG !!!
					

The following methods also will cause a compile time error:

public static void erasureTest2(Basket<? extends Apple> basket) {}	
public static void erasureTest2(Basket<? extends Orange> basket) {} // WRONG !!!
					
					

public static void erasureTest2(Basket basket) {}	
public static void erasureTest2(Basket basket) {} // WRONG !!!
					

The following code is a legal example of overloaded methods:

public static <A extends Apple>	 void erasureTest2(A a, Basket<? super A> b){} // OK
public static <G extends Orange> void erasureTest2(G g, Basket<? super G> b){} // OK
					
					

public static void erasureTest2(Apple a,  Basket b)		
public static void erasureTest2(Orange g, Basket b)

The following code will compile (with warnings):

Basket<Orange> bO = new Basket<Orange>();
Basket b = bO;
Basket<Apple> bA = (Basket<Apple>) b; // WARNING
					
					

Basket bA = (Basket) b;
					

The using of instanceof is ILLEGAL with parameterized types:

Collection cs = new ArrayList<String>();
if (cs instanceof Collection<String>) { // WRONG !!! Compilation error !
	...
}
					
					

Arrays and generics

The component type of an array object may not be a type variable or a parameterized type, unless it is an (unbounded) wildcard type. You can declare array types whose element type is a type variable or a parameterized type, but not array objects.

// Cannot create a generic array of Basket<Apple>
Basket<Apple>[] b  = new Basket<Apple>[10]; // WRONG !!!!

// Cannot create a generic array of Basket<Apple>
Basket<?>[] b1 = new Basket<Apple>[10]; // WRONG !!!

Basket<?>[] b2 = new Basket<?>[10]; // OK !

public <T> T[] test() { // OK !
	return null;
}

// Cannot create a generic array of T
public <T> T[] test1() { // WRONG !!!
	return new T[10];
}