Skip to content
notes.vinhnq.com

Search

Data Structures & AlgorithmsJunior19 min read

Java Collections: List, Set and Map

Review 13 cards
On this page

Data structures series: 1. Arrays, linked lists, stacks, queues · 2. List, Set, Map · 3. TreeMap, Comparator, iterators · 4. Inside ArrayList and HashMap

Part 1 covered arrays, linked lists, stacks and queues as concepts; this part is the API every Java codebase uses: the Java Collections Framework. By the end you can pick the right List/Set/Map/Queue, avoid the traps in ArrayList, HashSet and HashMap, and use the Java 8 methods such as merge and computeIfAbsent. Ordered data (TreeSet, TreeMap, Comparator) and iterators are in part 3; how ArrayList grows and how HashMap hashes and resizes is in part 4.

1. The Java Collections Framework

Key idea: Java has two container families: a Collection holds a group of elements, a Map holds key/value pairs. Pick the interface by the property your data needs: order, uniqueness, or lookup by key.

  • Collection: a group of elements (List, Set, Queue/Deque).
  • Map: key/value pairs. Map does not extend Collection.
flowchart TB
  Iterable --> Collection
  Collection --> List
  Collection --> Set
  Collection --> Queue
  Queue --> Deque
  List --> ArrayList
  List --> LinkedList
  List --> Vector --> Stack
  Deque --> ArrayDeque
  Deque --> LinkedList
  Queue --> PriorityQueue
  Set --> HashSet --> LinkedHashSet
  Set --> SortedSet --> TreeSet
  Map --> HashMap --> LinkedHashMap
  Map --> SortedMap --> TreeMap
Interface What it guarantees Use it when Real-world example Usual class
List Ordered, indexed, duplicates allowed You need insertion order or access by position Students in sign-up order ArrayList
Set No duplicates (by equals or by compareTo) You need uniqueness or “have I seen this?” Registered emails, employee IDs HashSet, LinkedHashSet, TreeSet
Map Key/value pairs, unique keys You look things up by key Phone book number → name, cart product ID → quantity HashMap, LinkedHashMap, TreeMap
Queue/Deque Removal in FIFO, LIFO or priority order You process items one at a time Outgoing email queue, “Back” history ArrayDeque, PriorityQueue

A good habit: declare variables with the interface (List<String> names = new ArrayList<>()), not the concrete class. Everything after that line depends only on the List contract, so switching implementations (say, to CopyOnWriteArrayList) is a one-line change.

1.1. Collection and List

Key idea: Collection is the root interface (add, remove, contains, size…); List adds ordering, allows duplicates and adds positional methods. The bulk operations (addAll, removeAll, retainAll…) do set algebra, but they modify the collection you call them on.

  • Collection: add, remove, contains, size, isEmpty, iterator, stream…
  • List adds: get(i), set(i, e), add(i, e), remove(i), indexOf, lastIndexOf, subList.

Bulk operations are methods that take a whole other collection. The first four return a boolean meaning “did this collection change”, not “did it succeed”:

Method What it does Set-theory equivalent
addAll(c) Adds every element of c Union (for a Set)
containsAll(c) Does it contain every element of c (read-only) Subset check
removeAll(c) Removes every element that is in c Difference A \ B
retainAll(c) Keeps only the elements that are in c Intersection A ∩ B
clear() Removes everything
toArray() / toArray(T[]) Copies into an array
equals(o) Compares content per the sub-interface’s contract
List<String> backend  = new ArrayList<>(List.of("java", "sql", "git", "docker"));
List<String> frontend = List.of("js", "git", "docker", "css");

List<String> common = new ArrayList<>(backend);
common.retainAll(frontend);                         // true, common = [git, docker]

List<String> onlyBackend = new ArrayList<>(backend);
onlyBackend.removeAll(new HashSet<>(frontend));     // [java, sql]

backend.containsAll(List.of("java", "git"));        // true

Object[] raw     = backend.toArray();                // Object[], can't be cast to String[]
String[] typed   = backend.toArray(new String[0]);   // String[]
String[] typed11 = backend.toArray(String[]::new);   // Java 11+, shorter

new ArrayList<>(List.of(1, 2)).equals(new LinkedList<>(List.of(1, 2))); // true: List compares elements in order
List.of(1, 2).equals(List.of(2, 1));                                     // false

Copy first if you need the original, as above. Calling retainAll on a List.of(...) (an immutable list, one you can’t modify) throws UnsupportedOperationException.

1.2. ArrayList

Key idea: ArrayList is a dynamic array (an array that grows itself when full) implementing List. There are four ways to iterate; to remove while iterating, use only iterator.remove() or removeIf.

List<String> names = new ArrayList<>(List.of("An", "Binh", "Chi"));

for (int i = 0; i < names.size(); i++) {        // 1. by index
    System.out.println(names.get(i));
}
for (String name : names) {                      // 2. enhanced for
    System.out.println(name);
}
Iterator<String> it = names.iterator();          // 3. Iterator
while (it.hasNext()) {
    String name = it.next();
    if (name.startsWith("B")) it.remove();       // the safe way to remove while iterating
}
names.forEach(System.out::println);              // 4. forEach + lambda (Java 8+)

1.3. The Collections utility class

Key idea: java.util.Collections (with an s) is a static toolbox: sort, reverse, shuffle, min/max, count, and wrap a list as read-only or synchronized.

List<Integer> nums = new ArrayList<>(List.of(5, 3, 8, 1, 3));
Collections.sort(nums);                         // [1, 3, 3, 5, 8]
Collections.reverse(nums);                      // [8, 5, 3, 3, 1]
Collections.shuffle(nums);
int max = Collections.max(nums);                // 8
int freq = Collections.frequency(nums, 3);      // 2
Collections.swap(nums, 0, 1);
List<Integer> readOnly = Collections.unmodifiableList(nums);
List<Integer> syncList = Collections.synchronizedList(new ArrayList<>());
List<String> fives = Collections.nCopies(5, "x");
More methods: reverseOrder, binarySearch, copy, fill, disjoint
List<Integer> nums = new ArrayList<>(List.of(5, 1, 4, 2, 3));
Collections.sort(nums, Collections.reverseOrder());   // [5, 4, 3, 2, 1], sort with a Comparator
int min = Collections.min(nums);                      // 1 (min/max also take a Comparator)
String shortest = Collections.min(List.of("pear", "fig", "banana"),
                                  Comparator.comparing(String::length)); // "fig"

Collections.sort(nums);                               // [1, 2, 3, 4, 5]
int idx = Collections.binarySearch(nums, 4);          // 3; the list must already be sorted
int miss = Collections.binarySearch(nums, 9);         // -6 = -(insertion point) - 1

List<Integer> dest = new ArrayList<>(Collections.nCopies(nums.size(), 0));
Collections.copy(dest, nums);                         // dest = [1, 2, 3, 4, 5]
Collections.fill(dest, -1);                           // [-1, -1, -1, -1, -1]
boolean noCommon = Collections.disjoint(List.of(1, 2), Set.of(3, 4)); // true: no element in common
  • Collections.sort(list, comparator) is the same as list.sort(comparator); since Java 8 prefer the latter. Under the hood it’s TimSort, which is stable (equal elements keep their order); see merge sort and quick sort.
  • Collections.reverseOrder() returns a Comparator that reverses natural ordering; reverseOrder(cmp) reverses an existing comparator. Don’t confuse it with Collections.reverse(list), which flips element positions.
  • Collections.binarySearch is only correct on a list sorted in the same order; the algorithm is in binary search.

1.4. The Stack class and Queue

Key idea: java.util.Stack (push, pop, peek, empty, search) is a legacy class from Java 1.0 that extends Vector. Queue is an interface; common implementations are ArrayDeque, LinkedList and PriorityQueue.

Stack<Integer> st = new Stack<>();
st.push(1); st.push(2); st.push(3);   // 3 is on top
st.search(3);   // 1  (the top is distance 1, counting from 1)
st.search(1);   // 3  (the bottom)
st.search(9);   // -1 (absent)
st.empty();     // false, the legacy name from Java 1.0
st.isEmpty();   // false, inherited from Vector, same meaning
  • Queue: ArrayDeque, LinkedList, PriorityQueue (removes by priority, not FIFO), and the BlockingQueue family for concurrency.

1.5. Set and HashSet

Key idea: a Set never holds two elements with e1.equals(e2). HashSet uses hashCode to pick a bucket (a slot in the hash table) and equals to decide duplicates, so the class must override both.

// a record generates equals/hashCode from all its components
record Email(String value) {}

Set<Email> emails = new HashSet<>();
emails.add(new Email("a@x.com"));
emails.add(new Email("a@x.com"));
System.out.println(emails.size()); // 1

What set.add(x) does. A HashSet is really a HashMap that only uses the keys, so add goes through the four steps of HashMap.put:

  1. Call x.hashCode() to get an integer.
  2. Turn it into a bucket. If the bucket is empty, put x there and you’re done.
  3. If the bucket already holds elements (a collision), walk through them.
  4. Call equals against each one. If any equals x, nothing is added (add returns false); otherwise x joins the bucket.

Some beginner material claims that without hashCode “every element ends up in one bucket”. That’s wrong: Object’s default hashCode is based on identity and spreads objects out nicely. The real bug is that two objects that are equal by equals get different hashes, land in different buckets, and the set keeps both. The hash table details (bit mixing, treeification, resizing) are in part 4.

HashSet LinkedHashSet TreeSet
Inside Hash table Hash table + doubly linked list Red-black tree
Iteration order Not guaranteed Insertion order Ascending by compareTo/comparator
Duplicates decided by hashCode + equals hashCode + equals compareTo/compare
null element One One No (natural ordering throws NullPointerException)
add/contains/remove O(1) average O(1) average O(log n)

Default to HashSet; use LinkedHashSet when output must follow insertion order; use TreeSet when you need sorting or questions like “smallest element above x” (see part 3).

1.6. Map and HashMap

Key idea: a Map stores key/value pairs with unique keys and fetches a value by key very quickly; HashMap is the most used implementation. Since Java 8, getOrDefault, putIfAbsent, merge, compute and computeIfAbsent replace the “get, check for null, then put” dance.

Key methods: put, get, getOrDefault, containsKey, remove, keySet, values, entrySet, putIfAbsent, merge, computeIfAbsent. How HashMap works inside (buckets, hashing, treeification, resizing) is in part 4.

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

stock.getOrDefault("apple", 0);              // 0; does NOT write anything into the map
stock.putIfAbsent("apple", 10);              // puts only if the key is absent (or mapped to null)
stock.merge("apple", 5, Integer::sum);       // present, so add: apple=15
stock.merge("pear", 3, Integer::sum);        // absent, so put 3
stock.compute("apple", (k, v) -> v == null ? 1 : v * 2);   // recompute from the old value

// Group by key (a multimap) without any if
Map<String, List<String>> byDept = new HashMap<>();
byDept.computeIfAbsent("dev", k -> new ArrayList<>()).add("An");
byDept.computeIfAbsent("dev", k -> new ArrayList<>()).add("Binh");   // {dev=[An, Binh]}

// Iterate: entrySet gives key and value together, with no extra get per element
for (Map.Entry<String, Integer> e : stock.entrySet()) {
    System.out.println(e.getKey() + " = " + e.getValue());
}
stock.entrySet().removeIf(e -> e.getValue() == 0);   // safe removal while iterating

Three details people miss:

  • A merge/compute/computeIfPresent function that returns null removes the entry: merge("pear", -3, (a, b) -> a + b == 0 ? null : a + b) removes pear once it reaches 0.
  • Iterating keySet() and calling get(key) hashes every key twice; on a TreeMap it adds another O(log n) lookup. Use entrySet() or forEach((k, v) -> ...).
  • The function passed to computeIfAbsent must not modify the same map. Memoizing a recursive Fibonacci with memo.computeIfAbsent(n, k -> fib(k - 1) + fib(k - 2)) throws ConcurrentModificationException on a HashMap since Java 9 (on a ConcurrentHashMap it may hang or throw IllegalStateException). Compute the value first, then put it.

Exercises

Exercise 1: Manage a list of numbers with ArrayList

Task: a program that lets the user add, update, delete and view a collection of numbers.

Solution to Exercise 1
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class NumberManager {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        Scanner in = new Scanner(System.in);
        while (true) {
            System.out.print("1-Add 2-Update 3-Delete 4-Show 0-Exit: ");
            int choice = in.nextInt();
            switch (choice) {
                case 1 -> {
                    System.out.print("Value: ");
                    numbers.add(in.nextInt());
                }
                case 2 -> {
                    System.out.print("Index and new value: ");
                    int idx = in.nextInt(), val = in.nextInt();
                    if (idx >= 0 && idx < numbers.size()) numbers.set(idx, val);
                    else System.out.println("Invalid index");
                }
                case 3 -> {
                    System.out.print("Value to delete: ");
                    // box it so we call remove(Object), not remove(int index)
                    boolean removed = numbers.remove(Integer.valueOf(in.nextInt()));
                    System.out.println(removed ? "Deleted" : "Not found");
                }
                case 4 -> System.out.println(numbers);
                case 0 -> { return; }
                default -> System.out.println("Unknown option");
            }
        }
    }
}

Exercise 2: Count word frequency with HashMap

Task: read a paragraph, count how many times each word appears and print the result.

Solution to Exercise 2
static Map<String, Integer> countWords(String text) {
    Map<String, Integer> counts = new TreeMap<>();      // TreeMap so the output is alphabetical
    for (String word : text.toLowerCase().split("[^\\p{L}\\p{N}]+")) {
        if (word.isEmpty()) continue;
        counts.merge(word, 1, Integer::sum);           // absent -> 1, present -> +1
    }
    return counts;
}
// "Java is fun. Java, is it? fun fun" -> {fun=3, is=2, it=1, java=2}
  • Normalize case; split on anything that isn’t a letter or digit (\p{L} also matches accented letters).
  • Use merge instead of a containsKey + put pair.
  • If you only need counts and not ordering, HashMap is faster. With streams: Collectors.groupingBy(w -> w, Collectors.counting()).

Exercise 3: Count distinct values with HashSet

Task: count how many different values a sequence contains, e.g. 1, 2, 2, 3, 4, 5, 4 has 5 distinct numbers.

Solution to Exercise 3
static int countDistinct(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int n : nums) seen.add(n);   // duplicate adds are ignored
    return seen.size();
}
// or: Arrays.stream(nums).distinct().count()

O(n) time, O(n) extra memory. If extra memory isn’t allowed, sort and count how often the value changes: O(n log n).

Exercise 4: ArrayList<Student> by index and HashSet<Product> by ID

Task (paraphrased), two small exercises from the Hỏi Dân IT material:

  • (a) A Student(name, age) record printed as Name: <name>, Age: <age>. Add three students to an ArrayList and print; insert one at index 1 and print; remove the student at index 0 and print.
  • (b) A Product(id, name, price) class with getters/setters and overridden toString, equals and hashCode. Add five products to a HashSet, one of them with a duplicate ID but a different name/price and one a full duplicate; print the set; then remove the product with ID 3.
Solution to Exercise 4
import java.util.*;

public class StudentProduct {

    record Student(String name, int age) {
        @Override
        public String toString() { return "Name: " + name + ", Age: " + age; }
    }

    // The business identity is the ID: two Products with the same ID are "the same product"
    static final class Product {
        private final int id;
        private String name;
        private double price;

        Product(int id, String name, double price) {
            this.id = id;
            this.name = name;
            this.price = price;
        }

        int getId() { return id; }
        String getName() { return name; }
        double getPrice() { return price; }
        void setName(String name) { this.name = name; }       // not part of equals/hashCode
        void setPrice(double price) { this.price = price; }   // so changing it can't break the HashSet

        @Override
        public boolean equals(Object o) {
            return this == o || (o instanceof Product p && p.id == id);
        }

        @Override
        public int hashCode() { return Integer.hashCode(id); }

        @Override
        public String toString() { return "Product{id=" + id + ", name=" + name + ", price=" + price + "}"; }
    }

    static void print(String title, List<Student> students) {
        System.out.println(title);
        students.forEach(s -> System.out.println("  " + s));
    }

    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        students.add(new Student("Alice", 20));
        students.add(new Student("Bob", 22));
        students.add(new Student("Charlie", 21));
        print("Initial:", students);

        students.add(1, new Student("David", 23));   // insert: shifts Bob and Charlie right
        print("After add at index 1:", students);    // Alice, David, Bob, Charlie

        students.remove(0);                          // remove(int): by position
        print("After remove index 0:", students);    // David, Bob, Charlie

        Set<Product> products = new HashSet<>();
        products.add(new Product(1, "Laptop", 1500.0));       // true
        products.add(new Product(2, "Mouse", 20.0));          // true
        products.add(new Product(3, "Keyboard", 45.0));       // true
        products.add(new Product(1, "Laptop Pro", 2000.0));   // false: same ID
        products.add(new Product(1, "Laptop", 1500.0));       // false: full duplicate
        products.forEach(System.out::println);                // 3 products, the first "Laptop" is kept

        products.removeIf(p -> p.getId() == 3);      // or products.remove(new Product(3, "", 0))
        System.out.println("After removing id 3: " + products.size() + " products");   // 2
    }
}

Notes:

  • add(1, x) and remove(0) on an ArrayList both shift everything after them, O(n). With three elements you won’t notice, but removing from the front of a big list inside a loop is O(n²); use an ArrayDeque or iterate backwards instead.
  • “Duplicate” is a business decision: here two products with the same ID are one product, so equals/hashCode use only id. If Product were a record Product(id, name, price), the record would compare every field and "Laptop Pro" with ID 1 would be added as a separate product. Neither is right in general; choose on purpose.
  • A duplicate add doesn’t overwrite: the set keeps the old object ("Laptop", 1500.0). If you want “update if present”, use a Map<Integer, Product> and put.
  • The field used by hashCode (id) is final; name and price can change because they don’t affect the bucket. Letting id change after the object is in a set is a reliable way to “lose” elements.

I ran the program on JDK 21 and the output matches the comments above.

Remember

  • Pick List, Set, Map or Queue for a requirement, and explain why you declare with the interface.
  • Explain the four steps of HashSet.add and why a missing hashCode lets a set hold duplicates.
  • Know how to remove safely while iterating, and what remove(1) on a List<Integer> removes.
  • Know when to use getOrDefault, putIfAbsent, computeIfAbsent and merge, and what a null-returning function does.
  • Know why removeAll/retainAll can be O(n·m) and how to fix it.

Interview questions

Junior

Why must you override hashCode when you override equals?

Because the contract says equal objects must have equal hash codes, and HashMap/HashSet use hashCode to pick a bucket before they ever compare with equals.

Override only equals and two “equal” objects can sit in different buckets, so a set holds duplicates and a map can’t find your key.

How do HashSet, LinkedHashSet and TreeSet differ, and which do you pick?

Default to HashSet; use LinkedHashSet for insertion order; use TreeSet for sorting or range queries.

  • HashSet: a hash table, O(1) average add/contains/remove, no ordering guarantee, duplicates decided by hashCode + equals, one null allowed.
  • LinkedHashSet: the same plus a linked list, so it iterates in insertion order.
  • TreeSet: a red-black tree, O(log n), always iterates in ascending order, decides duplicates with compareTo/the comparator, rejects null under natural ordering, and offers floor/ceiling/headSet.
Given List<Integer> list, what does list.remove(1) remove?

The element at index 1, not the value 1.

The remove(int index) overload matches an int argument exactly, so it wins over remove(Object), which would need boxing. To remove the value 1, write list.remove(Integer.valueOf(1)). It’s a classic trap in code that reads numbers from input and then deletes by value.

Mid

When does ConcurrentModificationException happen, and how do you avoid it?

When a collection gets elements added or removed while an iterator is walking it, even on a single thread; fix it with iterator.remove() or removeIf.

For example list.remove(x) inside an enhanced for loop. The iterator compares modCount against what it expects and throws (fail-fast). Other options: iterate over a copy, or use a concurrent collection.

How do getOrDefault, putIfAbsent, computeIfAbsent and merge differ?

getOrDefault only reads; putIfAbsent stores a value built up front; computeIfAbsent builds the value only when the key is missing; merge puts or combines.

  • getOrDefault(k, d): returns d for a missing key and writes nothing.
  • putIfAbsent(k, v): writes v when the key is absent (or mapped to null); v is built even if it isn’t used.
  • computeIfAbsent(k, fn): calls fn only when the key is missing, which suits expensive values and multimaps (computeIfAbsent(k, x -> new ArrayList<>()).add(v)).
  • merge(k, v, fn): puts v if absent, otherwise combines with fn, which suits counting and summing.
  • A function returning null in compute/merge removes the entry.
You put Product in a HashSet: which fields go into equals/hashCode? Does adding a duplicate replace the old one?

Exactly the fields that make up the business identity (usually id, and they should be final); adding a duplicate replaces nothing and returns false.

Mutable fields such as price or name shouldn’t take part, or changing a price after add makes the element “disappear” from the set. A record compares every field, so as records two products with the same ID and different prices are different elements. The set keeps the old object; for update-by-ID use a Map<Id, Product> and put.

How do you get the intersection and the difference of two lists? Any performance trap?

Copy the original, then call retainAll(other) for the intersection or removeAll(other) for the difference; wrap other in a HashSet to avoid O(n·m).

Both modify the collection they’re called on and return true if it changed. Internally they call other.contains(x) for every element, so if other is an ArrayList the cost is O(n·m); with new HashSet<>(other) it’s O(n + m). Calling them on an immutable list (List.of) throws UnsupportedOperationException.

Useful phrases for interviews

  • “The contract between equals and hashCode is what makes hash-based collections work.”
  • “I declare the variable as the interface, List or Map, so swapping the implementation is a one-line change.”
  • “hashCode decides which bucket to look in; equals decides whether it’s actually a duplicate.”
  • “Whether two products count as duplicates is a business decision, so I choose the fields in equals on purpose.”
  • “getOrDefault never writes to the map; if I want the default stored, I use computeIfAbsent.”
  • “For counting, merge with Integer::sum replaces the get-check-put dance with a single call.”
  • “Removing inside a for-each trips the fail-fast check, so I use removeIf or the iterator’s own remove.”
  • “retainAll keeps only what’s in both, but I wrap the argument in a HashSet so it isn’t O(n times m).”
  • “If insertion order matters for the output, I switch to the Linked variant, LinkedHashMap or LinkedHashSet.”

Notes based on the Fundamentals of Backend course (Ronin Engineer) and the Hỏi Dân IT Java Core material, plus my own research, rewritten in my own words.