Collections (Data Structure Library)

Predefined Libraries

• Standard data-structure solutions.
• Similar to C++ Standard Template Library.
• Don't rewrite structures already available: linked lists, hash tables, expanding arrays, balanced binary search trees, etc.
• Do write structures specialized to your problem domain.
• Versions
  • <ver 1.2: Legacy versions still used some (esp Vector)
  • ver 1.2-1.4: Collections without generics (templaces).
  • Java 5 (1.5) has generics, similar to C++ templates.
• Non-standard packages fill gaps in Collections, eg, Apache Jakarta Commons Collections.

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

• No primitives can be stored in Collections.
  • Use wrapper classes (Integer, Float, ...) or your own class.
  • Wrapper classes are immutable, which may be a problem.
  • Bad: Performance, inconvenience.
• Pre Java 5: All elements are type Object
  • Upcasting is automatic.
  • Ugly: Only Objects come back out. Requires downcasting.
  • Insecure: Mixed types can potentially be added to a Collection.
• Java 5 Generics
  • Like C++ templates.
  • Compiler change only -- same Java Virtual Machine is used.
  • More secure -- adding different types is extremely difficult.
  • Automatic downcasting makes code much more readable.
  • "Autoboxing" hides conversion between primitive types and their wrapper classes. Problems lurking here?

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

• List interface specifies common methods.
  • ArrayList - Expandable array. Access O(1). Insertions/Deletions O(n).
  • LinkedList - Linked list implementation. Access O(N). Insertions/deletions O(1).

Set Interface with two concrete implementations

• Set interface specifies common methods.
  • TreeSet - Balanced binary tree. Insert/access O(log N). Sorted.
  • HashSet - Hash table. Insert/access O(1). Unsorted.

Map Interface with two concrete implementations

• Map interface specifies common methods.
  • TreeMap - Balanced binary tree. Insert/access O(log N). Sorted by key.
  • HashMap - Hash table. Insert/access O(1). Unsorted.
    • LinkedHashMap - Iterator produced elements in insertion order.
  • WeakHashMap - If no references to key object, can delete entry.
  • IdentityHashMap - Compare by key reference identity, not hashcode.

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