Java 2 Data Structures

public interface Collection

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

• int size() Returns the number of elements in this collection.
• boolean isEmpty() Returns true if this collection contains no elements.
• boolean contains(Object o) Returns true if this collection contains the specified element.
• boolean remove(Object o) Removes a single instance of the specified element from this collection, if it is present (optional operation).
• boolean add(Object o) Ensures that this collection contains the specified element (optional operation).

Bulk Operations

• boolean containsAll(Collection c) Returns true if this collection contains all of the elements in the specified collection.
• boolean addAll(Collection c) Adds all of the elements in the specified collection to this collection (optional operation).
• boolean removeAll(Collection c) Removes all this collection's elements that are also contained in the specified collection (optional operation).
• boolean retainAll(Collection c) Retains only the elements in this collection that are contained in the specified collection (optional operation).
• void clear() Removes all of the elements from this collection (optional operation).

Array Operations

• Object[] toArray() Returns an array containing all of the elements in this collection.
• Object[] toArray(Object[] a) Returns an array containing all of the elements in this collection whose runtime type is that of the specified array.

  Iterator

• Iterator iterator() Returns an iterator over the elements in this collection.

public interface Iterator

    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

• boolean hasNext()    Returns true if the iteration has more elements.
• Object   next()          Returns the next element in the interation.
•  void  remove()         Removes from the underlying collection the last element returned by the iterator (optional operation).

public interface Set extends Collection

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)

• boolean add(Object o)             Adds the specified element to this set if it is not already present (optional operation).
• boolean  addAll(Collection c)   Adds all of the elements in the specified collection to this set if they're not already present (optional operation).

public interface List extends Collection

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)

•  void  add(int index, Object element)   Inserts the specified element at the specified position in this list (optional operation).
• addAll(int index, Collection c)     Inserts all of the elements in the specified collection into this list at the specified position (optiona
• Object  get(int index)  Returns the element at the specified position in this list.
• int  indexOf(Object o)  Returns the index in this list of the first occurrence of the specified element, or -1 if this list does not contain this element.
•  int lastIndexOf(Object o) Returns the index in this list of the last occurrence of the specified element, or -1 if this list does not contain this element.
• ListIterator  listIterator()  Returns a list iterator of the elements in this list (in proper sequence).
•  ListIterator  listIterator(int index) Returns a list iterator of the elements in this list (in proper sequence), starting at the specified position  in this list.
• Object  set(int index, Object element)  Replaces the element at the specified position in this list with the specified element (optional operation).
• List  subList(int fromIndex, int toIndex) Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex,       exclusive.

public interface ListIterator extends Iterator

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

 Method Summary

• void add(Object o)        Inserts the specified element into the list (optional operation).
• boolean   hasNext()       Returns true if this list iterator has more elements when traversing the list in the forward direction.
• boolean  hasPrevious()   Returns true if this list iterator has more elements when traversing the list in the reverse direction.
• Object   next()               Returns the next element in the list.
• int   nextIndex()              Returns the index of the element that would be returned by a subsequent call to next.
• Object   previous()         Returns the previous element in the list.
• int  previousIndex()         Returns the index of the element that would be returned by a subsequent call to previous.
• void   remove()               Removes from the list the last element that was returned by next or previous (optional operation).
• void  set(Object o)         Replaces the last element returned by next or previous with the specified element (optional operation).

public interface Map

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

• static interface  Map.Entry       A map entry (key-value pair).

 Method Summary

    Basic Operations

• Object  get(Object key)                        Returns the value to which this map maps the specified key.
• Object  put(Object key, Object value)  Associates the specified value with the specified key in this map (optional operation).
• Object  remove(Object key)                 Removes the mapping for this key from this map if present (optional operation).
• int size()                                                Returns the number of key-value mappings in this map.

Set Operations

• Set  keySet()                                        Returns a set view of the keys contained in this map.
• Set  entrySet()                                      Returns a set view of the mappings contained in this map.
• Collection  values()                               Returns a collection view of the values contained in this map.

Other Operations

• void  clear()                                          Removes all mappings from this map (optional operation).
• boolean  containsKey(Object key)        Returns true if this map contains a mapping for the specified key.
• boolean  containsValue(Object value)   Returns true if this map maps one or more keys to the specified value.
• boolean   isEmpty()                              Returns true if this map contains no key-value mappings.
• void  putAll(Map t)                              Copies all of the mappings from the specified map to this map (optional operation).

public static interface Map.Entry

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

• Object   getKey()                           Returns the key corresponding to this entry.
• Object  getValue()                          Returns the value corresponding to this entry.
• Object   setValue(Object value)      Replaces the value corresponding to this entry with the specified value (optional operation).

public interface SortedSet extends Set

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

• Comparator  comparator()   Returns the comparator associated with this sorted set, or null if it uses its elements' natural ordering.
• Object  first()                       Returns the first (lowest) element currently in this sorted set.
• Object   last()                      Returns the last (highest) element currently in this sorted set.
• SortedSet  headSet(Object toElement)      Returns a view of the portion of this sorted set whose elements are strictly less than toElement.
• SortedSet   subSet(Object fromElement, Object toElement)   Returns a view of the portion of this sorted set whose elements range from fromElement, inclusive, to toElement, exclusive.
• SortedSet   tailSet(Object fromElement)     Returns a view of the portion of this sorted set whose elements are greater than or equal to         fromElement.

public interface SortedMap extends Map

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

• Comparator   comparator()       Returns the comparator associated with this sorted map, or null if it uses its keys' natural ordering.
• Object  firstKey()                      Returns the first (lowest) key currently in this sorted map.
• Object   lastKey()                     Returns the last (highest) key currently in this sorted map.
• SortedMap  headMap(Object toKey)       Returns a view of the portion of this sorted map whose keys are strictly less than toKey.
• SortedMap  subMap(Object fromKey, Object toKey)    Returns a view of the portion of this sorted map whose keys range from fromKey, inclusive, to  toKey, exclusive.
• SortedMap  tailMap(Object fromKey)      Returns a view of the portion of this sorted map whose keys are greater than or equal to fromKey.

public interface Comparator

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

•  int  compare(Object o1, Object o2)        Compares its two arguments for order.

public interface Comparable

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

• int  compareTo(Object o)   Compares this object with the specified object for order.