Java Technology Home Page
A-Z Index

Java Developer Connection(SM)
Books

Downloads, APIs, Documentation
Java Developer Connection
Tutorials, Tech Articles, Training
Online Support
Community Discussion
News & Events from Everywhere
Products from Everywhere
How Java Technology is Used Worldwide
Print Button
 
Book Excerpt Index

Core Java 2, Volume II

by Cay S. Horstmann and Gary Cornell

Chapter 2: Collections

(December 1999)

The Java Developer Connection is pleased to present a chapter excerpt from "Core Java 2 Volume II--Advanced Features," by Cay S. Horstmann and Gary Cornell, published December 1999 by Sun Microsystems Press.

Chapter 2, "Collections" covers the collections framework of the JavaTM 2 platform. When you want to collect multiple objects and retrieve them later, instead of just tossing the elements into a Vector, you can use a collection that is best suited for your circumstances. This chapter shows you how to take advantage of the standard collections that are prebuilt for your use. "Core Java 1" covers the essential features of the language. This second volume "Core Java 2" covers advanced topics that a programmer needs to know for professional software development. Both volumes are intended for programmers who want to put Java technology to work on real projects.

Object-oriented programming encapsulates data inside classes, but this doesn't make the organization of data inside the classes any less important than in traditional programming languages. Of course, how you choose to structure the data depends on the problem you are trying to solve. Does your class need a way to easily search through thousands (or even millions) of items quickly? Does it need an ordered sequence of elements and the ability to rapidly insert and remove elements in the middle of the sequence? Does it need an arraylike structure with random-access ability that can grow at run time? The way you structure your data inside your classes can make a big difference when it comes to implementing methods in a natural style, as well as for performance.

This chapter shows how JavaTM technology can help you accomplish the traditional data structuring needed for serious programming. In college computer science programs, there is a course called Data Structures that usually takes a s emester to complete, so there are many, many books devoted to this important topic. Exhaustively covering all the data structures that may be useful is not our goal in this chapter; instead, we cover the fundamental ones that the standard Java library supplies. We hope that, after you finish this chapter, you will find it easy to translate any of your data structures to the Java programming language.

Collection Interfaces

Before the release of the JavaTM 2 platform, the standard library supplied only a small set of classes for the most useful data structures: Vector, Stack, Hashtable, BitSet, and the Enumeration interface that provides an abstract mechanism for visiting elements in an arbitrary container. That was certainly a wise choice--it takes time and skill to come up with a comprehensive collection class library.

With the advent of the Java 2 platform, the designers felt that the time had come to roll out a full-fledged set of data structures. They faced a number of conflicting design decisions. They wanted the library to be small and easy to learn. They did not want the complexity of the Standard Template Library (or STL) of C++, but they wanted the benefit of generic algorithms that STL pioneered. They wanted the legacy classes to fit into the new framework. As all designers of collection libraries do, they had to make some hard choices, and they came up with a number of idiosyncratic design decisions along the way. In this section, we will explore the basic design of the Java collections framework, show you how to put it to work, and explain the reasoning behind some of the more controversial features.

Separating Collection Interfaces and Implementation

As is common for modern data structure libraries, the Java collection library separates interfaces and implementations. Let us look at that separation with a familiar data structure, the queue. The Java library does not supply a queue, but it is nevertheless a good example to introduce the basic concepts.



NOTE: If you need a queue, you can simply use the LinkedList class that we discuss later in this chapter.

A queue interface specifies that you can add elements at the tail end of the queue, remove them at the head, and find out how many elements are in the queue. You use a queue when you need to collect objects and retrieve them in a "first in, first out" fashion (see Figure 2-1).

Figure 2-1: A queue

If there was a queue interface in the collections library, it might look like this:

interface Queue
{  void add(Object obj);
   Object remove();
   int size();
}
The interface tells you nothing about how the queue is implemented. There are two common implementations of a queue, one that uses a "circular array" and one that uses a linked list (see Figure 2-2).


Figure 2-2: Queue implementations

Each implementation can be expressed by a class that realizes the Queue interface:

class CircularArrayQueue 
             implements Queue
{  CircularArrayQueue(
                 int capacity) { . . . }
   public void add(Object obj) { . . . }
   public Object remove() { . . . }
   public int size() { . . . }
   private Object[] elements;
   private int head;
   private int tail;
}

class LinkedListQueue implements Queue
{  LinkedListQueue() { . . . }
   public void add(Object obj) { . . . }
   public Object remove() { . . . }
   public int size() { . . . }

   private Link head;
   private Link tail;
} 
When you use a queue in your program, you don't need to know which implementation is actually used once the collection has been constructed. Therefore, it makes sense to use the concrete class (such as CircularArrayQueue) only when you construct the collection object. Use the interface type to hold the collection reference.
Queue expressLane = 
        new CircularArrayQueue(100);
expressLane.add(new Customer("Harry"));
This approach makes it easy to change your mind and use a different implementation. You only need to change your program in one place--the constructor. If you decide that a LinkedListQueue is a better choice after all, your code becomes
Queue expressLane = 
   new LinkedListQueue();
expressLane.add(
  new Customer("Harry"));
Why would you choose one implementation over another? The interface says nothing about the efficiency of the implementation. A circular array is somewhat more efficient than a linked list, so it is generally preferable. However, as usual, there is a price to pay. The circular array is a bounded collection--it has a finite capacity. If you don't have an upper limit on the number of objects that your program will collect, you may be better off with a linked list implementation after all.

This example illustrates another issue for the designer of a collection class library. Strictly speaking, in a bounded collection, the interface of the add method should indicate that the method can fail:

class CircularArrayQueue
{  public void add(Object obj)
  throws CollectionFullException
   . . .
}  
That's a problem--now the CircularArrayQueue class can't implement the Queue interface since you can't add exception specifiers when overriding a method. Should one have two interfaces, BoundedQueue and Queue? Or should the add method throw an unchecked exception? There are advantages and disadvantages to both approaches. It is these kinds of issues that make it genuinely hard to design a logically coherent collection class library.

As we already mentioned, the Java library has no separate class for queues. We just used this example to illustrate the difference between interface and implementation since a queue has a simple interface and two well-known distinct implementations. In the next section, you will see how the Java library classifies the collections that it supports.

TOP | NEXT

Print Button
[ This page was updated: 27-Sep-2000 ]
Products & APIs | Developer Connection | Docs & Training | Online Support
Community Discussion | Industry News | Solutions Marketplace | Case Studies
Glossary | Feedback | A-Z Index
For more information on Java technology
and other software from Sun Microsystems, call:
(800) 786-7638
Outside the U.S. and Canada, dial your country's AT&T Direct Access Number first.
Sun Microsystems, Inc.
Copyright © 1995-2000 Sun Microsystems, Inc.
All Rights Reserved. Terms of Use. Privacy Policy.