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 }