The Collection Classes - java.util

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. As a general rule, the collection classes are not synchronized, but as you will see later in this chapter, it is possible to obtain synchronized versions.

The core collection classes are summarized in the following table:

Class : Description

AbstractCollection : Implements most of the Collection interface.

AbstractList : Extends AbstractCollection and implements most of the List interface.

AbstractQueue : Extends AbstractCollection and implements parts of the Queue 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.

ArrayDeque : Implements a dynamic double-ended queue by extending AbstractCollection and implementing the Deque interface.

AbstractSet : Extends AbstractCollection and implements most of the Set interface.

EnumSet : Extends AbstractSet for use with enum elements.

HashSet : Extends AbstractSet for use with a hash table.

LinkedHashSet : Extends HashSet to allow insertion-order iterations.

PriorityQueue : Extends AbstractQueue to support a priority-based queue.

TreeSet : Implements a set stored in a tree. Extends AbstractSet.

The ArrayList Class

The ArrayList class extends AbstractList and implements the List interface. ArrayList is a generic class that has this declaration:

class ArrayList<E>

Here, E specifies the type of objects that the list will hold.

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 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 can be shrunk.

ArrayList has the constructors shown here:

ArrayList( )

ArrayList(Collection<? extends E> 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 for objects of type String, and then several strings 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<String> al = new ArrayList<String>();

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( ) is sufficient.

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 than 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 specifies the new minimum capacity of the collection.

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. You can do this by calling toArray( ), which is defined by Collection. 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 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 explained earlier, there are two versions of toArray( ), which are shown again here for your convenience:

object[ ] toArray( )

<T> T[ ] toArray(T array[ ])

The first returns an array of Object. The second returns an array of elements that have the same type as T. Normally, the second form is more convenient because it returns the proper type of array. The following program demonstrates its use:

// Convert an ArrayList into an array.

import java.util.*;

class ArrayListToArray {

public static void main(String args[]) { // Create an array list.

ArrayList<Integer> al = new ArrayList<Integer>();

// Add elements to the array list.

al.add(1);

al.add(2);

al.add(3);

al.add(4);

System.out.println("Contents of al: " + al);

// Get the array.

Integer ia[] = new Integer[al.size()]; ia = al.toArray(ia);

int sum = 0;

// Sum the array.

for(int i : ia) sum += i;

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. Next, toArray( ) is called and it obtains an array of Integers. Then, the contents of that array are summed by use of a for-each style for loop.

There is something else of interest in this program. As you know, collections can store only references, not values of primitive types. However, autoboxing makes it possible

to pass values of type int to add( ) without having to manually wrap them within an Integer, as the program shows. Autoboxing causes them to be automatically wrapped. In this way, autoboxing significantly improves the ease with which collections can be used to store primitive values.

The LinkedList Class

The LinkedList class extends AbstractSequentialList and implements the List, Deque, and

Queue interfaces. It provides a linked-list data structure. LinkedList is a generic class that has this declaration:

class LinkedList<E>

Here, E specifies the type of objects that the list will hold. LinkedList has the two constructors shown here:

LinkedList( ) LinkedList(Collection<? extends E> 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.

Because LinkedList implements the Deque interface, you have access to the methods defined by Deque. For example, to add elements to the start of a list, you can use addFirst( ) or offerFirst( ). To add elements to the end of the list, use addLast( ) or offerLast( ). To obtain the first element, you can use getFirst( ) or peekFirst( ). To obtain the last element, use getLast( ) or peekLast( ). To remove the first element, use removeFirst( ) or pollFirst( ). To remove the last element, use removeLast( ) or pollLast( ).

The following program illustrates LinkedList:

// Demonstrate LinkedList.

import java.util.*;

class LinkedListDemo {

public static void main(String args[]) { // Create a linked list.

LinkedList<String> ll = new LinkedList<String>();

// 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);

// Remove first and last elements.

ll.removeFirst(); ll.removeLast();

System.out.println("ll after deleting first and last: " ll);

     //Get and set a value.

String val = 11.get(2); ll.set(2, 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(E) append items to the end of the list, as do calls to addLast( ). To insert items at a specific location, use the add(int, E) 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. HashSet is a generic class that has this declaration:

class HashSet<E>

Here, E specifies the type of objects that the set will hold.

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 add( ), contains( ), remove( ), and size( ) to remain constant even for large sets.

The following constructors are defined:

HashSet( )

HashSet(Collection<? extends E> 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 default capacity is 16.) 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.

It is important to note that HashSet 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<String> hs = new HashSet<String>();

// Add elements to the hash set.

hs.add("Beta");

hs.add("Alpha");

hs.add("Eta");

hs.add("Gamma");

hs.add("Epsilon");

hs.add("Omega");

System.out.println(hs);

}

}

The following is the output from this program:

[Gamma, Eta, Alpha, Epsilon, Omega, Beta]

As explained, the elements are not stored in sorted order, and the precise output may vary.

The LinkedHashSet Class

The LinkedHashSet class extends HashSet and adds no members of its own. It is a generic class that has this declaration:

class LinkedHashSet<E>

Here, E specifies the type of objects that the set will hold. Its constructors parallel those in HashSet.

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

[Beta, Alpha, Eta, Gamma, Epsilon, Omega]

which is the order in which the elements were inserted.

The TreeSet Class

TreeSet extends AbstractSet and implements the NavigableSet interface. It creates a collection 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.

TreeSet is a generic class that has this declaration: class TreeSet<E>

Here, E specifies the type of objects that the set will hold. TreeSet has the following constructors:

TreeSet( )

TreeSet(Collection<? extends E> c) TreeSet(Comparator<? super E> comp) TreeSet(SortedSet<E> 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<String> ts = new TreeSet<String>();

// 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.

Because TreeSet implements the NavigableSet interface, you can use the methods defined by NavigableSet to retrieve elements of a TreeSet. For example, assuming the preceding program, the following statement uses subSet( ) to obtain a subset of ts that contains the elements between C (inclusive) and F (exclusive). It then displays the resulting set.

System.out.println(ts.subSet("C", "F"));

The output from this statement is shown here:

[C, D, E]

You might want to experiment with the other methods defined by NavigableSet.

The PriorityQueue Class

PriorityQueue extends AbstractQueue and implements the Queue interface. It creates a queue that is prioritized based on the queue’s comparator. PriorityQueue is a generic class that has this declaration:

class PriorityQueue<E>

Here, E specifies the type of objects stored in the queue. PriorityQueues are dynamic, growing as necessary.

PriorityQueue defines the six constructors shown here:

PriorityQueue( ) PriorityQueue(int capacity)

PriorityQueue(Comparator<? super E> comp) (Added by JDK 8.) PriorityQueue(int capacity, Comparator<? super E> comp) PriorityQueue(Collection<? extends E> c) PriorityQueue(PriorityQueue<? extends E> c) PriorityQueue(SortedSet<? extends E> c)

The first constructor builds an empty queue. Its starting capacity is 11. The second constructor builds a queue that has the specified initial capacity. The third constructor specifies a comparator, and the fourth builds a queue with the specified capacity and comparator. The last three constructors create queues that are initialized with the elements of the collection passed in c. In all cases, the capacity grows automatically as elements are added.

If no comparator is specified when a PriorityQueue is constructed, then the default comparator for the type of data stored in the queue is used. The default comparator will order the queue in ascending order. Thus, the head of the queue will be the smallest value. However, by providing a custom comparator, you can specify a different ordering scheme. For example, when storing items that include a time stamp, you could prioritize the queue such that the oldest items are first in the queue.

You can obtain a reference to the comparator used by a PriorityQueue by calling its comparator( ) method, shown here:

Comparator<? super E> comparator( )

It returns the comparator. If natural ordering is used for the invoking queue, null is returned.

One word of caution: Although you can iterate through a PriorityQueue using an iterator, the order of that iteration is undefined. To properly use a PriorityQueue, you must call methods such as offer( ) and poll( ), which are defined by the Queue interface.

The ArrayDeque Class

The ArrayDeque class extends AbstractCollection and implements the Deque interface. It adds no methods of its own. ArrayDeque creates a dynamic array and has no capacity restrictions. (The Deque interface supports implementations that restrict capacity, but does not require such restrictions.) ArrayDeque is a generic class that has this declaration:

class ArrayDeque<E>

Here, E specifies the type of objects stored in the collection. ArrayDeque defines the following constructors:

ArrayDeque( ) ArrayDeque(int size)

ArrayDeque(Collection<? extends E> c)

The first constructor builds an empty deque. Its starting capacity is 16. The second constructor builds a deque that has the specified initial capacity. The third constructor creates a deque that is initialized with the elements of the collection passed in c. In all cases, the capacity grows as needed to handle the elements added to the deque.

The following program demonstrates ArrayDeque by using it to create a stack:

// Demonstrate ArrayDeque.

import java.util.*;

class ArrayDequeDemo {

public static void main(String args[]) { // Create an array deque.

ArrayDeque<String> adq = new ArrayDeque<String>();

// Use an ArrayDeque like a stack.

adq.push("A");

adq.push("B");

adq.push("D");

adq.push("E");

adq.push("F");

System.out.print("Popping the stack: ");

while(adq.peek() != null) System.out.print(adq.pop() + " ");

System.out.println();

}

}

The output is shown here:

Popping the stack: F E D B A

The EnumSet Class

EnumSet extends AbstractSet and implements Set. It is specifically for use with elements of an enum type. It is a generic class that has this declaration:

class EnumSet<E extends Enum<E>>

Here, E specifies the elements. Notice that E must extend Enum<E>, which enforces the requirement that the elements must be of the specified enum type.

EnumSet defines no constructors. Instead, it uses the factory methods shown in Table 18-7 to create objects. All methods can throw NullPointerException. The copyOf( ) and range( ) methods can also throw IllegalArgumentException. Notice that the of( ) method is overloaded a number of times. This is in the interest of efficiency. Passing a known number of arguments can be faster than using a vararg parameter when the number of arguments is small.