Java 5 Data Structures

public interface Collection<E>

The root interface in the collection hierarchy. A collection represents a group of objects, known as its elements. Some collections allow duplicate elements and others do not. Some are ordered and others unordered.

The JDK does not provide any direct implementations of this interface: it provides implementations of more specific subinterfaces like Set and List. This interface is typically used to pass collections around and manipulate them where maximum generality is desired.

All general-purpose Collection implementation classes (which typically implement Collection indirectly through one of its subinterfaces) should provide two "standard" constructors: a void (no arguments) constructor, which creates an empty collection, and a constructor with a single argument of type Collection, which creates a new collection with the same elements as its argument. In effect, the latter constructor allows the user to copy any collection, producing an equivalent collection of the desired implementation type. There is no way to enforce this convention (as interfaces cannot contain constructors) but all of the general-purpose Collection implementations in the JDK comply.

Method Summary
Basic Operations

Bulk Operations

Array Operations

Iterator<E>

public interface Iterator<E>

An iterator over a collection. Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined
semantics.

Method Summary

public interface Set<E> extends Collection<E>

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.

The additional stipulation on constructors is, not surprisingly, that all constructors must create a set that contains no duplicate elements (as defined above).

Method Summary ( Collection operations with set rules)


public interface List<E> extends Collection<E>

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each
element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the
list.

Unlike sets, lists typically allow duplicate elements. More formally, lists typically allow pairs of elements e1 and e2 such
that e1.equals(e2), and they typically allow multiple null elements if they allow null elements at all.

The List interface places additional stipulations, beyond those specified in the Collection interface, on the contracts of
the iterator, add, remove, equals, and hashCode methods. Declarations for other inherited methods are also included
here for convenience.

The List interface provides four methods for positional (indexed) access to list elements. Lists (like Java arrays) are zero
based. Note that these operations may execute in time proportional to the index value for some implementations (the
LinkedList class, for example). Thus, iterating over the elements in a list is typically preferable to indexing through it if the
caller does not know the implementation.

The List interface provides a special iterator, called a ListIterator, that allows element insertion and replacement, and
bidirectional access in addition to the normal operations that the Iterator interface provides. A method is provided to
obtain a list iterator that starts at a specified position in the list.

The List interface provides two methods to search for a specified object. From a performance standpoint, these methods
should be used with caution. In many implementations they will perform costly linear searches.

The List interface provides two methods to efficiently insert and remove multiple elements at an arbitrary point in the list.

Method Summary ( in addition to Collection)

public interface ListIterator<E> extends Iterator<E>

An iterator for lists that allows the programmer to traverse the list in either direction and modify the list during iteration.

 Method Summary


public interface Map<K,V>

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

The Map interface provides three collection views, which allow a map's contents to be viewed as a set of keys, collection of values, or set of key-value mappings. The order of a map is defined as the order in which the iterators on the map's collection views return their elements. Some map implementations, like the TreeMap class, make specific guarantees as to their order; others, like the HashMap class, do not.

All general-purpose map implementation classes should provide two "standard" constructors: a void (no arguments) constructor which creates an empty map, and a constructor with a single argument of type Map, which creates a new map with the same key-value mappings as its argument. In effect, the latter constructor allows the user to copy any map, producing an equivalent map of the desired class.

Inner Class Summary


Method Summary

Basic Operations

Set Operations

Other Operations

public static interface Map.Entry<K,V>

A map entry (key-value pair). The Map.entrySet method returns a collection-view of the map, whose elements are of this class. The only way to obtain a reference to a map entry is from the iterator of this collection-view. These Map.Entry objects are valid only for the duration of the iteration; more formally, the behavior of a map entry is undefined if the backing map has been modified after the entry was returned by the iterator, except through the iterator's own remove operation, or through the setValue operation on a map entry returned by the iterator.

Method Summary


public interface SortedSet<E> extends Set<E>

A set that further guarantees that its iterator will traverse the set in ascending element order, sorted according to the
natural ordering of its elements (see Comparable), or by a Comparator provided at sorted set creation time. Several
additional operations are provided to take advantage of the ordering. (This interface is the set analogue of SortedMap.)

All elements inserted into an sorted set must implement the Comparable interface (or be accepted by the specified
Comparator). Furthermore, all such elements must be mutually comparable: e1.compareTo(e2) (or
comparator.compare(e1, e2)) must not throw a ClassCastException for any elements e1 and e2 in the sorted
set. Attempts to violate this restriction will cause the offending method or constructor invocation to throw a
ClassCastException.

All general-purpose sorted set implementation classes should provide four "standard" constructors: 1) A void (no
arguments) constructor, which creates an empty sorted set sorted according to the natural order of its elements. 2) A
constructor with a single argument of type Comparator, which creates an empty sorted set sorted according to the
specified comparator. 3) A constructor with a single argument of type Collection, which creates a new sorted set with
the same elements as its argument, sorted according to the elements' natural ordering. 4) A constructor with a single
argument of type SortedSet, which creates a new sorted set with the same elements and the same ordering as the input
sorted set.

Method Summary


public interface SortedMap<K,V> extends Map<K,V>

A map that further guarantees that it will be in ascending key order, sorted according to the natural ordering of its keys
(see the Comparable interface), or by a comparator provided at sorted map creation time. This order is reflected when
iterating over the sorted map's collection views (returned by the entrySet, keySet and values methods). Several
additional operations are provided to take advantage of the ordering. (This interface is the map analogue of the
SortedSet interface.)

All keys inserted into a sorted map must implement the Comparable interface (or be accepted by the specified
comparator). Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) (or
comparator.compare(k1, k2)) must not throw a ClassCastException for any elements k1 and k2 in the sorted
map. Attempts to violate this restriction will cause the offending method or constructor invocation to throw a
ClassCastException.

All general-purpose sorted map implementation classes should provide four "standard" constructors: 1) A void (no
arguments) constructor, which creates an empty sorted map sorted according to the natural order of its keys. 2) A
constructor with a single argument of type Comparator, which creates an empty sorted map sorted according to the
specified comparator. 3) A constructor with a single argument of type Map, which creates a new map with the same
key-value mappings as its argument, sorted according to the keys' natural ordering. 4) A constructor with a single
argument of type sorted map, which creates a new sorted map with the same key-value mappings and the same ordering
as the input sorted map.

Method Summary


public interface Comparator<E>

A comparison function, which imposes a total ordering on some collection of objects. Comparators can be passed to a sort method (such as Collections.sort) to allow precise control over the sort order. Comparators can also be used to control the order of certain data structures (such as TreeSet or TreeMap).

It follows immediately from the contract for compare that the quotient is an equivalence relation on S, and that the natural ordering is a total order on S. When we say that the ordering imposed by c on S is consistent with equals, we mean that the quotient for the natural ordering is the equivalence relation defined by the objects' equals(Object) method(s):

{(x, y) such that x.equals((Object)y)}.

Method Summary

public interface Comparable<E>

This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method.

Lists (and arrays) of objects that implement this interface can be sorted automatically by Collections.sort (and Arrays.sort). Objects that implement this interface can be used as keys in a sorted map or elements in a sorted set, without the need to specify a comparator.

Virtually all Java core classes that implement comparable have natural orderings that are consistent with equals. One exception is java.math.BigDecimal, whose natural ordering equates BigDecimals with equal values and different precisions (such as 4.0 and 4.00).

Method Summary