41. Java Collections for DSA

[!NOTE] In DSA interviews and competitive programming, choosing the right data structure is often more important than choosing the right algorithm. This chapter is your comprehensive reference for Java's built-in data structures, their time complexities, and exactly when to reach for each one.

The Collections Framework Hierarchy

Java's Collections Framework is a unified architecture for representing and manipulating groups of data. Everything descends from two root interfaces:

                    Iterable
                       |
                   Collection
                  /    |     \
               List   Set   Queue
              /   \    |  \     \
      ArrayList  LinkedList  HashSet  TreeSet  PriorityQueue  ArrayDeque
                              |
                        LinkedHashSet

                      Map (separate hierarchy)
                     /    |        \
                HashMap  TreeMap  LinkedHashMap
  

Key insight: Map does NOT extend Collection. It's a completely separate inheritance tree because maps store key-value pairs, not individual elements.

The Big-O Cheat Sheet

This is the single most important table for DSA. Memorize it.

List Implementations

DSA verdict: Use ArrayList 99% of the time. LinkedList is only better when you're doing heavy insert/remove at the head/tail AND never doing random access.

Set Implementations

Map Implementations

Queue/Stack Implementations

PriorityQueue (Min-Heap / Max-Heap)

The PriorityQueue is the single most important DSA collection. It's a binary heap that always gives you the minimum (or maximum) element in O(1) peek and O(log n) insert/remove.

// Min-Heap (default) — smallest element first
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(30);
minHeap.offer(10);
minHeap.offer(20);
minHeap.poll();  // Returns 10 (smallest)
minHeap.peek();  // Returns 20 (next smallest)

// Max-Heap — largest element first
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(30);
maxHeap.offer(10);
maxHeap.offer(20);
maxHeap.poll();  // Returns 30 (largest)

// Custom comparator — sort by frequency, then alphabetically
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
    if (a[1] != b[1]) return b[1] - a[1]; // Higher frequency first
    return a[0] - b[0]; // Then by value ascending
});
  

DSA use cases: Kth largest/smallest element, merge K sorted lists, Dijkstra's shortest path, task scheduling, median finding (two heaps), top-K frequent elements.

ArrayDeque (Stack + Queue)

ArrayDeque is the universal replacement for both Stack and LinkedList when used as a stack or queue. It's faster than both because it uses a resizable array with no node overhead.

// As a Stack (LIFO) — use push/pop/peek
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);    // [1]
stack.push(2);    // [2, 1]
stack.push(3);    // [3, 2, 1]
stack.pop();      // Returns 3
stack.peek();     // Returns 2

// As a Queue (FIFO) — use offer/poll/peek
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);   // [1]
queue.offer(2);   // [1, 2]
queue.offer(3);   // [1, 2, 3]
queue.poll();     // Returns 1
queue.peek();     // Returns 2
  

[!CAUTION] Never use java.util.Stack in production or interviews. It extends Vector (synchronized, slow) and is a legacy class. Always use ArrayDeque instead. Interviewers will notice.

DSA use cases: BFS (queue), DFS (stack), parenthesis matching, monotonic stack, sliding window maximum, backtracking.

TreeMap & TreeSet (Sorted Structures)

When you need elements automatically sorted and want to do range queries, floor/ceiling lookups, or find the next greater/smaller element in O(log n) — use TreeMap or TreeSet.

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "ten");
map.put(20, "twenty");
map.put(30, "thirty");

map.firstKey();        // 10 (smallest key)
map.lastKey();         // 30 (largest key)
map.floorKey(25);      // 20 (largest key ≤ 25)
map.ceilingKey(25);    // 30 (smallest key ≥ 25)
map.subMap(10, 30);    // {10=ten, 20=twenty} (range query, end exclusive)

TreeSet<Integer> set = new TreeSet<>();
set.add(5); set.add(15); set.add(25);
set.floor(20);         // 15
set.ceiling(20);       // 25
set.headSet(20);       // [5, 15] (elements < 20)
  

DSA use cases: Interval problems, skyline problem, ordered statistics, range queries, calendar scheduling, finding closest values.

HashMap — The DSA Workhorse

You already learned HashMap in Chapter 26. Here's the DSA-specific perspective:

// Frequency counting (THE most common DSA pattern)
Map<Character, Integer> freq = new HashMap<>();
for (char c : str.toCharArray()) {
    freq.put(c, freq.getOrDefault(c, 0) + 1);
}

// Two Sum pattern — store complement
Map<Integer, Integer> seen = new HashMap<>(); // value → index
for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    if (seen.containsKey(complement)) {
        return new int[]{seen.get(complement), i};
    }
    seen.put(nums[i], i);
}

// Group Anagrams pattern — key = sorted string
Map<String, List<String>> groups = new HashMap<>();
for (String word : words) {
    char[] chars = word.toCharArray();
    Arrays.sort(chars);
    String key = new String(chars);
    groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
}
  

DSA use cases: Two Sum, frequency counting, anagram grouping, substring problems, graph adjacency lists, memoization/caching.

DSA Pattern → Collection Mapping

When you see a problem pattern, reach for the right collection immediately:

Common Gotchas in DSA Interviews

1. HashMap Key Requirements

Objects used as HashMap keys must properly override hashCode() and equals(). If you use arrays as keys, they compare by reference, not content!

// WRONG — arrays use identity for equals/hashCode
Map<int[], Integer> map = new HashMap<>();
map.put(new int[]{1, 2}, 1);
map.get(new int[]{1, 2}); // Returns NULL! Different object reference.

// RIGHT — convert to String or List for content-based hashing
Map<String, Integer> map = new HashMap<>();
map.put(Arrays.toString(new int[]{1, 2}), 1);
map.get(Arrays.toString(new int[]{1, 2})); // Returns 1 ✅
  

2. PriorityQueue Is NOT Sorted Iteration

Iterating a PriorityQueue does NOT give elements in sorted order. Only poll() guarantees min/max extraction:

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(3, 1, 4, 1, 5));

// WRONG — iterator order is NOT guaranteed sorted
for (int x : pq) System.out.print(x + " "); // Could print: 1 1 4 3 5

// RIGHT — poll() extracts in sorted order
while (!pq.isEmpty()) System.out.print(pq.poll() + " "); // 1 1 3 4 5
  

3. ConcurrentModificationException

Never modify a collection while iterating it with a for-each loop. Use an Iterator with remove(), or collect items to remove separately.

// WRONG — crashes!
for (String s : list) {
    if (s.startsWith("x")) list.remove(s); // ConcurrentModificationException
}

// RIGHT — use Iterator
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().startsWith("x")) it.remove(); // Safe
}
  

4. Collections.sort() vs Arrays.sort()

Use Arrays.sort() for arrays, Collections.sort() for Lists. For primitives, Arrays.sort() uses dual-pivot quicksort (O(n log n) avg). For objects, it uses TimSort (O(n log n) guaranteed).

int[] arr = {5, 3, 1, 4, 2};
Arrays.sort(arr); // [1, 2, 3, 4, 5]

List<Integer> list = Arrays.asList(5, 3, 1, 4, 2);
Collections.sort(list); // [1, 2, 3, 4, 5]

// Custom comparator (sort descending)
Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // Sort 2D by first element
list.sort(Comparator.reverseOrder()); // [5, 4, 3, 2, 1]
  

Collections Utility Methods You Must Know

Collections.sort(list);            // Sort a List
Collections.reverse(list);         // Reverse a List
Collections.swap(list, i, j);     // Swap elements at indices i and j
Collections.frequency(list, obj); // Count occurrences of obj
Collections.min(collection);      // Find minimum element
Collections.max(collection);      // Find maximum element
Collections.unmodifiableList(list); // Return read-only view

// Initialization shortcuts
List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
Set<String> set = new HashSet<>(Set.of("a", "b", "c"));
Map<String, Integer> map = new HashMap<>(Map.of("a", 1, "b", 2));
  

[!TIP] DSA Interview Summary: When in doubt: HashMap for O(1) lookups, PriorityQueue for top-K/Kth problems, ArrayDeque for any stack/queue needs, TreeMap when you need sorted keys or floor/ceiling. Master these four and you can solve 90% of DSA problems efficiently.

Map<Integer, Integer> frequency = new HashMap<>();
for (int value : nums) {
    frequency.put(value, frequency.getOrDefault(value, 0) + 1);
}