Some Java Data Structures Interfaces

public interface Collection<T>

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 x) Returns true if this collection contains the specified element.

• boolean remove( Object x) Removes a single instance of the specified element from this collection, if it is present (optional operation).

• boolean add(T x) 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<? extends T> 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.

• <T> T[] toArray(T[] 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<T>

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.

• T next() Returns the next element in the interation.

• void remove() Removes from the underlying collection the last element returned by the iterator (optional operation).

Example code to construct a String to display all item in a Collection<T> c is:

String out = "";

Iterator<T> itr = c.iterator();

while( itr.hasNext() ) out += itr.next() + "\n";

Example code remove all occurrences of a element item from a Collection<T> is

while( c.remove(item) );

public interface Set<T> extends Collection<T>

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(T x) Adds the specified element to this set if it is not already present (optional operation).

• boolean  addAll(Collection<? extends T> c) Adds all of the elements in the specified collection to this set if they're not already present (optional operation).

public interface List<T> extends Collection<T>

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, T element) Inserts the specified element at the specified position in this list (optional operation).

• addAll(int index, Collection<? extends T> c) Inserts all of the elements in the specified collection into this list at the specified position (optional operation)

• T get(int index) Returns the element at the specified position in this list.

• int indexOf(Object x) 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 x) 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<T> listIterator() Returns a list iterator of the elements in this list (in proper sequence).

• ListIterator<T> listIterator(int index) Returns a list iterator of the elements in this list (in proper sequence), starting at the specified position  in this list.

• T set(int index, T element) Replaces the element at the specified position in this list with the specified element (optional operation).

• List<T> 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<T> extends Iterator<T>

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(T x) 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.

• T 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.

• T 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(T x) Replaces the last element returned by next or previous with the specified element (optional operation).

public interface Comparator <T>

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(y)}.

 Method Summary

• int compare(T lhs, T rhs) Compares its two arguments for order.

public interface Comparable<T>

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(T rhs) Compares this object with the specified object for order.

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 ollection 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 TreeMapclass, make specific guarantees as to their order; others, like the HashMap class, do not.

Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map. A special case of this prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the equals and hashCode methods are no longer well defined on such a map.

This interface is a member of the Java Collections Framework.

Many methods in Collections Framework interfaces are defined in terms of the equals method. For example, the specification for the containsKey(Object key)method says: "returns true if and only if this map contains a mapping for a key k such that (key==null ? k==null : key.equals(k))." This specification should notbe construed to imply that invoking Map.containsKey with a non-null argument key will cause key.equals(k) to be invoked for any key k. Implementations are free to implement optimizations whereby the equals invocation is avoided, for example, by first comparing the hash codes of the two keys. (The Object.hashCode()specification guarantees that two objects with unequal hash codes cannot be equal.) More generally, implementations of the various Collections Framework interfaces are free to take advantage of the specified behavior of underlying Object methods wherever the implementor deems it appropriate.