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 |