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`