Collections Overview

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

Maps relate a Key to a Value

AbstractMap implements Map
HashMap
LinkedHashMap // Keys can be iterated in insertion order.
TreeMap implements SortedMap
EnumMap          // Keys must be from same Enum class.
WeakHashMap      // Special usage - Keys are weak references.
IdentityHashMap  // Special usage - Keys must be identical.

Map.Entry       // Map key/value pair.

Interfaces used with data structures

Iterator           // Interface requires hasNext(), next(), ?remove()
ListIterator   // Interface

Comparator         // Interface requires compare() and equals()

// The following java.lang interfaces are commonly used in Collections.
Iterable          // Interface requires iterator()
Comparable        // 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