Collections (Data Structure Library)

Predefined Libraries

Basic Data Structures

Containers - hold values
  • Arrays - In language. Stores elements at numbered positions.
  • Lists - Sequential elements (ArrayList and LinkedList)
  • Sets - Single copy of elements (TreeSet and HashSet)
  • Maps - Key-value pairs. (HashMap and TreeMap).
  • Misc others.
Iterators
Pass over the elements of data structures.
Algorithms
Manipulate data structures (sorting, searching, ...).

All classes are in java.util.* unless otherwise specified.

Objects only

Class Hierarchy

Collections class contains useful static methods.
AbstractCollection implements Collection
    AbstractList implements List
        ArrayList implements RandomAccess
        AbstractSequentialList
            LinkedList
        Vector implements RandomAccess
            Stack 
    AbstractSet implements Set
        HashSet
            LinkedHashSet
        TreeSet implements SortedSet
AbstractMap implements Map
    HashMap
        LinkedHashMap
    TreeMap implements SortedMap
    WeakHashMap
    IdentityHashMap

Interface Hierarchy

Collection
    Set
        SortedSet
    List
Map
    SortedMap
Map.Entry
Iterator
    ListIterator
Comparator
RandomAccess   // Marker interface

java.util.Collections Class static methods

binarySearch(List, Object)
binarySearch(List, Object, Comparator)
copy(List dest, List src)
fill(List, Object)
indexOfSublist(List src, List target)
max(Collection)               min also
max(Collection, Comparator)   min also
replaceAll(List, Object oldval, Object newval)
reverse(List)
rotate(List, distance)
shuffle(List)
sort(List)
sort(List, Comparator)   O(N log N), stable
swap(List, i, j)
synchronizedCollection(Collection)
synchronizedList(List)  same for Map, SortedMap, Set, SortedSet
unmodifiableCollection(Collection)
unmodifiableList(List)  same for Map, SortedMap, Set, SortedSet

Collection Interface Methods

add(Object)
add(Collection)
clear()
contains(Object)
containsAll(Collection)
isEmpty()
iterator()
remove(Object)
removeAll(Collection)
retailAll(Collection)
size()
toArray()
toArray(Object[])

List Interface with two concrete implementations

Set Interface with two concrete implementations

Map Interface with two concrete implementations

Map Interface methods

clear()
containsKey(Object)
containsValue(Object)
entrySet()  returns Set of Map.Entry elements.
get(Object key)
isEmpty()
keySet()    returns Set of keys
put(Object key, Object value)
putAll(Map)
remove(Object key)
size()
values()   returns Collection view of values.

Iterator Interface

public interface Iterator {
    public booean hasNext();  // true if there are more elements.
    public Object next();     // returns next element.
    public void   remove();   // Removes last element returned by next. Optional.
}

Typical pattern pre Java 5.

List names = new ArrayList();
names.add("Bill");
names.add("Jill");   //  Strings will get upcast to Object in the ArrayList.
...
Iterator it = names.iterator();
while (it.hasNext()) {
   String aName = (String)(it.next());
   ...
}

Must cast the Object that comes out of the data structure to the type we need, eg, String in this case.

Iterator Interface

Typical pattern in Java 5.

List<String> names = new ArrayList<String>();
names.add("Bill");
names.add("Jill"); 
. . .
Iterator<String> it = names.iterator();
while (it.hasNext()) {
   String aName = it.next();
   .  ..
}

Or using the new Java 5 for loop.

. . .
for (String aName : names {
   . . .
}

ListIterator Interface

In addition to hasNext() and next(), has the following. A ListIterator is always between elements. The operation applies to the most recently accessed element, either from either next() or previous*(.

add(Object)
hasPrevious()  // true if there is a previous element
previous()     // return previous element
set(Object)    // changes value of most recent (prev/next) element.

Comparator Interface

When sorting objects, there is usually no obviously natural way to compare them (exception: Strings). You often need to supply a Comparator object when sorting data strucutures.

public interface Comparator {
    public int compareTo(Object a, Object b); // <0, 0, or >0
}

See Example - Word Frequency lines 105 and 123.

Similar to Comparable interface, as in String.

public interface Comparable {
    public int compareTo(Object b); // <0, 0, or >0
}

End