Time Complexity of Java Collection Operations — The Cheat Sheet

Memorize these five rows because they show up in every Java interview.

ArrayList

• get(i): O(1)
• add(e) append: amortized O(1) — occasional resize is O(n)
• add(i, e) middle: O(n) — shift
• remove(i): O(n) — shift
• contains: O(n) — linear scan

LinkedList

• get(i): O(n) — must walk; common trap
• addFirst / addLast: O(1)
• remove first / last: O(1)
• contains: O(n)
• Almost always wrong choice in modern Java
• ArrayDeque beats it for deque ops

ArrayDeque — modern Stack/Queue replacement

• offerFirst, offerLast, pollFirst, pollLast: O(1) amortized
• peekFirst, peekLast: O(1)
• contains: O(n)
• Use instead of Stack (legacy, synchronized, slow)

HashMap / HashSet / LinkedHashMap

• get, put, remove, contains: O(1) average
• Worst case: O(log n) since Java 8 (treeification at 8 entries per bucket)
• Worst case O(n) pre-Java 8

TreeMap / TreeSet

• All ops: O(log n) guaranteed (red-black tree)
• Range queries (subMap, headMap, ceilingKey, floorKey): O(log n)
• Use for sorted iteration or range queries

LinkedHashMap

• Same O(1) as HashMap
• Preserves insertion order (default) OR access-order (useful for LRU cache)
• Small memory overhead for linked list

PriorityQueue (binary heap)

• offer: O(log n) — sift up
• poll: O(log n) — sift down
• peek: O(1)
• contains: O(n) — NOT O(log n); common trap
• remove(element): O(n)
• Default min-heap; for max-heap use Comparator.reverseOrder()

Legacy — don't use

• Stack: synchronized, slow; use ArrayDeque
• Vector: synchronized, slow; use ArrayList
• Hashtable: synchronized; use ConcurrentHashMap

Common traps

1. LinkedList.get(i) is O(n)

• Must walk the links
• Never use LinkedList for indexed access

2. PriorityQueue.contains is O(n)

• No hash index
• If you need efficient contains, maintain a separate HashMap

3. ArrayList.add(0, e) is O(n)

• Shifts everything right
• Use ArrayDeque if you need front-insertion

4. HashMap.get() is not always O(1)

• O(1) average, O(log n) worst case
• Depends on hash distribution and treeification

5. ArrayList.remove(i) is O(n)

• Shifts all subsequent elements left

Decision matrix

Indexed sequential data

• Random access → ArrayList
• Front/back ops → ArrayDeque

Key→value lookup

• Unordered fast → HashMap
• Sorted / range → TreeMap
• Insertion/access order → LinkedHashMap
• Thread-safe → ConcurrentHashMap
• Enum keys → EnumMap

Set membership

• Fast contains → HashSet
• Sorted iteration → TreeSet
• Insertion order → LinkedHashSet
• Enum elements → EnumSet (bitset, very fast)

Stack / Queue / Deque

• LIFO stack → ArrayDeque (push/pop)
• FIFO queue → ArrayDeque
• Priority → PriorityQueue
• Concurrent queue → ConcurrentLinkedDeque, LinkedBlockingQueue

Immutable snapshots (Java 9+)

• List.of, Set.of, Map.of
• Compact, fast, throw on mutation, throw NPE on null

Amortized O(1)

• ArrayList.add and HashMap.put
• Single op can be O(n) (resize)
• Over many ops, averages to O(1)
• Spread the occasional big cost across many small ones

Recommendation: Memorize the table — this is the most common Java interview question category. For each operation, know both average and worst case for hash-based structures, and amortized for resize-based. The big decisions: `ArrayList` for indexed, `ArrayDeque` for stack/queue/deque, `HashMap` for O(1) lookup, `TreeMap` for sorted/range, `LinkedHashMap` for insertion-order or LRU, `PriorityQueue` for always-smallest. Avoid `LinkedList` in modern code — ArrayDeque wins for deque ops, ArrayList for indexed. Avoid `Stack`, `Vector`, `Hashtable` — legacy synchronized; use the modern non-synchronized versions. Remember the three classic traps: `LinkedList.get(i)` is O(n), `PriorityQueue.contains` is O(n) (not log n), `ArrayList.add(0, e)` is O(n). In interviews, always qualify hash structures: 'O(1) average, O(log n) worst case since Java 8' — shows depth and precision.