With Java 2, developers have a good suite of data structure implementations and interfaces for building classes.
A common need for all but the most trivial of Java applications is the ability to gather together a collection of object references. Java has always had minimal support for object collections, with the Vector, Stack and Hashtable classes. There is also, of course, the handy array of objects (though the array is fixed in size). The Java 2 platform takes this one step further, by providing a common framework for representing object collections, as well as some concrete implementations of data structures. The Java collections framework is a set of interfaces and classes that provide an easy way to store collections of objects.
Why introduce a new API just for data structures?
The data structures provided by earlier editions of the Java platform are primitive tools for serious application development. For example, adding and deleting from an array requires reshuffling, and extra code has to be added for sorting. While a class like Vector helps with resizing, it still doesn't guarantee order. That means extra work for developers, every time they want to use it. Wouldn't it be nice if you didn't care about the implementation of the data structure, and could just use it?
That's what the collections framework provides. It introduces a variety of interfaces and classes, which belong to two distinct groups (Collection and Map). Collections are for storing a sequence of object references, whereas Maps provide a key-value pair mapping to objects. Together with some support classes, the collection framework offers developers the following benefits:
- A wider variety of data structures, for those who don't want to write their own
- A standard framework for developing new data structures that are interoperable
- Easy-to-use interfaces, with implementations that can be transparently substituted to improve application performance.
This new framework adds a new degree of maturity to the Java programming language, by providing a more-useful data structure API consistent with the flexibility and versatility of other parts of the Java API.
Introducing the interface
The interface provides a base from which other collection interfaces are extended. It declares several methods, which provide the means by which object references can be added to a collection, searched, accessed, and removed.
| Collection Method | Purpose |
add (Object) | Adds the specified object |
addAll (Collection) | Adds all of the objects contained in the specified collection |
clear () | Dumps all stored objects |
boolean contains (Object o) | Checks for presence of specified object |
boolean containsAll (Collection) | Checks for presence of all objects contained in the specified collection |
boolean isEmpty () | Checks for an empty collection |
Iterator iterator () | Returns an - a sequence of data elements |
remove (Object o) | Removes the specified object |
removeAll (Collection) | Removes all objects contained in the specified collection |
retainAll (Collection) | Removes all objects not contained in the specified collection |
int size() | Returns the number of elements in the collection |
Object[] toArray () | Converts the collection to an array |
The interface offers a standard set of methods, regardless of the actual type of collection that is used. Indeed, in many situations the actual data structure used will be irrelevant to the code, and could be easily substituted (perhaps for performance reasons). By referring to the data structure as a instance, and not its class, you can substitute it at a later date without requiring any further code changes.
Collection c;
c = new ArrayList(); OR
c = new LinkedList();
// Add elements to the collection
c.add ( ... );
The collections framework also makes an important distinction between types of collections, by offering a further two new interfaces. A is a collection that accepts only one copy of an object, whereas a can accept multiple copies. Figure One shows the relationship between the and interfaces.
Figure 1. Collection interfaces.
More often than not, programmers will be using implementations of the interface, which corresponds to the old class. In fact, the class has been modified to make it compatible with the new interface. Also, there is another interface ( ) which imposes a further condition that a be sorted. When writing data structure implementations, these interfaces will be very useful (and corresponding , , and templates are also provided). However, in normal circumstances, developers will choose existing implementations provided as part of the collections framework.
Introducing the interface
The interface declares methods for classes that implement a mapping between keys and values. While part of the collections framework, it does not subclass the interface — it is for representing mappings not aggregations. implementations are subject to a few restrictions:
If these restrictions sound extreme, remember that multiple values can be achieved by storing a rather than an . Maps are extremely useful, and even before their introduction in JDK 1.2, were quite commonplace. The class is a that most developers will be familiar with, and it has been modified in JDK 1.2 to implement the interface. The following table shows the most useful methods of the interface.
| Map Method | Purpose |
clear () | Dumps all stored objects |
boolean containsKey (Object) | Checks for the presence of a key |
boolean containsValue (Object) | Checks for the presence of a value |
Set entrySet () | Returns a collection of key-value mappings represented as instances |
boolean equals (Object) | Checks for equality between two maps |
Object get (Object) | Returns the value associates with the specified key, and if no such mapping exists, or if the key is mapped to the value |
boolean isEmpty () | Checks for an empty map |
Set keySet() | Returns a collection of all keys |
Object put (Object key, Object value) | Maps the key to the specified value, overwriting any previous mapping for that key. Returns the previous mapping (which may be ) |
Object putAll (Map) | Puts all key-value pair mappings in the specified map into the current map. Similiar to the Collection.addAll
(Collection) |
method |
remove (Object o) | Removes specified object |
int size() | Returns number of elements in collection |
As in the interface, the interface provides a standard set of methods that can be used with Maps. By maintaining reference to the interface, and not implementations, it is easy to later substitute an alternate data structure. Also, the interface is similar to the older JDK 1.0 abstract class. When designing new implementations, the interface should be used in place of the class. This means implementing the interface, instead of extending the class.
// Old way of creating a map-like data structure public class FileBasedHashTable extends java.util.Dictionary
// New way of creating a map-like data structure public class FileBasedHashtable implements java.util.Map
There is also a interface, which provides a method for sorting the key mappings. When using a , all keys must implement the new interface, which is required to allow comparison during the sorting process. The good news is that most of the wrapper objects for primitive data-types ( Byte, Character, Double, Float,
String, |
, etc.) implement the interface, but when using custom-designed classes as keys, you will need to implement , or avoid using a .
Summary
With the new collections framework included in the Java 2 platform, developers finally have at their fingertips a good suite of data structure implementations and interfaces from which further classes can be built. In the next part of our lesson (The Java Collections Framework: Implementations), we'll examine the new classes that form the collections framework, such as linked lists and trees. We'll also look at how you can safely use collections in a multithreaded environment and how to convert from a to an array — and back again.
Further reading
About the author
David Reilly is a software engineer and freelance technical writer living in Australia. A Sun Certified Java 1.1 Programmer, his research interests include the Java programming language, as well as networking and distributed systems. He can be reached via e-mail at java@davidreilly.com, or via his personal Web site.