List
| 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
| 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
| Queue | offer | peek | 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 |
Deque
| Deque | offer/offerLast | peek | poll/pollLast | remove/removeLast | Size | Data Structure |
|---|
| 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 |
Map
| Map | put | get | containsKey | next | Data Structure |
|---|
| HashMap | O(1) ~ O(n) | O(1) | O(1) | O(h / n) | Hash Table |
| LinkedHashMap | O(1) ~O(n) | O(1) | O(1) | O(1) | Hash Table + Linked List |
| IdentityHashMap | O(1) ~O(n) | O(1) | O(1) | O(h / n) | Array |
| WeakHashMap | O(1) ~O(n) | O(1) | O(1) | O(h / n) | Hash Table |
| EnumMap | O(1) ~O(n) | O(1) | O(1) | O(1) | Array |
| TreeMap | O(log n) | O(log n) | O(log n) | O(log n) | Red-black tree |
| ConcurrentHashMap | O(1) ~O(n) | O(1) | O(1) | O(h / n) | Hash Tables |
| ConcurrentSkipListMap | O(1) ~O(n) | O(log n) | O(log n) | O(1) | Skip List |