iSergius / Java Collections Complexity cheatsheet
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| Below are the Big O performance of common functions of different Java Collections. |
| List | Add | Remove | Get | Contains | Next | Data Structure |
| ———————|——|———|——|———-|——|————— |
| ArrayList | O(1) | O(n) | O(1) | O(n) | O(1) | Array |
| LinkedList | O(1) | O(1) | O(n) | O(n) | O(1) | Linked List |
| CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | O(1) | Array |
| Set | Add | Remove | Contains | Next | Size | Data Structure |
| ———————-|———-|———-|———-|———-|——|————————- |
| HashSet | O(1) | O(1) | O(1) | O(h/n) | O(1) | Hash Table |
| LinkedHashSet | O(1) | O(1) | O(1) | O(1) | O(1) | Hash Table + Linked List |
| EnumSet | O(1) | O(1) | O(1) | O(1) | O(1) | Bit Vector |
| TreeSet | O(log n) | O(log n) | O(log n) | O(log n) | O(1) | Red-black tree |
| CopyOnWriteArraySet | O(n) | O(n) | O(n) | O(1) | O(1) | Array |
| ConcurrentSkipListSet | O(log n) | O(log n) | O(log n) | O(1) | O(n) | Skip List |
| Queue | Offer | Peak | Poll | Remove | Size | Data Structure |
| ————————|———-|——|———-|———|——|————— |
| PriorityQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap |
| LinkedList | O(1) | O(1) | O(1) | O(1) | O(1) | Array |
| ArrayDequeue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List |
| ConcurrentLinkedQueue | O(1) | O(1) | O(1) | O(n) | O(n) | Linked List |
| ArrayBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Array |
| PriorirityBlockingQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap |
| SynchronousQueue | O(1) | O(1) | O(1) | O(n) | O(1) | None! |
| DelayQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap |
| LinkedBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List |
| Map | Get | ContainsKey | Next | Data Structure |
| ———————-|———-|————-|———-|————————- |
| HashMap | O(1) | O(1) | O(h / n) | Hash Table |
| LinkedHashMap | O(1) | O(1) | O(1) | Hash Table + Linked List |
| IdentityHashMap | O(1) | O(1) | O(h / n) | Array |
| WeakHashMap | O(1) | O(1) | O(h / n) | Hash Table |
| EnumMap | O(1) | O(1) | O(1) | Array |
| TreeMap | O(log n) | O(log n) | O(log n) | Red-black tree |
| ConcurrentHashMap | O(1) | O(1) | O(h / n) | Hash Tables |
| ConcurrentSkipListMap | O(log n) | O(log n) | O(1) | Skip List |
Java — Collection Interfaces and Implementations
This is a quick walk-through tutorial of Java Collections interfaces and their implementations.
Collection Interfaces
Collection Operations
It’s good to know what methods each interface offer:
Note that Set doesn’t have get(int index) method because no order is maintained with Set so elements don’t have fixed index.
Collection Implementations
Making a Decision in choosing a Collection
Making a decision regarding choosing a Queue implementation is quite straight forward and is not relevant in above diagram. Whenever we need to hold elements prior to processing and just need the method remove() to get and remove elements at the same time we are going to use queues. Also there’s no index based operation to be performed when using queues. If we want to order queue elements in some order then use PriorityQueue, otherwise use ArrayDeque.
EnumSet is also very straight forward i.e. whenever we want to hold certain elements of an enum we will use it. We can also use other collections for the same purpose but remember EnumSet is very very efficient comparatively.
Synchronization
It’s not recommended to use legacy collections. One advantage of using them might seem to be that they are synchronized. java.util.Collections provides methods to wrap any collection around a new collection which is synchronized. These methods are:
Collection synchronizedCollection(Collection c)
Set synchronizedSet(Set s)
SortedSet synchronizedSortedSet(SortedSet s)
NavigableSet synchronizedNavigableSet(NavigableSet s)
List synchronizedList(List list)
Read Only Collections
java.util.Collections provides methods to wrap any collection and return a new Collection which are read only. Attempts to modify (calling mutative methods), directly or via iterators will cause UnsupportedOperationException . Followings are the methods:
Collection unmodifiableCollection(Collection c)
Set unmodifiableSet(Set s)
SortedSet unmodifiableSortedSet(SortedSet s)
NavigableSet unmodifiableNavigableSet(NavigableSet s)
List unmodifiableList(List list)
In next topics we will explore concurrent collections and then maps.