The Collection Classes
Now that you are familiar with the collection interfaces, you are ready to examine the standard classes that implement them. Some of the classes provide full implementations that can be used as-is. Others are abstract, providing skeletal implementations that are used as starting points for creating concrete collections. None of the collection classes are synchronized, but as you will see later in this chapter, it is possible to obtain synchronized versions.
The standard collection classes are summarized in the following table:
AbstractCollection: Implements most of the Collection interface.
AbstractList: Extends AbstractCollection and implements most of the List interface.
AbstractSequentialList: Extends AbstractList for use by a collection that uses sequential rather than random access of its elements.
LinkedList: Implements a linked list by extending AbstractSequentialList.
ArrayList: Implements a dynamic array by extending AbstractList.
AbstractSet: Extends AbstractCollection and implements most of the Set interface.
HashSet: Extends AbstractSet for use with a hash table.
LinkedHashSet: Extends HashSet to allow insertion-order iterations.
TreeSet: Implements a set stored in a tree. Extends AbstractSet.
In addition to the collection classes, several legacy classes, such as Vector, Stack, and Hashtable, have been reengineered to support collections. These are examined later in this chapter.
The following sections examine the concrete collection classes and illustrate their use.
The ArrayList Class
The ArrayList class extends AbstractList and implements the List interface. ArrayList supports dynamic arrays that can grow as needed. In Java, standard arrays are of a fixed length. After arrays are created, they cannot grow or shrink, which means that you must know in advance how many elements an array will hold. But, sometimes, you may not know until run time precisely how large of an array you need. To handle this situation, the collections framework defines ArrayList. In essence, an ArrayList is a variable-length array of object references. That is, an ArrayList can dynamically increase or decrease in size. Array lists are created with an initial size. When this size is exceeded, the collection is automatically enlarged. When objects are removed, the array may be shrunk.
Dynamic arrays are also supported by the legacy class Vector, which is described later in this chapter.
ArrayList has the constructors shown here:
ArrayList( )
ArrayList(Collection c)
ArrayList(int capacity)
The first constructor builds an empty array list. The second constructor builds an array list that is initialized with the elements of the collection c. The third constructor builds an array list that has the specified initial capacity. The capacity is the size of the underlying array that is used to store the elements. The capacity grows automatically as elements are added to an array list.
The following program shows a simple use of ArrayList. An array list is created, and then objects of type String are added to it. (Recall that a quoted string is translated into a String object.) The list is then displayed. Some of the elements are removed and the list is displayed again.
// Demonstrate ArrayList.
import java.util.*;
class ArrayListDemo {
public static void main(String args[]) {
// create an array list
ArrayList al = new ArrayList();
System.out.println("Initial size of al: " +
al.size());
// add elements to the array list
al.add("C");
al.add("A");
al.add("E");
al.add("B");
al.add("D");
al.add("F");
al.add(1, "A2");
System.out.println("Size of al after additions: " +
al.size());
// display the array list
System.out.println("Contents of al: " + al);
// Remove elements from the array list
al.remove("F");
al.remove(2);
System.out.println("Size of al after deletions: " +
al.size());
System.out.println("Contents of al: " + al);
}
}
The output from this program is shown here:
Initial size of al: 0
Size of al after additions: 7
Contents of al: [C, A2, A, E, B, D, F]
Size of al after deletions: 5
Contents of al: [C, A2, E, B, D]
Notice that a1 starts out empty and grows as elements are added to it. When elements are removed, its size is reduced.
In the preceding example, the contents of a collection are displayed using the default conversion provided by toString( ), which was inherited from AbstractCollection. Although it is sufficient for short, sample programs, you seldom use this method to display the contents of a real-world collection. Usually, you provide your own output routines. But, for the next few examples, the default output created by toString( ) will continue to be used.
Although the capacity of an ArrayList object increases automatically as objects are stored in it, you can increase the capacity of an ArrayList object manually by calling ensureCapacity( ). You might want to do this if you know in advance that you will be storing many more items in the collection that it can currently hold. By increasing its capacity once, at the start, you can prevent several reallocations later. Because reallocations are costly in terms of time, preventing unnecessary ones improves performance. The signature for ensureCapacity( ) is shown here:
void ensureCapacity(int cap)
Here, cap is the new capacity.
Conversely, if you want to reduce the size of the array that underlies an ArrayList object so that it is precisely as large as the number of items that it is currently holding, call trimToSize( ), shown here:
void trimToSize( )
Obtaining an Array from an ArrayList
When working with ArrayList, you will sometimes want to obtain an actual array that
contains the contents of the list. As explained earlier, you can do this by calling toArray( ).
Several reasons exist why you might want to convert a collection into an array such as:
- To obtain faster processing times for certain operations.
- To pass an array to a method that is not overloaded to accept a collection.
- To integrate your newer, collection-based code with legacy code that does not understand collections.
Whatever the reason, converting an ArrayList to an array is a trivial matter, as the following program shows:
// Convert an ArrayList into an array.
import java.util.*;
class ArrayListToArray {
public static void main(String args[]) {
// Create an array list
ArrayList al = new ArrayList();
// Add elements to the array list
al.add(new Integer(1));
al.add(new Integer(2));
al.add(new Integer(3));
al.add(new Integer(4));
System.out.println("Contents of al: " + al);
// get array
Object ia[] = al.toArray();
int sum = 0;
// sum the array
for(int i=0; i<ia.length; i++)
sum += ((Integer) ia[i]).intValue();
System.out.println("Sum is: " + sum);
}
}
The output from the program is shown here:
Contents of al: [1, 2, 3, 4]
Sum is: 10
The program begins by creating a collection of integers. As explained, you cannot store primitive types in a collection, so objects of type Integer are created and stored. Next, toArray( ) is called and it obtains an array of Objects. The contents of this array are cast to Integer, and then the values are summed.
The LinkedList Class
The LinkedList class extends AbstractSequentialList and implements the List interface. It provides a linked-list data structure. It has the two constructors, shown here:
LinkedList( )
LinkedList(Collection c)
The first constructor builds an empty linked list. The second constructor builds a linked list that is initialized with the elements of the collection c.
In addition to the methods that it inherits, the LinkedList class defines some useful methods of its own for manipulating and accessing lists. To add elements to the start of the list, use addFirst( ); to add elements to the end, use addLast( ). Their signatures are shown here:
void addFirst(Object obj)
void addLast(Object obj)
Here, obj is the item being added.
To obtain the first element, call getFirst( ). To retrieve the last element, call getLast( ). Their signatures are shown here:
Object getFirst( )
Object getLast( )
To remove the first element, use removeFirst( ); to remove the last element, call removeLast( ). They are shown here:
Object removeFirst( )
Object removeLast( )
The following program illustrates several of the methods supported by LinkedList:
// Demonstrate LinkedList.
import java.util.*;
class LinkedListDemo {
public static void main(String args[]) {
// create a linked list
LinkedList ll = new LinkedList();
// add elements to the linked list
ll.add("F");
ll.add("B");
ll.add("D");
ll.add("E");
ll.add("C");
ll.addLast("Z");
ll.addFirst("A");
ll.add(1, "A2");
System.out.println("Original contents of ll: " + ll);
// remove elements from the linked list
ll.remove("F");
ll.remove(2);
System.out.println("Contents of ll after deletion: "
+ ll);
// remove first and last elements
ll.removeFirst();
ll.removeLast();
System.out.println("ll after deleting first and last: "
+ ll);
// get and set a value
Object val = ll.get(2);
ll.set(2, (String) val + " Changed");
System.out.println("ll after change: " + ll);
}
}
The output from this program is shown here:
Original contents of ll: [A, A2, F, B, D, E, C, Z]
Contents of ll after deletion: [A, A2, D, E, C, Z]
ll after deleting first and last: [A2, D, E, C]
ll after change: [A2, D, E Changed, C]
Because LinkedList implements the List interface, calls to add(Object) append items to the end of the list, as does addLast( ). To insert items at a specific location, use the add(int, Object) form of add( ), as illustrated by the call to add(1, “A2”) in the example.
Notice how the third element in ll is changed by employing calls to get( ) and set( ). To obtain the current value of an element, pass get( ) the index at which the element is stored. To assign a new value to that index, pass set( ) the index and its new value.
The HashSet Class
HashSet extends AbstractSet and implements the Set interface. It creates a collection that uses a hash table for storage. As most readers likely know, a hash table stores information by using a mechanism called hashing. In hashing, the informational content of a key is used to determine a unique value, called its hash code. The hash code is then used as the index at which the data associated with the key is stored. The transformation of the key into its hash code is performed automatically—you never see the hash code itself. Also, your code can’t directly index the hash table. The advantage of hashing is that it allows the execution time of basic operations, such as add( ), contains( ), remove( ), and size( ), to remain constant even for large sets.
The following constructors are defined:
HashSet( )
HashSet(Collection c)
HashSet(int capacity)
HashSet(int capacity, float fillRatio)
The first form constructs a default hash set. The second form initializes the hash set by using the elements of c. The third form initializes the capacity of the hash set to capacity. The fourth form initializes both the capacity and the fill ratio (also called load capacity) of the hash set from its arguments. The fill ratio must be between 0.0 and 1.0, and it determines how full the hash set can be before it is resized upward. Specifically, when the number of elements is greater than the capacity of the hash set multiplied by its fill ratio, the hash set is expanded. For constructors that do not take a fill ratio, 0.75 is used.
HashSet does not define any additional methods beyond those provided by its superclasses and interfaces. Importantly, note that a hash set does not guarantee the order of its elements, because the process of hashing doesn’t usually lend itself to the creation of sorted sets. If you need sorted storage, then another collection, such as TreeSet, is a better choice. Here is an example that demonstrates HashSet:
// Demonstrate HashSet.
import java.util.*;
class HashSetDemo {
public static void main(String args[]) {
// create a hash set
HashSet hs = new HashSet();
// add elements to the hash set
hs.add("B");
hs.add("A");
hs.add("D");
hs.add("E");
hs.add("C");
hs.add("F");
System.out.println(hs);
}
}
The following is the output from this program:
[A, F, E, D, C, B]
As explained, the elements are not stored in sorted order, and the precise output may vary.
The LinkedHashSet Class
Java 2, version 1.4 adds the LinkedHashSet class. This class extends HashSet, but adds no members of its own. LinkedHashSet maintains a linked list of the entries in the set, in the order in which they were inserted. This allows insertion-order iteration over the set. That is, when cycling through a LinkedHashSet using an iterator, the elements will be returned in the order in which they were inserted. This is also the order in which they are contained in the string returned by toString( ) when called on a LinkedHashSet object. To see the effect of LinkedHashSet, try substituting LinkedHashSet For HashSet in the preceding program. The output will be
[B, A, D, E, C, F]
which is the order in which the elements were inserted.
The TreeSet Class
TreeSet provides an implementation of the Set interface that uses a tree for storage. Objects are stored in sorted, ascending order. Access and retrieval times are quite fast, which makes TreeSet an excellent choice when storing large amounts of sorted information that must be found quickly.
The following constructors are defined:
TreeSet( )
TreeSet(Collection c)
TreeSet(Comparator comp)
TreeSet(SortedSet ss)
The first form constructs an empty tree set that will be sorted in ascending order according to the natural order of its elements. The second form builds a tree set that contains the elements of c. The third form constructs an empty tree set that will be sorted according to the comparator specified by comp. (Comparators are described later in this chapter.) The fourth form builds a tree set that contains the elements of ss.
Here is an example that demonstrates a TreeSet:
// Demonstrate TreeSet.
import java.util.*;
class TreeSetDemo {
public static void main(String args[]) {
// Create a tree set
TreeSet ts = new TreeSet();
// Add elements to the tree set
ts.add("C");
ts.add("A");
ts.add("B");
ts.add("E");
ts.add("F");
ts.add("D");
System.out.println(ts);
}
}
The output from this program is shown here:
[A, B, C, D, E, F]
As explained, because TreeSet stores its elements in a tree, they are automatically arranged in sorted order, as the output confirms.
No comments:
Post a Comment