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.
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.
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).
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).
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.
PropertyResourceBundle is a concrete subclass of
ResourceBundle that manages resources for a locale
using a set of static strings from a property file.
ResourceBundle.Control defines a set of callback methods
that are invoked by the ResourceBundle.getBundle factory
methods during the bundle loading process.
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:
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:
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 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)