Java Collections Cheat Sheet
Pick a collection
index access ............ ArrayList
stack / queue / deque ... ArrayDeque
heap .................... PriorityQueue (reverseOrder() = max-heap)
unique, fast ............ HashSet sorted ... TreeSet
key→value, fast ......... HashMap sorted ... TreeMap
insertion order / LRU ... LinkedHashSet / LinkedHashMap
threads ................. ConcurrentHashMap, CopyOnWriteArrayList
Complexity
ArrayList get O(1) add O(1)* insert/remove middle O(n) contains O(n)
HashMap/Set get/put/contains O(1) avg
TreeMap/Set get/put/floor/ceiling O(log n)
PriorityQueue offer/poll O(log n), peek O(1)
ArrayDeque push/pop/offer/poll O(1)
Must-know methods
map.getOrDefault(k, 0); map.merge(k, 1, Integer::sum);
map.computeIfAbsent(k, x -> new ArrayList<>()).add(v);
treeSet.floor(x); treeSet.ceiling(x); treeMap.floorKey(x);
deque.offerFirst/offerLast/pollFirst/pollLast/peekFirst/peekLast
list.removeIf(...); list.sort(Comparator.comparing(...));
Full Java Collections documentation