Java Notes

Collections Overview

Summary of Collections interfaces

Most of the methods in the data structure classes are those of the interfaces that the classes implement.

• Collections - This is a basic set of methods for working with data structures.
• List - (extends Collection) Elements are accessible sequentially.
• Map - Stores key/value pairs, rapidly accessible by key.
• SortedMap - (extends Map) As with map, but can be also be accessed in order.
• Set - (extends Collection) For a given key there is only one value.
• SortedSet - (extends Set) As above, but can also be accessed in order.

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
        AbstractSequentialList<E>
            LinkedList<E>
        Vector<E> implements RandomAccess<E>  // Synchronized equivalent of ArrayList
            Stack<E>  // Adds push(), pop(), and peek()
    AbstractSet<E> implements Set<E>
        HashSet<E>
            LinkedHashSet<E>
        TreeSet<E> implements SortedSet<E>
        EnumSet<E>   // Bitset implementation for Enum class.
    AbstractQueue<E> implements Queue<E>
        PriorityQueue<E>
    
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.
    
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.

Interface Implementations

Algorithm and Data Structure Links

• www.nist.gov/dads/terms.html - Dictionary of Algorithms and Data Structures