Java Notes

Collections Overview

Summary of Collections interfaces

Most methods in data structure classes are required by implemented interfaces.

Class/Interface Hierarchy

The following classes and interfaces, are in the java.util package. Indentation shows the class inheritance. The most useful classes are in bold.

Collections  // Contains may useful static methods.

AbstractCollection<E> implements Collection<E>, Iterable<E>
    AbstractList<E> implements List<E>
        ArrayList<E> implements RandomAccess
            LinkedList<E> implements Deque<E>
        Vector<E> implements RandomAccess<E>  // Synchronized equivalent of ArrayList
            Stack<E>  // Adds push(), pop(), and peek()
    AbstractSet<E> implements Set<E>
        TreeSet<E> implements SortedSet<E>
        EnumSet<E>   // Bitset implementation for Enum class.
    AbstractQueue<E> implements Queue<E>
    ArrayDeque<E> implements Queue<E> Deque<E>

Maps relate a Key to a Value

AbstractMap<K, V> implements Map<K, V>
    HashMap<K, V>
        LinkedHashMap<K, V> // Keys can be iterated in insertion order.
    TreeMap<K, V> implements SortedMap<K, V>
    EnumMap<K, V>          // Keys must be from same Enum class.
    WeakHashMap<K, V>      // Special usage - Keys are weak references.
    IdentityHashMap<K, V>  // Special usage - Keys must be identical.
Map.Entry<K, V>       // Map key/value pair.

Interfaces used with data structures

Iterator<E>           // Interface requires hasNext(), next(), ?remove()
    ListIterator<E>   // Interface
Comparator<T>         // Interface requires compare() and equals()

// The following java.lang interfaces are commonly used in Collections.
Iterable<T>          // Interface requires iterator()
Comparable<T>        // Interface requires compareTo()

Concrete classes and interfaces

These are some of the most useful data structure classes, listing the primary data-structure relevant interface, and omitting utility interfaces such as Cloneable and Serializable.

Class Implementation
Most commonly used classes
ArrayList Sequence of values stored in resizable array
LinkedListSequence of values stored in linked list
HashMap Key/value pairs in hash table.
TreeMap Key/value pairs in balanced binary tree.
HashSet Single copy of value stored in hash table. Implements Set.
TreeSet Single copy of value stored in balanced binary. Implements Set.
CollectionMethods common to all data structures.
List Basic List methods. Implemented by ArrayList and LinkedList.
Map Basic Map methods. Implemented by HashMap and TreeMap.
Map.Entry Key/value pairs in Set returned by Map.entrySet().
Set Basic Set methods. Implemented by HashSet and TreeSet.
Iterator Methods for forward iteration.
ListIteratorAdditional methods for going backward.
Specialized classes
BitSet Expandable array of bits.
LinkedBlockingDequeCan have fixed upper size. Can block getting element until one added.
LinkedHashMapHash table where entries can also be accessed in order of creation.
LinkedHashSetHash set where entries can also be accessed in order of creation.
WeakHashMapHash table using weak references
PreferencesFor persistent storage of program options.
Properties Pre-Java 2, compare to Preferences
Older classes which have a newer replacement
HashTable Older, synchronized version of HashMap.
Vector Older, synchronized version of ArrayList, still used.
Obsolete classes
Dictionary Obsolete abstract class. Do not use.

Interface Implementations

InterfaceArrayBalanced TreeLinked ListHash table
List ArrayList LinkedList 
Map   TreeMap  HashMap
Set   TreeSet  HashSet
DequeArrayDeque  LinkedList 

More needed on the following newer topics

Algorithm and Data Structure Links