# Java: 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, except Object, are in the `java.util` package. Indentation shows the class inheritance. The most useful classes are in bold.

    java.util.Collections  // Contains may useful static methods.
    java.util.AbstractCollection implements Collection
        java.util.AbstractList implements List
            java.util.ArrayList implements RandomAccess
            java.util.AbstractSequentialList
                java.util.LinkedList
            java.util.Vector implements RandomAccess  // Synchronized equivalent of ArrayList
                java.util.Stack  // Adds push(), pop(), and peek()
        java.util.AbstractSet implements Set
            java.util.HashSet
                java.util.LinkedHashSet
            java.util.TreeSet implements SortedSet
    java.util.AbstractMap implements Map
        java.util.HashMap
            java.util.LinkedHashMap
        java.util.TreeMap implements SortedMap
        java.util.WeakHashMap      // Special usage
        java.util.IdentityHashMap  // Special usage
    java.util.Dictionary           // Old - do not use
        java.util.HashTable implements Map // Old - replaced by HashMap
    java.util.Iterator         // An interface.
        java.util.ListIterator // An interface
    java.util.Map.Entry               // Map key/value pair.

## Concrete classes and interfaces

Theser 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.
LinkedHashSet | Hash table 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 + Linked List
`List` | `ArrayList` |  | `LinkedList` |
`Map` |  | `TreeMap` |  | `HashMap`
`Set` |  | `TreeSet` |  | `HashSet`