The collections framework defines several interfaces. This section provides an overview of
each interface. Beginning with the collection interfaces is necessary because they determine
the fundamental nature of the collection classes. Put differently, the concrete classes simply
provide different implementations of the standard interfaces. The interfaces that provide
collections are summarized in the following table:
Interface |
Description |
| Collection |
Enables you to work with groups of objects; it is at the top of the
collections hierarchy |
| List |
Extends Collection to handle sequences (lists of objects) |
| Set |
Extends Collection to handle sets, which must contain unique elements |
| SortedSet |
Extends Set to handle sorted sets |
The Collection Interface
The Collection interface is the foundation upon which the collections framework is
built. It declares the core methods that all collections will haveObjects are added to a collection by calling add( ). Notice that add( ) takes an
argument of type Object. Because Object is a superclass of all classes, any type of
object may be stored in a collection. However, primitive types may not. For example, a
collection cannot directly store values of type int, char, double, and so forth. Of course,
if you want to store such objects, you can also use one of the primitivee wrapper classes
You can add the entire contents of one collection to another by
calling addAll( ).
You can remove an object by using remove( ). To remove a group of objects, call
removeAll( ). You can remove all elements except those of a specified group by calling
retainAll( ). To empty a collection, call clear( ).
You can determine whether a collection contains a specific object by calling
contains( ). To determine whether one collection contains all the members of another, call
containsAll( ). You can determine when a collection is empty by calling isEmpty( ). The
number of elements currently held in a collection can be determined by calling size( ).
The toArray( ) method returns an array that contains the elements stored in the
invoking collection. This method is more important than it might at first seem.
Methods defined bt Collection interface
List Interface
The List interface extends Collection and declares the behavior of a collection that
stores a sequence of elements. Elements can be inserted or accessed by their position
in the list, using a zero-based index. A list may contain duplicate elements.
In addition to the methods defined by Collection, List defines some of its own,
which are summarized in Table . Note again that several of these methods will
throw an if the collection cannot be modified, and
a ClassCastException is generated when one object is incompatible with another,
such as when an attempt is made to add an incompatible object to a collection.
To the versions of add( ) and addAll( ) defined by Collection, List adds the methods
add(int, Object) and addAll(int, Collection). These methods insert elements at the
specified index. Also, the semantics of add(Object) and addAll(Collection) defined by
Collection are changed by List so that they add elements to the end of the list.
To obtain the object stored at a specific location, call get( ) with the index of the
object. To assign a value to an element in the list, call set( ), specifying the index of the
object to be changed. To find the index of an object, use indexOf( ) or lastIndexOf( ).
Methods in List Interface
The Set Interface
The Set interface defines a set. It extends Collection and declares the behavior of a
collection that does not allow duplicate elements. Therefore, the add( ) method returns
false if an attempt is made to add duplicate elements to a set. It does not define any
additional methods of its own.
The SortedSet Interface
The SortedSet interface extends Set and declares the behavior of a set sorted in ascending
order. In addition to those methods defined by Set, the SortedSet interface declares the
methods summarized in Table Several methods throw a NoSuchElementException
when no items are contained in the invoking set. A ClassCastException is thrown when an
object is incompatible with the elements in a set. A NullPointerException is thrown if an
attempt is made to use a null object and null is not allowed in the set.
SortedSet defines several methods that make set processing more convenient. To
obtain the first object in the set, call first( ). To get the last element, use last( ). You can
obtain a subset of a sorted set by calling subSet( ), specifying the first and last object in
the set. If you need the subset that starts with the first element in the set, use headSet( ). If you want the subset that ends the set, use tailSet( ).
Methods defined by Sorted Interfece
Accessing a Collection via an Iterator
Often, you will want to cycle through the elements in a collection. For example, you
might want to display each element. By far, the easiest way to do this is to employ an
iterator, an object that implements either the Iterator or the ListIterator interface.
Iterator enables you to cycle through a collection, obtaining or removing elements.
ListIterator extends Iterator to allow bidirectional traversal of a list, and the
modification of elements. The Iterator interface declares the methods shown in
Table.
Example:-
// Demonstrate iterators.
import java.util.*;
class IteratorDemo {
public static void main(String args[]) {
// create an array list
ArrayList al = new ArrayList();
// add elements to the array list
al.add("C");
al.add("A");
al.add("E");
al.add("B");
al.add("D");
al.add("F");
// use iterator to display contents of al
System.out.print("Original contents of al: ");
Iterator itr = al.iterator();
while(itr.hasNext()) {
Object element = itr.next();
System.out.print(element + " ");
}
System.out.println();
// modify objects being iterated
ListIterator litr = al.listIterator();
while(litr.hasNext()) {
Object element = litr.next();
litr.set(element + "+");
}
System.out.print("Modified contents of al: ");
itr = al.iterator();
while(itr.hasNext()) {
Object element = itr.next();
System.out.print(element + " ");
}
System.out.println();
// now, display the list backwards
System.out.print("Modified list backwards: ");
while(litr.hasPrevious()) {
Object element = litr.previous();
System.out.print(element + " ");
}
System.out.println();
}
}
The output is shown here:
Original contents of al: C A E B D F
Modified contents of al: C+ A+ E+ B+ D+ F+
Modified list backwards: F+ D+ B+ E+ A+ C+
Classes implementing collection interfaces
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.
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]
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]
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.
Vector
Vector implements a dynamic array. It is similar to ArrayList, but with two differences:
Vector is synchronized, and it contains many legacy methods that are not part of
the collections framework. With the release of Java 2, Vector was reengineered to
extend AbstractList and implement the List interface, so it now is fully compatible
with collections.
Here are the Vector constructors:
Vector( )
Vector(int size)
Vector(int size, int incr)
Vector(Collection c)
The first form creates a default vector, which has an initial size of 10. The second form
creates a vector whose initial capacity is specified by size. The third form creates a
vector whose initial capacity is specified by size and whose increment is specified by
incr. The increment specifies the number of elements to allocate each time that a vector
is resized upward. The fourth form creates a vector that contains the elements of
collection c.
// Demonstrate various Vector operations.
import java.util.*;
class VectorDemo {
public static void main(String args[]) {
// initial size is 3, increment is 2
Vector v = new Vector(3, 2);
System.out.println("Initial size: " + v.size());
System.out.println("Initial capacity: " +
v.capacity());
v.addElement(new Integer(1));
v.addElement(new Integer(2));
v.addElement(new Integer(3));
v.addElement(new Integer(4));
System.out.println("Capacity after four additions: " +
v.capacity());
v.addElement(new Double(5.45));
System.out.println("Current capacity: " +
v.capacity());
v.addElement(new Double(6.08));
v.addElement(new Integer(7));
System.out.println("Current capacity: " +
v.capacity());
v.addElement(new Float(9.4));
v.addElement(new Integer(10));
System.out.println("Current capacity: " +
v.capacity());
v.addElement(new Integer(11));
v.addElement(new Integer(12));
System.out.println("First element: " +
(Integer)v.firstElement());
System.out.println("Last element: " +
(Integer)v.lastElement());
if(v.contains(new Integer(3)))
System.out.println("Vector contains 3.");
// enumerate the elements in the vector.
Enumeration vEnum = v.elements();
System.out.println("\nElements in vector:");
while(vEnum.hasMoreElements())
System.out.print(vEnum.nextElement() + " ");
System.out.println();
}
}
