Java Data Structures

The standard Java Data Structures is represented an amalgam of classes, interfaces and algorithms consolidated in the java.util package. These are often referred to as the Java collections, although this is a misleading term. Indeed there is a Collection interface and a Collections class which serve very different purposes.

java.util summary

Extracted directly from JDK7.0 API documentation.

Interfaces

Collection<E> The root interface in the collection hierarchy.
Comparator<T> A comparison function, which imposes a total ordering on some collection of objects.
Deque<E> A linear collection that supports element insertion and removal at both ends.
Enumeration<E> An object that implements the Enumeration interface generates a series of elements, one at a time.
EventListener A tagging interface that all event listener interfaces must extend.
Formattable The Formattable interface must be implemented by any class that needs to perform custom formatting using the 's' conversion specifier of Formatter.
Iterator<E> An iterator over a collection.
List<E> An ordered collection (also known as a sequence).
ListIterator<E> An iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list.
Map<K,V> An object that maps keys to values.
Map.Entry<K,V> A map entry (key-value pair).
NavigableMap<K,V> A SortedMap extended with navigation methods returning the closest matches for given search targets.
NavigableSet<E> A SortedSet extended with navigation methods reporting closest matches for given search targets.
Observer A class can implement the Observer interface when it wants to be informed of changes in observable objects.
Queue<E> A collection designed for holding elements prior to processing.
RandomAccess Marker interface used by List implementations to indicate that they support fast (generally constant time) random access.
Set<E> A collection that contains no duplicate elements.
SortedMap<K,V> A Map that further provides a total ordering on its keys.
SortedSet<E> A Set that further provides a total ordering on its elements.

Classes

AbstractCollection<E> This class provides a skeletal implementation of the Collection interface, to minimize the effort required to implement this interface.
AbstractList<E> This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a "random access" data store (such as an array).
AbstractMap<K,V> This class provides a skeletal implementation of the Map interface, to minimize the effort required to implement this interface.
AbstractMap.SimpleEntry<K,V> An Entry maintaining a key and a value.
AbstractMap.SimpleImmutableEntry<K,V> An Entry maintaining an immutable key and value.
AbstractQueue<E> This class provides skeletal implementations of some Queue operations.
AbstractSequentialList<E> This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a "sequential access" data store (such as a linked list).
AbstractSet<E> This class provides a skeletal implementation of the Set interface to minimize the effort required to implement this interface.
ArrayDeque<E> Resizable-array implementation of the Deque interface.
ArrayList<E> Resizable-array implementation of the List interface.
Arrays This class contains various methods for manipulating arrays (such as sorting and searching).
BitSet This class implements a vector of bits that grows as needed.
Calendar The Calendar class is an abstract class that provides methods for converting between a specific instant in time and a set of calendar fields such as YEAR, MONTH, DAY_OF_MONTH, HOUR, and so on, and for manipulating the calendar fields, such as getting the date of the next week.
Collections This class consists exclusively of static methods that operate on or return collections.
Currency Represents a currency.
Date The class Date represents a specific instant in time, with millisecond precision.
Dictionary<K,V> The Dictionary class is the abstract parent of any class, such as Hashtable, which maps keys to values.
EnumMap<K extends Enum<K>,V> A specialized Map implementation for use with enum type keys.
EnumSet<E extends Enum<E>> A specialized Set implementation for use with enum types.
EventListenerProxy An abstract wrapper class for an EventListener class which associates a set of additional parameters with the listener.
EventObject The root class from which all event state objects shall be derived.
FormattableFlags FomattableFlags are passed to the Formattable.formatTo() method and modify the output format for Formattables.
Formatter An interpreter for printf-style format strings.
GregorianCalendar GregorianCalendar is a concrete subclass of Calendar and provides the standard calendar system used by most of the world.
HashMap<K,V> Hash table based implementation of the Map interface.
HashSet<E> This class implements the Set interface, backed by a hash table (actually a HashMap instance).
Hashtable<K,V> This class implements a hashtable, which maps keys to values.
IdentityHashMap<K,V> This class implements the Map interface with a hash table, using reference-equality in place of object-equality when comparing keys (and values).
LinkedHashMap<K,V> Hash table and linked list implementation of the Map interface, with predictable iteration order.
LinkedHashSet<E> Hash table and linked list implementation of the Set interface, with predictable iteration order.
LinkedList<E> Linked list implementation of the List interface.
ListResourceBundle ListResourceBundle is an abstract subclass of ResourceBundle that manages resources for a locale in a convenient and easy to use list.
Locale A Locale object represents a specific geographical, political, or cultural region.
Observable This class represents an observable object, or "data" in the model-view paradigm.
PriorityQueue<E> An unbounded priority queue based on a priority heap.
Properties The Properties class represents a persistent set of properties.
PropertyPermission This class is for property permissions.
PropertyResourceBundle PropertyResourceBundle is a concrete subclass of ResourceBundle that manages resources for a locale using a set of static strings from a property file.
Random An instance of this class is used to generate a stream of pseudorandom numbers.
ResourceBundle Resource bundles contain locale-specific objects.
ResourceBundle.Control ResourceBundle.Control defines a set of callback methods that are invoked by the ResourceBundle.getBundle factory methods during the bundle loading process.
Scanner A simple text scanner which can parse primitive types and strings using regular expressions.
ServiceLoader<S> A simple service-provider loading facility.
SimpleTimeZone SimpleTimeZone is a concrete subclass of TimeZone that represents a time zone for use with a Gregorian calendar.
Stack<E> The Stack class represents a last-in-first-out (LIFO) stack of objects.
StringTokenizer The string tokenizer class allows an application to break a string into tokens.
Timer A facility for threads to schedule tasks for future execution in a background thread.
TimerTask A task that can be scheduled for one-time or repeated execution by a Timer.
TimeZone TimeZone represents a time zone offset, and also figures out daylight savings.
TreeMap<K,V> A Red-Black tree based NavigableMap implementation.
TreeSet<E> A NavigableSet implementation based on a TreeMap.
UUID A class that represents an immutable universally unique identifier (UUID).
Vector<E> The Vector class implements a growable array of objects.
WeakHashMap<K,V> A hashtable-based Map implementation with weak keys.

Collection interface

A Collection is Java's notion of something which holds objects. We can add and remove in a variety of ways along with a few other basic operations. Technically, a Collection is a (templated) interface supporting these member functions:
boolean  add(E e)
boolean  addAll(Collection<? extends E> c)
void     clear()
boolean  contains(Object o)
boolean  containsAll(Collection<?> c)
boolean  equals(Object o)
int      hashCode()
boolean  isEmpty()
boolean  remove(Object o)
boolean  removeAll(Collection<?> c)
boolean  retainAll(Collection<?> c)
int      size()
Object[] toArray()
E[]      toArray(E[] a)

Iterator<E> iterator()
The last of these, the iterator operation, is required by virtue of Collection being a subinterface of the Iterable interface whose sole requirement is the iterator function. The value returned by iterator is an object implementing the Iterator<T> interface with these functions:
boolean hasNext()
E next()
void remove()

Subinterfaces and implementations

The subinterfaces of Collection of interest to us are: We are interested in the subinterfaces, in particular these:
Deque<E>, List<E>, 
NavigableSet<E>, Queue<E>, 
Set<E>, SortedSet<E>
The implementations of interest are:
ArrayDeque, ArrayList, EnumSet, HashSet, LinkedHashSet, 
LinkedList, PriorityQueue, Stack, TreeSet, Vector

List interface

A List extends Collection, and so, contains the all the Collection member functions. In addition, it has these member functions which add the ability to identify and manipulate via an integer position:
void add(int index, E element)
boolean addAll(int index, Collection<? extends E> c)

E get(int index)
E remove(int index)
E set(int index, E element)

int  indexOf(Object o)
int  lastIndexOf(Object o)

List<E>         subList(int fromIndex, int toIndex)
ListIterator<E> listIterator()
ListIterator<E> listIterator(int index)
In addition, the ListIterator interface extends Iterator by adding these member functions:
boolean hasPrevious()
int  nextIndex()
E    previous()
int  previousIndex()
void add(E e) 
void set(E e)
Implementations are:
ArrayList, LinkedList, Stack, Vector
The LinkedList distinguishes itself from the others by not being a RandomAccess implementation, implying that the time to access different elements in the list may differ greatly.

Set interface

A Set adds no new member functions to a Collection. It is a Collection which contains no duplicate elements. In particular, for the set object S, the sequence:
S.add( obj );
S.add( obj );
S.remove( obj );
will remove obj, something that would not happen in a non-Set collection.

Implementations of interest to us are:
EnumSet, HashSet, LinkedHashSet, TreeSet

Queue/Deque/Stack

The Queue, Deque, Stack represent list structures which focus on operations restricted primarily to the ends of the list.

Queue interface

A Queue is a Collection in which elements are added and removed in a manner dictated by an ordering policy (FIFO being the simplest, but there are others). These six member functions apply (add is already defined from Collection):
// add something to the Queue
boolean  offer(E e)  // false returned if no space to add
boolean  add(E e)    // exception thrown if no space to add

// retrieve front element (null if empty)
E peek()
E element()   // exception thrown if empty

// retrieve and remove front element (null if empty)
E poll()
E remove()   // exception thrown if empty
Implementations of interest to us are:
ArrayDeque, LinkedList, PriorityQueue

Deque interface

The Deque (double-ended queue) is an extension of Queue which gives access to "both sides" of the queue to which elements can be added or removed. The two sides of the queue are viewed as:
first:  the "head" of the queue (least recently added)
last:   the "tail" of the queue (most recently added)
The Queue's six operations (add, offer, remove, poll, element, peek) become 12 operations, replacing element by get and appending First and Last to each of them. Thus we get these equivalences:
Queue/Deque Method Equivalent Deque Method
add(e) addLast(e)
offer(e) offerLast(e)
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()
Implementations of interest to us are:
ArrayDeque, LinkedList

Stack

Unlike the List, Queue and Deque, the Java Stack per se is not an interface; rather, Stack is an extension of the Vector class. This is actually a legacy class and the Deque should be preferred to it.

When using a Deque as a Stack, we execute adds and removes exclusively from one side. The JDK documentation appears to prefer to use the "First" side; thus, these are the suggested implementations:
Stack Method Equivalent Deque Methods
boolean push(e) addFirst(e), offerFirst(e)
pop() remove() ( = removeFirst() ) or poll() ( = pollFirst() )
In order to access or peek at the "top" element without removing we would use:
peek() ( = peekFirst() )  or  getFirst()
Strictly speaking, peek is not necessary in a Stack since it is implementable from pop and push by popping the value, pushing it back on and returning the popped value.

Map interface

A Map is another name for an association list, something which assigns a certain set of keys to values. Like other collection classes it is templated, this time by two types:
Map<K,V>
associating elements of key type K to elements of value type V. The term map is synonymous with the mathematical term partial function. A map is a function because only one value can be associated with a given key. It is partial because not all elements of K have associated values. These are the member functions:
void      clear()
boolean   containsKey(Object key)
boolean   containsValue(Object value)
boolean   equals(Object o)
V         get(Object key)
int       hashCode()
boolean   isEmpty()
V         put(K key, V value)
void      putAll(Map<? extends K,? extends V> m)
V         remove(Object key)
int       size()

Set<Map.Entry<K,V>>  entrySet()
Set<K>               keySet()
Collection<V>        values()
The only subinterfaces of interest to us are:
NavigableMap<K,V>, SortedMap<K,V>
The implementations of interest are:
HashMap, Hashtable, IdentityHashMap, LinkedHashMap, 
Properties, TabularDataSupport, TreeMap, WeakHashMap 

Collections class

The Java Collections class represents a collection of algorithms represented as static member functions acting on the Collection and Map objects.. The functions (all static) are indicated below. See the documentation for a fuller explanation.
boolean addAll(Collection<? super E> c, E... elements)

Queue<E> asLifoQueue(Deque<E> deque)

int binarySearch(List<? extends Comparable<? super E>> list, E key)
int binarySearch(List<? extends E> list, E key, Comparator<? super E> c)

void copy(List<? super E> dest, List<? extends E> src)

boolean disjoint(Collection<?> c1, Collection<?> c2)

List<E>  emptyList()
Map<K,V> emptyMap()
Set<E>   emptySet()

Enumeration<E> enumeration(Collection<E> c)

void fill(List<? super E> list, E obj)

int frequency(Collection<?> c, Object o)

int indexOfSubList(List<?> source, List<?> target)
int lastIndexOfSubList(List<?> source, List<?> target)

ArrayList<T> list(Enumeration<T> e)

T max(Collection<? extends E> coll)
T max(Collection<? extends E> coll, Comparator<? super E> comp)
T min(Collection<? extends E> coll)
T min(Collection<? extends E> coll, Comparator<? super E> comp)

List<E> nCopies(int n, E o)

Set<E> newSetFromMap(Map<E,Boolean> map)

boolean replaceAll(List<E> list, E oldVal, E newVal)

void reverse(List<?> list)

Comparator<E> reverseOrder()
Comparator<E> reverseOrder(Comparator<E> cmp)

void rotate(List<?> list, int distance)

void shuffle(List<?> list)
void shuffle(List<?> list, Random rnd)

void sort(List<E> list)
void sort(List<E> list, Comparator<? super E> c)

void swap(List<?> list, int i, int j)

Set<E>   singleton(E o)
List<E>  singletonList(E o)
Map<K,V> singletonMap(K key, V value)

Collection<E>  checkedCollection(Collection<E> c, Class<E> type)
List<E>        checkedList(List<E> list, Class<E> type)
Map<K,V>       checkedMap(Map<K,V> m, Class<K> keyType, Class<V> valueType)
Set<E>         checkedSet(Set<E> s, Class<E> type)
SortedMap<K,V> checkedSortedMap(SortedMap<K,V> m, Class<K> keyType, Class<V> valueType)
SortedSet<E>   checkedSortedSet(SortedSet<E> s, Class<E> type)

Collection<E>  synchronizedCollection(Collection<E> c)
List<E>        synchronizedList(List<E> list)
Map<K,V>       synchronizedMap(Map<K,V> m)
Set<E>         synchronizedSet(Set<E> s)
SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m)
SortedSet<E>   synchronizedSortedSet(SortedSet<E> s)

Collection<E>  unmodifiableCollection(Collection<? extends E> c)
List<E>        unmodifiableList(List<? extends E> list)
Map<K,V>       unmodifiableMap(Map<? extends K,? extends V> m)
Set<E>         unmodifiableSet(Set<? extends E> s)
SortedMap<K,V> unmodifiableSortedMap(SortedMap<K,? extends V> m)
SortedSet<E>   unmodifiableSortedSet(SortedSet<E> s)

Arrays class

The Java Arrays class represents a collection of algorithms represented as static member functions acting on arrays. The functions (all static) are indicated below. The "T" represents not only a templated class, but the generic Object class as well as one of the primitive types byte, char, double, float, int, short, long. See the documentation for a fuller explanation.
List<T> asList(T[] a)

int binarySearch(T[] a, T key)
int binarySearch(T[] a, int fromIndex, int toIndex, T key)
int binarySearch(T[] a, T key, Comparator<? super T> c)
int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)

void sort(T[] a)
void sort(T[] a, Comparator<? super T> c)
void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)

boolean equals(T[] a, T[] a2)

String toString(T[] a)

T[] copyOf(T[] original, int newLength)
T[] copyOfRange(T[] original, int from, int to)

boolean deepEquals(Object[] a1, Object[] a2)
int deepHashCode(Object[] a)
String deepToString(Object[] a)

void fill(T[] a, T val)

int hashCode(T[] a)


© Robert M. Kline