Lesson 0.4 · Java for DSA

The Collections Toolkit

ArrayList, HashMap, HashSet, ArrayDeque and PriorityQueue: what each is for, the methods you'll use, how fast they are, and the boxing traps.

20 min

Think of it like this

Collections are tools in a toolbox. A list is a numbered shopping list, a map is a phone book (name to number), a set is a guest list (each name once), a deque is a stack of plates that also works as a queue, and a priority queue is a hospital waiting room where the most urgent patient is always next.

1.Which tool for which job

ArrayList: a growable array. Get or set by index in O(1); add at the end in O(1) on average; insert or remove in the middle in O(n).

HashMap and HashSet: look up, insert and remove by key in O(1) on average. No order.

ArrayDeque: add or remove at either end in O(1). Use it as a stack (push, pop, peek) or a queue (offer, poll, peek). Prefer it over the old Stack class.

PriorityQueue: always gives you the smallest element (or largest, with a reversed comparator). Add and remove in O(log n), peek in O(1).

Toolkit.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(List.of(3, 1, 2));
        list.add(5);
        System.out.println(list.get(0) + " " + list.size());     // 3 4

        Map<String, Integer> count = new HashMap<>();
        for (String w : "a b a c a".split(" ")) count.merge(w, 1, Integer::sum);
        System.out.println(count.get("a") + " " + count.getOrDefault("z", 0));  // 3 0

        Set<Integer> seen = new HashSet<>();
        System.out.println(seen.add(4) + " " + seen.add(4));   // true false

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1); stack.push(2);
        System.out.println(stack.pop());                       // 2 (last in, first out)

        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(1); queue.offer(2);
        System.out.println(queue.poll());                      // 1 (first in, first out)

        PriorityQueue<Integer> minHeap = new PriorityQueue<>(List.of(5, 1, 3));
        System.out.println(minHeap.poll());                    // 1
    }
}

Output

3 4
3 0
true false
2
1
1

2.Boxing: Integer is not int

Collections hold objects, so int values are "boxed" into Integer objects automatically. Comparing two Integer objects with == compares references. Java caches small values (−128 to 127), so == happens to work for them and then fails for larger numbers, which makes the bug hard to spot.

Compare boxed values with .equals(), or unbox them first (int a = map.get(k);). Also, map.get(k) returns null for a missing key, and unboxing null throws a NullPointerException; use getOrDefault.

Boxing.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Integer a = 127, b = 127, c = 1000, d = 1000;
        System.out.println(a == b);         // true  (cached)
        System.out.println(c == d);         // false (different objects)
        System.out.println(c.equals(d));    // true
        Map<String, Integer> m = new HashMap<>();
        System.out.println(m.getOrDefault("x", 0));   // 0, no exception
    }
}

Output

true
false
true
0

Quick check

Your code compares map.get(a) == map.get(b) to check two counts are equal. It passes small tests and fails on large inputs. Why?

3.Iterating maps

Loop over map.entrySet() to get each key and value together, map.keySet() for keys and map.values() for values. A HashMap has no guaranteed order; use LinkedHashMap for insertion order or TreeMap for sorted keys.

MapLoop.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> price = new TreeMap<>(Map.of("tea", 20, "coffee", 50, "lassi", 40));
        for (Map.Entry<String, Integer> e : price.entrySet()) {
            System.out.println(e.getKey() + " -> " + e.getValue());
        }
    }
}

Output

coffee -> 50
lassi -> 40
tea -> 20

Remember

List for order and index access, Map for key lookups, Set for membership, Deque for stacks and queues, PriorityQueue for "always the smallest".
Use ArrayDeque for stacks and queues.
Compare Integer objects with equals, and use getOrDefault for missing keys.
HashMap order is unpredictable; use LinkedHashMap or TreeMap when order matters.

Common mistakes

Comparing boxed Integer values with ==.
Unboxing map.get(missingKey) and getting a NullPointerException.
Removing from a list while looping over it with for-each (ConcurrentModificationException).
Using list.remove(1) when you meant to remove the value 1 (it removes index 1; use list.remove(Integer.valueOf(1))).

Words used in this lesson

Collection: A Java object that holds a group of elements, like a list or set.
Boxing: Automatically wrapping a primitive (int) in its object type (Integer).
Generic type: The type in angle brackets, as in List<Integer>, saying what the collection holds.
Amortised O(1): Usually instant, with an occasional slow step, so the average stays constant.

Command Palette

The Collections Toolkit

1.Which tool for which job

2.Boxing: Integer is not int

3.Iterating maps