Creating Generic Collection Classes

In the previous two chapters, you've seen how you can specify the type for an ArrayList or a LinkedList so the compiler can prevent you from accidentally adding the wrong type of data to the collection. The ArrayList and LinkedList classes can do this because they take advantage of a feature called generics. Generics first became available in Java 1.5.

In this chapter, I show you how the generics feature works and how to put it to use in your own classes. Specifically, you see examples of two classes that use the LinkedList class to implement a specific kind of collection. The first is a stack, a collection in which items are always added to the front of the list and retrieved from the front of the list. The second is a queue, a collection in which items are added to the end of the list and retrieved from the front.

TECHNICAL STAUFF 

This is one of those chapters where the entire chapter gets a Technical Stuff icon. Frankly, generics is on the leading edge of object-oriented programming. You can get by without knowing any of the information in this chapter, so feel free to skip it if you're on your way to something more interesting. However, this chapter is worth looking at even if you just want to get an idea of how the ArrayList and LinkedList classes use the new generics feature. And, you might find that someday you want to create your own generic classes. Your friends will surely think you're a genius.

To be sure, I won't be covering all the intricacies of programming with generics. If your next job happens to be writing Java class libraries for Sun, you'll need to know a lot more about generics than this chapter covers. I focus just on the basics of writing simple generic classes.

Why Generics?

Before Java 1.5, collection classes could hold any type of object. For example, the add method for the ArrayList class had this declaration:

public boolean add(Object o)
{
 // code to implement the add method
}

Thus, you could pass any type of object to the add method-and the array list gladly accepts it.

When you retrieved an item from a collection, you had to cast it to the correct object type before you could do anything with it. For example, if you had an array list named empList with Employee objects, you'd use a statement like this one to get the first Employee from the list:

Employee e = (Employee)empList.get(0);

The trouble is, what if the first item in the list isn't an Employee? Because the add method accepts any type of object, there was no way to guarantee that only certain types of objects could be added to the collection.

That's why generics were invented. Now you can declare the ArrayList like this:

ArrayList empList = new ArrayList();

Here empList is declared as an ArrayList that can hold only Employee types. Now the add method has a declaration that is the equivalent of this:

public boolean add(Employee o)
{
 // code to implement the add method
}

Thus, you can only add Employee objects to the list. And the get method has a declaration that's equivalent to this:

public Employee get(int index)
{
 // code to implement the get method
}

Thus, the get method returns Employee objects. You don't have to cast the result to an Employee because the compiler already knows the object is an Employee.

Creating a Generic Class

Generics let you create classes that can be used for any type specified by the programmer at compile time. To accomplish that, the Java designers introduced a new feature to the language, called formal type parameters. To create a class that uses a formal type parameter, you list the type parameter after the class name in angle brackets. The type parameter has a name-Sun recommends you use single uppercase letters for type parameter names-that you can then use throughout the class anywhere you'd otherwise use a type.

For example, here's a simplified version of the class declaration for the ArrayList class:

public class ArrayList

I left out the extends and implements clauses to focus on the formal type parameter: . The E parameter specifies the type of the elements that are stored in the list. Sun recommends the type parameter name E (for Element) for any parameter that specifies element types in a collection.

So consider this statement:

ArrayList empList;

Here the E parameter is Employee, which simply means that the element type for this instance of the ArrayList class is Employee.

Now take a look at the declaration for the add method for the ArrayList class:

public boolean add(E o)
{
 // body of method omitted (thank you)
}

Where you normally expect to see a parameter type, you see the letter E. Thus, this method declaration specifies that the type for the o parameter is the type specified for the formal type parameter E. If E is Employee, that means the add method only accepts Employee objects.

So far, so good. Now take a look at how you can use a formal type parameter as a return type. Here's the declaration for the get method:

public E get(int index)
{
 // body of method omitted (you're welcome)
}

Here, E is specified as the return type. That means that if E is Employee, this method returns Employee objects.

One final technique you need to know before moving on: You can use the formal type parameter within your class to create objects of any other class that accepts formal type parameters. For example, the clone method of the ArrayList class is written like this:

public Object clone()
{
 try
 {
 ArrayList v = (ArrayList) super.clone();
 v.elementData = (E[])new Object[size];
 System.arraycopy(elementData, 0,
 v.elementData, 0, size);
 v.modCount = 0;
 return v;
 }
 catch (CloneNotSupportedException e)
 {
 // this shouldn't happen since we're Cloneable
 throw new InternalError();
 }
}

You don't need to look much at the details in this method; just notice that the first statement in the try block declares an ArrayList of type . In other words, the ArrayList class uses its own formal type parameter to create another array list object of the same type. If you think about it, that makes perfect sense. After all, that's what the clone method does: It creates another array list just like this one.

The key benefit of generics is that this typing happens at compile time. Thus, after you specify the value of a formal type parameter, the compiler knows how to do the type checking implied by the parameter. That's how it knows not to let you add String objects to an Employee collection.

A Generic Stack Class

Now that you've seen the basics of creating generic classes, in this section you look at a simple generic class that implements a stack. A stack is a simple type of collection that lets you add objects to the top of the collection and remove them from the top. I name this Stack class in this section GenStack, and it has five methods:

• push: This method adds an object to the top of the stack.
• pop: This method retrieves the top item from the stack. The item is removed from the stack in the process. If the stack is empty, this method returns null.
• peek: This method lets you peek at the top item on the stack. In other words, it returns the top item without removing it. If the stack is empty, it returns null.
• hasItems: This method returns a boolean value of true if the stack has at least one item in it.
• size: This method returns an int value that indicates how many items are in the stack.

The GenStack class uses a LinkedList to implement the stack. For the most part, this class simply exposes the various methods of the LinkedList class using names that are more appropriate for a stack. The complete code for the GenStack class is shown in Listing 5-1.

Listing 5-1: The GenStack Class

import java.util.*;

public class GenStack → 3
{
 private LinkedList list = new LinkedList(); → 5
 public void push(E item) → 7
 {
 list.addFirst(item);
 }

 public E pop() → 12
 {
 return list.poll();
 }

 public E peek() → 17
 {
 return list.peek();
 }

 public boolean hasItems() → 22
 {
 return !list.isEmpty();
 }

 public int size() → 27

 {
 return list.size();
 }
}

The following paragraphs highlight the important details in this class:

→ 3	The class declaration specifies the formal type parameter . Thus, users of this class can specify the type for the stack's elements.
→ 5	This class uses a private LinkedList object list to keep the items stored in the stack. The LinkedList is declared with the same type as the GenStack class itself. Thus, if the E type parameter is Employee, the type for this LinkedList is Employee.
→ 7	The push method accepts a parameter of type E. It uses the linked list's addFirst method to add the item to the beginning of the list.
→ 12	The pop method returns a value of type E. It uses the linked list's poll method, which removes and returns the first element in the linked list. If the list is empty, the poll method-and therefore the pop method-returns null.
→ 17	The peek method also returns a value of type E. It simply returns the result of the linked list's peek method.
→ 22	The hasItems method returns the opposite of the linked list's isEmpty method.
→ 27	The size method simply returns the result of the linked list's size method.

Open table as spreadsheet

That's all there is to it. The following program gives the GenStack class a little workout to make sure it functions properly:

public class GenStackTest
{
 public static void main(String[] args)
 {
 GenStack gs = new GenStack();

 System.out.println(
 "Pushing four items onto the stack.");
 gs.push("One");
 gs.push("Two");
 gs.push("Three");

 gs.push("Four");

 System.out.println("There are "
 + gs.size() + " items in the stack.
");

 System.out.println("The top item is: "
 +gs.peek() + "
");

 System.out.println("There are still "
 + gs.size() + " items in the stack.
");

 System.out.println("Popping everything:");
 while (gs.hasItems())
 System.out.println(gs.pop());

 System.out.println("There are now "
 + gs.size() + " items in the stack.
");

 System.out.println("The top item is: "
 +gs.peek() + "
");

 }
}

This program creates a GenStack object that can hold String objects. It then pushes four strings onto the stack and prints the number of items in the stack. Next, it uses the peek method to print the top item and again prints the number of items in the stack, just to make sure the peek method doesn't accidentally remove the item. Next, it uses a while loop to pop each item off the stack and print it. Then it once again prints the number of items (which should now be zero), and it peeks at the top item (which should be null).

Here's the output that results when you run this program:

Pushing four items onto the stack.
There are 4 items in the stack.

The top item is: Four

There are still 4 items in the stack.

Popping everything:
Four
Three
Two
One
There are now 0 items in the stack.

The top item is: null

Tip 

Notice that when the program pops the items off the stack, they come out in reverse order in which they were pushed on to the stack. That's normal behavior for stacks. In fact, stacks are sometimes called Last-In, First-Out lists, or LIFO lists, for this very reason.

Using Wildcard Type Parameters

public void addItems(ArrayList list)
{
 // body of method not shown
}

Thought question: Does the following statement compile?

addItems(new ArrayList());

Answer: Nope.

That's surprising because String is a subtype of Object. So you'd think that a parameter that says it accepts an ArrayList of objects accepts an ArrayList of strings.

Unfortunately, inheritance doesn't work quite that way when it comes to formal type parameters. Instead, you have to use another feature of generics, called wildcards.

In short, if you want to create a method that accepts any type of ArrayList, you have to code the method like this:

public void addItems(ArrayList list)

In this case, the question mark indicates that you can code any kind of type here.

That's almost as good as inheritance, but what if you want to actually limit the parameter to collections of a specific superclass? For example, suppose you're working on a payroll system that has an Employee superclass with two subclasses named HourlyEmployee and SalariedEmployee, and you want this method to accept an ArrayList of Employee objects, HourlyEmployee objects, or SalariedEmployee objects?

In that case, you can add an extends clause to the wildcard, like this:

public void addItems(ArrayList list)

Then you can call the addItems method with an ArrayList of type Employee, HourlyEmployee, or SalariedEmployee.

Now, before you call it a day, take this example one step farther: Suppose this addItems method appears in a generic class that uses a formal type parameter to specify the type of elements the class accepts, and you want the addItems method to accept an ArrayList of type E or any of its subclasses. To do that, you'd declare the addItems method like this:

public void addItems(ArrayList list)

Here the wildcard type parameter simply means that the ArrayList can be of type E or any type that extends E.

A Generic Queue Class

Now that you've seen how to use wildcards in a generic class, this section presents a generic class that implements a queue. A queue is another type of collection that lets you add objects to the end of the collection and remove them from the top. Queues are commonly used in all sorts of applications, from data processing applications to sophisticated networking systems.

This queue class is named GenQueue and has the following methods:

• enqueue: This method adds an object to the end of the queue.
• dequeue: This method retrieves the first item from the queue. The item is removed from the queue in the process. If the queue is empty, this method returns null.
• hasItems: This method returns a boolean value of true if the queue has at least one item in it.
• size: This method returns an int value that indicates how many items are in the stack.
• addItems: This method accepts another GenQueue object as a parameter. All the items in that queue are added to this queue. In the process, all the items from the queue passed to the method are removed. The GenQueue parameter must be of the same type as this queue or a sub-type of this queue's type.

The GenQueue class uses a LinkedList to implement its queue. The complete code for the GenQueue class is shown in Listing 5-2.

Listing 5-2: The GenQueue Class

import java.util.*;

public class GenQueue → 3
{
 private LinkedList list = new LinkedList(); → 5
 public void enqueue(E item) → 7
 {
 list.addLast(item);
 }

 public E dequeue() → 12
 {
 return list.poll();
 }

 public boolean hasItems() → 17
 {
 return !list.isEmpty();
 }

 public int size() → 22
 {
 return list.size();
 }

 public void addItems(GenQueue q) → 27
 {
 while (q.hasItems())
 list.addLast(q.dequeue());
 }
}

The following paragraphs point out the highlights of this class:

→ 3	The class declaration specifies the formal type parameter . Thus, users of this class can specify the type for the elements of the queue.
→ 5	Like the GenStack class, this class uses a private LinkedList object list to keep its items.
→ 7	The enqueue method accepts a parameter of type E. It uses the linked list's addLast method to add the item to the end of the queue.
→ 12	The dequeue method returns a value of type E. Like the pop method of the GenStack class, this method uses the linked list's poll method to return the first item in the list.
→ 17	The hasItems method returns the opposite of the linked list's isEmpty method.
→ 22	The size method returns the result of the linked list's size method.
→ 27	The addItems method accepts a parameter that must be another GenQueue object whose element type is either the same type as this GenQueue object's elements or a subtype of this GenQueue object's element type. This method uses a while loop to remove all the items from the q parameter and add them to this queue.

Open table as spreadsheet

The following program exercises the GenQueue class:

public class GenQueueTest
{
 public static void main(String[] args)
 {
 GenQueue empList;
 empList = new GenQueue();

 GenQueue hList;
 hList = new GenQueue();
 hList.enqueue(new HourlyEmployee(
 "Trump", "Donald"));
 hList.enqueue(new HourlyEmployee(
 "Gates", "Bill"));
 hList.enqueue(new HourlyEmployee(
 "Forbes", "Steve"));

 empList.addItems(hList);

 while (empList.hasItems())
 {
 Employee emp = empList.dequeue();
 System.out.println(emp.firstName
 + " " + emp.lastName);
 }
 }
}

class Employee
{
 public String lastName;
 public String firstName;

 public Employee() {}

 public Employee(String last, String first)
 {
 this.lastName = last;

 this.firstName = first;
 }

 public String toString()
 {
 return firstName + " " + lastName;
 }
}

class HourlyEmployee extends Employee
{
 public double hourlyRate;

 public HourlyEmployee(String last, String first)
 {
 super(last, first);
 }
}

This program begins by creating a GenQueue object that can hold Employee objects. This queue is assigned to a variable named empList.

Next, the program creates another GenQueue object. This one can hold HourlyEmployee objects (HourlyEmployee is a subclass of Employee) and is assigned to a variable named hList.

Then three rookie employees are created and added to the hList queue. The addItems method of the empList queue is then called to transfer these employees from the hList queue to the empList queue. Because HourlyEmployee is a subclass of Employee, the addItems method of the empList queue accepts hList as a parameter.

Finally, a while loop is used to print the employees that are now in the empList queue.

When this program is run, the following is printed on the console:

Donald Trump
Bill Gates
Steve Forbes

Thus, the addItems method successfully transferred the employees from the hlist queue, which held HourlyEmployee objects, to the empList queue, which holds Employee objects.