13. Collections Comparison Cheat Sheet

List Choices

ArrayList uses a resizable array. It is strong for indexed reads and appending. Insertions/removals in the middle require shifting.

LinkedList uses nodes. It can be useful for frequent additions/removals near known nodes or ends, but random access is slow and memory overhead is higher.

Map Choices

HashMap is unsynchronized, usually fast, and allows one null key plus multiple null values.

Hashtable is legacy, synchronized, slower, and does not allow null keys or null values.

Stack and Queue

Stack is LIFO. Queue is FIFO. In modern Java, ArrayDeque is usually preferred for stack/queue behavior over legacy Stack.

Common Methods

size(), isEmpty(), clear(), contains(), add(), remove(), get(), put(), keySet(), values(), and entrySet() are the everyday interview methods to know.

Collections Code Examples

HashMap Frequency Count

Map<String, Integer> counts = new HashMap<>();

for (String word : words) {
    counts.put(word, counts.getOrDefault(word, 0) + 1);
}

ArrayDeque as Stack and Queue

Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
System.out.println(stack.pop()); // B

Deque<String> queue = new ArrayDeque<>();
queue.offer("A");
queue.offer("B");
System.out.println(queue.poll()); // A

Sort Map by Value

List<Map.Entry<String, Integer>> entries =
        new ArrayList<>(counts.entrySet());

entries.sort(Map.Entry.<String, Integer>comparingByValue().reversed());

for (Map.Entry<String, Integer> entry : entries) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

Interview Scenario Practice

Scenario 1: BFS Frontier

Scenario: You are implementing BFS on a graph and need to process nodes in arrival order.

Strong answer: Use ArrayDeque as a queue with offer() and poll().

Why it works: BFS needs FIFO ordering, and ArrayDeque is a modern efficient queue implementation.

Common mistake: Using legacy Stack or assuming PriorityQueue preserves insertion order.

Scenario 2: Vote Counting

Scenario: You need to count votes by candidate name.

Strong answer: Use a HashMap<String, Integer> and update counts with getOrDefault, merge, or compute.

Why it works: A map gives direct key-to-count lookup and avoids nested loops.

Common mistake: Using a list and scanning it for every vote, which turns a simple frequency count into slower repeated work.

Scenario 3: Sort Candidates by Score

Scenario: After counting votes, you need candidates sorted by score descending.

Strong answer: Copy map.entrySet() into a list and sort with Map.Entry.comparingByValue().reversed(). Add a tie-breaker by key if the result must be deterministic.

Why it works: HashMap is optimized for lookup, not sorted iteration.

Common mistake: Expecting HashMap iteration order to reflect score order.