0%
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 |