![]() ![]() ![]() |
|
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Book Excerpt Index
Core Java 2, Volume IIby Cay S. Horstmann and Gary CornellChapter 2: Collections(December 1999)
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
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 InterfacesBefore 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).
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.
|