Runtime Complexity of Java Collections

gistfile1.java

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(n)  | O(n) |   O(n)   | O(1) | Double 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 (TreeMap)
CopyOnWriteArraySet   | O(n)     | O(n)     | O(n)     | O(1)     | O(1) | Array (CopyOnWriteArrayList)
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(n)  | O(1) | Double Linked List
ArrayDeque              | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | Array with head and tail index
ConcurrentLinkedQueue   | O(1)     | O(1) | O(1)     |  O(n)  | O(n) | Linked List with CAS(no lock)
ArrayBlockingQueue      | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | Array with reentrantLock
PriorirityBlockingQueue | O(log n) | O(1) | O(log n) |  O(n)  | O(1) | Priority Heap with reentrantLock
SynchronousQueue        | O(1)     | O(1) | O(1)     |  O(1)  | O(1) | None!
DelayQueue              | O(log n) | O(1) | O(log n) |  O(n)  | O(1) | Priority Heap with reentrantLock
LinkedBlockingQueue     | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | Linked List with 2 reentrantLock



Map                   |   Get    | ContainsKey |   Put   | Data Structure
----------------------|----------|-------------|---------|-------------------------
HashMap               | O(1)     |   O(1)      |   O(1)  | Hash Table
HashTable             | O(1)     |   O(1)      |   O(1)  | Hash Table
LinkedHashMap         | O(1)     |   O(1)      |   O(1)  | Hash Table + Double Linked List
IdentityHashMap       | O(1)     |   O(1)      |   O(1)  | Array
WeakHashMap           | O(1)     |   O(1)      |   O(1)  | 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(1)  | Hash Tables (Linked List + Array + Red-Black Tree)
ConcurrentSkipListMap | O(log n) |   O(log n)  | O(log n)| Skip List