Wednesday, September 22, 2010

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

Maps relate a Key to a Value

AbstractMap implements Map
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
LinkedListSequence 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.
CollectionMethods 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.
ListIteratorAdditional methods for going backward.
Specialized classes
BitSet Expandable array of bits.
LinkedBlockingDequeCan have fixed upper size. Can block getting element until one added.
LinkedHashMapHash table where entries can also be accessed in order of creation.
LinkedHashSetHash set where entries can also be accessed in order of creation.
WeakHashMapHash table using weak references
PreferencesFor 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

InterfaceArrayBalanced TreeLinked ListHash table
List ArrayListLinkedList 
Map   TreeMap  HashMap
Set   TreeSet  HashSet
DequeArrayDeque  LinkedList 

No comments:

Post a Comment