Java Collections Cheatsheet

Main operations: Insert, Search, Delete, Iterate (visit all the items in a collection).

Java Collections Framework provides three major types of collections: set, list and map.

They are defined in the interface Set, List and Map.

Set: no repeated elements.
List: elements stored in insertion order (but we can also insert elements anywhere in the list).
Map: stores key-value pairs.
Tree: elements stored based in their natural order.

CONCEPTS

• Array: Only built-in structure. Fixed size. Quick insertion (at the end). Slow search (unless we know the element’s index). Slow deletion.
• Stack: Last-In First-Out (LIFO). Slow access to other items (except last one).
• Queue: First-In First-Out (FIFO). Slow access to other items (except first one).

(Stacks and Queues are usually implemented by arrays or linked-lists with the constrains of FIFO or LIFO. There is no need for a custom implementation in the Java Collections Framework).

• Linked-list: The list contains only a reference to the first item. Each item contains a reference to the next one. Quick insertion (at the beginning). Slow deletion (except at the beginning). Slow search.
• Set: Group of elements with no duplicates. Usually implemented by a HashTable (=Map) where the keys have no meaning, or a Tree.
• Map: collection of key-value pairs. Usually implemented by HashTable (Array + LinkedLists, for example). Quick insertion. Quick search if key is known. Slow deletion. Inefficient memory usage (good if there won’t be too many deletions).
• Binary Tree: Only two children per node. The tree only contains a reference to the root (the first node). Each node contains a reference to its left and right nodes.
• Binary Search Tree: the nodes are ordered by key value. When we insert an item, the tree looks for the right position to insert it. Quick search, insertion, deletion (it tree is balanced). It might become unbalance if the elements are inserted in order.
• Red-Black Tree: balanced Binary Search Tree.

IMPLEMENTATIONS (in Java)

Interfaces

• Collection
• List: Collection whose elements can be traversed in insertion order.
• Queue: Collection that maintains its elements in processing order.
• Set: Collection that cannot contain duplicate objects.
• SortedSet: Set whose elements are ordered. => Deprecated. Replaced by NavigableSet
• Map: Collection of key-value pairs. Each key maps to at most one value (does not allow duplicate keys). Both the keys and the values must be objects, so primitive values will be wrapped.
• SortedMap: Map whose keys are ordered. => Deprecated. Replaced by NavigableMap

Classes

Implement List:

• LinkedList: elements will be traversed in insertion order. Elements can be accessed, added, and removed efficiently at either end of the list (it’s a doubly linked list). It also implements Queue and Deque.
• ArrayList: elements will be traversed in insertion order. Elements can be accessed efficiently by index (unlike in LinkedList).
• Vector: elements will be traversed in insertion order. Resizable array. Synchronized.

Implement Queue (elements in processing order):

• PriorityQueue: elements will be accessed according to priority order.
• ArrayDeque: elements will be accessed according to either FIFO or LIFO processing order. It also implements Dequeue.

Implement Set (unique elements):

• HashSet: no particular order. It’s a HashTable with no duplicates (we don’t know and don’t care about the key that maps to each value).
• LinkedHashSet: + elements traversed in insertion order.
• TreeSet: elements will be traversed in the order specified by the compareTo method of the elements = element order. It uses a balanced binary tree à all operations are efficient. It also implements NavigableSet.

Implement Map (unique keys):

• HashMap: no particular order. HashTable where each key maps to a value (we can retrieve both keys and values).
• LinkedHashMap: + elements will be traversed in key insertion order.
• IdentityHashMap: + compares keys using == instead of the equals method.
• HashTable: no particular order. Synchronized.
• TreeMap: elements will be traversed in the order specified by the compareTo method of the keys = key order. It uses a balanced binary tree à all operations are efficient. It also implements NavigableMap.

If the elements have hashCode method, they can be used as HashSet elements or HashMap keys.

If the elements have a compareTo method, they can be used as TreeSet elements or TreeMap keys.