# Java Notes

# Collections Overview

## Summary of Collections interfaces

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

- `Collections` - A basic set of methods for working with data structures.
- `List` - Extends Collection. Elements are accessible sequentially or by index.
- `Map` - Stores key/value pairs, rapidly accessible by key.
- `SortedMap` - Extends Map, adding access in sorted order.
- `Set` - Extends Collection. Conains only one copy of a value.
- `SortedSet` - Extends Set. As above, but can also be accessed in order.
- `Deque` - Double-ended queue, used for both stack (LIFO) and queue (FIFO) operations.

## 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> implements Deque<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>
        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
LinkedList | Sequence 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.
Interfaces
Collection | Methods 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.
ListIterator | Additional methods for going backward.
Specialized classes
BitSet | Expandable array of bits.
LinkedBlockingDeque | Can have fixed upper size. Can block getting element until one added.
LinkedHashMap | Hash table where entries can also be accessed in order of creation.
LinkedHashSet | Hash set where entries can also be accessed in order of creation.
WeakHashMap | Hash table using weak references
Preferences | For 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

| Implementations
--- | ---
Interface | Array | Balanced Tree | Linked List | Hash table
`List` | `ArrayList` |  | `LinkedList` |
`Map` |  | `TreeMap` |  | `HashMap`
`Set` |  | `TreeSet` |  | `HashSet`
`Deque` | `ArrayDeque` |  | `LinkedList` |

## More needed on the following newer topics

- NavigableSet and NavigableMap
- Concurrent data structures

## Algorithm and Data Structure Links

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