☕ DSA Java Articles

Topics › Basics › Learn STL/Java-Collections or similar thing in your | language

Java Collections

Easy TUF ID 1217 A2Z

Java source ↗ Edit this article ↗

Problem

Every Java solution on this site is written with the Java Collections Framework: ArrayList, ArrayDeque, HashMap, TreeMap, HashSet, PriorityQueue, plus Comparator, Iterator and a sprinkle of streams. This article is a working tour of exactly those parts, with the complexities you must know by heart and the handful of traps that cost people interviews. Each construct is shown as a small method from the Java file, and main asserts every result.

If you come from C++, read STL first for the name-to-name translation; this article assumes nothing and explains the Java side on its own terms.

The hierarchy in one paragraph

Collection is the root interface for groups of elements. Below it: List (ordered, indexed, duplicates allowed), Set (no duplicates), and Queue with its two-ended refinement Deque. Map (key to value) is a separate hierarchy because a map is not a collection of single elements. Each interface has a hash-based, a tree-based and sometimes a linked implementation. The rule for choosing: program against the interface (List<Integer> list = new ArrayList<>()), pick the implementation by the operations you need and their cost.

Need Use Key costs
indexed access, append ArrayList get/set O(1), add at end amortised O(1), insert/remove in middle O(n)
stack or queue ArrayDeque push/pop/offer/poll O(1) at both ends
membership, dedup HashSet add/contains/remove O(1) average
dedup, keep insertion order LinkedHashSet same, plus predictable iteration
sorted set, floor/ceiling TreeSet all operations O(log n)
key to value lookup HashMap get/put O(1) average
sorted keys, range queries TreeMap O(log n), firstKey, floorKey, ceilingKey
repeatedly take the min/max PriorityQueue offer/poll O(log n), peek O(1)

List: ArrayList

A resizable array. The one API wart is that List<Integer> has two remove methods: remove(int index) and remove(Object value). An int argument picks the index version; wrap the value in Integer.valueOf to delete by value.

static List<Integer> listOperations() {
    List<Integer> list = new ArrayList<>();
    list.add(10);                                // [10]
    list.add(20);                                // [10, 20]
    list.add(30);                                // [10, 20, 30]
    list.add(1, 15);                             // insert at index 1      -> [10, 15, 20, 30]
    list.set(0, 5);                              // overwrite index 0      -> [5, 15, 20, 30]
    list.remove(2);                              // remove by INDEX        -> [5, 15, 30]
    list.remove(Integer.valueOf(15));            // remove by VALUE        -> [5, 30]
    list.add(30);                                // duplicates are allowed -> [5, 30, 30]
    return list;
}

Removing from a list while iterating over it with a for-each loop throws ConcurrentModificationException (the list’s iterator is fail-fast). Use the iterator’s own remove, or removeIf:

static List<Integer> removeEvens(List<Integer> input) {
    List<Integer> list = new ArrayList<>(input);
    Iterator<Integer> it = list.iterator();
    while (it.hasNext()) {
        if (it.next() % 2 == 0) it.remove();
    }
    return list;
}

static List<Integer> removeEvensWithRemoveIf(List<Integer> input) {
    List<Integer> list = new ArrayList<>(input);
    list.removeIf(v -> v % 2 == 0);
    return list;
}

Deque: ArrayDeque as stack and queue

Use the Deque interface for both. As a stack: push, pop, peek (all at the head). As a queue: offer at the tail, poll and peek at the head. pop/remove throw on an empty deque; poll/peek return null. Prefer ArrayDeque over the legacy java.util.Stack and over LinkedList: it is faster and allocates less. It does not accept null elements.

static List<Integer> dequeAsStackAndQueue() {
    Deque<Integer> stack = new ArrayDeque<>();
    Deque<Integer> queue = new ArrayDeque<>();
    for (int x = 1; x <= 3; x++) {
        stack.push(x);                           // push adds at the head
        queue.offer(x);                          // offer adds at the tail
    }
    List<Integer> order = new ArrayList<>();
    while (!stack.isEmpty()) order.add(stack.pop());    // 3, 2, 1
    while (!queue.isEmpty()) order.add(queue.poll());   // 1, 2, 3
    return order;
}

Set: HashSet, LinkedHashSet, TreeSet

All three reject duplicates; they differ in iteration order and cost. HashSet has no order. LinkedHashSet iterates in insertion order. TreeSet iterates sorted and adds the navigation methods first, last, floor (largest <= x), ceiling (smallest >= x), lower, higher, and views such as headSet(x) (everything strictly below x). The navigation methods return null when no element qualifies, which is the case to handle.

static List<String> setOperations(int[] values, int query) {
    Set<Integer> hash = new HashSet<>();
    Set<Integer> linked = new LinkedHashSet<>();
    TreeSet<Integer> tree = new TreeSet<>();
    for (int v : values) {
        hash.add(v);
        linked.add(v);
        tree.add(v);
    }
    List<String> out = new ArrayList<>();
    out.add("distinct=" + hash.size());
    out.add("insertion=" + linked);
    out.add("sorted=" + tree);
    out.add("floor(" + query + ")=" + tree.floor(query));       // largest element <= query, or null
    out.add("ceiling(" + query + ")=" + tree.ceiling(query));   // smallest element >= query, or null
    out.add("headSet(" + query + ")=" + tree.headSet(query));   // everything strictly below query
    return out;
}

For values = [5, 1, 9, 5, 3, 9] and query = 6: distinct=4, insertion=[5, 1, 9, 3], sorted=[1, 3, 5, 9], floor(6)=5, ceiling(6)=9, headSet(6)=[1, 3, 5].

Map: HashMap and TreeMap

The most used collection in interview code is HashMap<K, V> as a frequency table. merge(key, 1, Integer::sum) increments a count or creates it, replacing the clumsy put(key, getOrDefault(key, 0) + 1). To rank keys by frequency, copy entrySet() into a list and sort it with a comparator.

static List<String> wordsByFrequency(String[] words) {
    Map<String, Integer> freq = new HashMap<>();
    for (String w : words) freq.merge(w, 1, Integer::sum);     // freq[w]++ in one call
    List<Map.Entry<String, Integer>> entries = new ArrayList<>(freq.entrySet());
    entries.sort((a, b) -> {
        if (!a.getValue().equals(b.getValue())) return b.getValue() - a.getValue();   // higher count first
        return a.getKey().compareTo(b.getKey());                                    // then alphabetical
    });
    List<String> out = new ArrayList<>();
    for (Map.Entry<String, Integer> e : entries) out.add(e.getKey() + "=" + e.getValue());
    return out;
}

TreeMap keeps keys sorted and answers “the largest key not above x” (floorKey) or “the smallest key not below x” (ceilingKey) in O(log n), which is what you need for interval and scheduling problems. firstKey/lastKey throw on an empty map, so guard them (or use firstEntry, which returns null).

static List<String> treeMapOperations(int[] keys, int query) {
    TreeMap<Integer, String> map = new TreeMap<>();
    for (int k : keys) map.put(k, "v" + k);                     // put overwrites an existing key
    List<String> out = new ArrayList<>();
    out.add("size=" + map.size());
    out.add("first=" + (map.isEmpty() ? null : map.firstKey()));
    out.add("last=" + (map.isEmpty() ? null : map.lastKey()));
    out.add("floorKey(" + query + ")=" + map.floorKey(query));
    out.add("ceilingKey(" + query + ")=" + map.ceilingKey(query));
    out.add("get(" + query + ")=" + map.getOrDefault(query, "absent"));
    return out;
}

Keys of a HashMap must implement equals and hashCode consistently. String, boxed numbers and records do; a hand-written class must override both or every lookup misses.

PriorityQueue

A binary min-heap: poll returns the smallest element. For a max-heap pass Collections.reverseOrder() or a reversed comparator. The classic use is the top-k pattern: keep a min-heap of size k; whenever it grows past k, evict the smallest. What survives is the k largest, in O(n log k) instead of sorting everything.

static List<Integer> kLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int v : nums) {
        minHeap.offer(v);
        if (minHeap.size() > k) minHeap.poll();  // evict the smallest so only the k largest survive
    }
    List<Integer> out = new ArrayList<>(minHeap);
    out.sort(Collections.reverseOrder());
    return out;
}

Iterating a PriorityQueue does not visit elements in sorted order; only repeated poll does. That is why the result above is copied out and sorted.

Comparator

Sorting by several keys is done by chaining: Comparator.comparingInt(Student::marks).reversed().thenComparing(Student::name). Use method references rather than lambdas in the first link; Comparator.comparing(s -> s.marks()) cannot infer the type of s once .reversed() is appended, while Student::marks can. Records are ideal here because their accessors are exactly such method references.

static List<String> rankStudents(List<Student> students) {
    List<Student> sorted = new ArrayList<>(students);
    sorted.sort(Comparator.comparingInt(Student::marks).reversed().thenComparing(Student::name));
    List<String> out = new ArrayList<>();
    for (Student s : sorted) out.add(s.name() + ":" + s.marks());
    return out;
}

Collections.sort and List.sort are stable, so equal keys keep their input order; Arrays.sort on primitives is not stable, which rarely matters for primitives.

Streams, briefly

Streams are a declarative pipeline over a collection or array. They are concise for sums, distinct values and grouping, and slower than a plain loop in hot code. Arrays.stream(int[]) is an IntStream; boxed() turns it into Stream<Integer> for collectors.

static String streamSummary(int[] nums) {
    int sum = Arrays.stream(nums).sum();
    List<Integer> distinctSorted = Arrays.stream(nums).distinct().sorted().boxed().toList();
    Map<Boolean, Long> evenOdd = Arrays.stream(nums).boxed()
            .collect(Collectors.partitioningBy(v -> v % 2 == 0, Collectors.counting()));
    return "sum=" + sum + " distinct=" + distinctSorted + " even=" + evenOdd.get(true) + " odd=" + evenOdd.get(false);
}

The pitfalls, demonstrated

The method below performs each classic mistake deliberately and records what happens, so the tests pin the behaviour down.

static List<String> pitfalls() {
    List<String> notes = new ArrayList<>();
    List<Integer> nums = new ArrayList<>(List.of(1, 2, 3));
    nums.remove(1);                                      // index 1 -> [1, 3]
    notes.add("remove(int) -> " + nums);
    nums.remove(Integer.valueOf(1));                     // value 1 -> [3]
    notes.add("remove(Object) -> " + nums);

    List<Integer> fixed = Arrays.asList(1, 2, 3);        // a view over the array: set works, add does not
    fixed.set(0, 9);
    try {
        fixed.add(4);
        notes.add("asList add -> ok");
    } catch (UnsupportedOperationException e) {
        notes.add("asList add -> UnsupportedOperationException");
    }

    List<Integer> immutable = List.of(1, 2, 3);          // fully immutable
    try {
        immutable.set(0, 9);
        notes.add("List.of set -> ok");
    } catch (UnsupportedOperationException e) {
        notes.add("List.of set -> UnsupportedOperationException");
    }

    Integer a = 127, b = 127, c = 1000, d = 1000;
    notes.add("127 == 127 -> " + (a == b));              // true only because small values are cached
    notes.add("1000.equals(1000) -> " + c.equals(d));    // always compare boxed values with equals

    try {
        for (Integer v : nums) {
            if (v == 3) nums.add(4);                     // structural change during a for-each
        }
        notes.add("modify in for-each -> ok");
    } catch (ConcurrentModificationException e) {
        notes.add("modify in for-each -> ConcurrentModificationException");
    }
    return notes;
}

Edge cases and pitfalls