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.
Mapdoes not extendCollection.
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…Listadds: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 aslist.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 withCollections.reverse(list), which flips element positions.Collections.binarySearchis 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 theBlockingQueuefamily 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:
- Call
x.hashCode()to get an integer. - Turn it into a bucket. If the bucket is empty, put
xthere and you’re done. - If the bucket already holds elements (a collision), walk through them.
- Call
equalsagainst each one. If any equalsx, nothing is added (addreturnsfalse); otherwisexjoins 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/computeIfPresentfunction that returnsnullremoves the entry:merge("pear", -3, (a, b) -> a + b == 0 ? null : a + b)removespearonce it reaches 0. - Iterating
keySet()and callingget(key)hashes every key twice; on aTreeMapit adds another O(log n) lookup. UseentrySet()orforEach((k, v) -> ...). - The function passed to
computeIfAbsentmust not modify the same map. Memoizing a recursive Fibonacci withmemo.computeIfAbsent(n, k -> fib(k - 1) + fib(k - 2))throwsConcurrentModificationExceptionon aHashMapsince Java 9 (on aConcurrentHashMapit may hang or throwIllegalStateException). Compute the value first, thenputit.
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
mergeinstead of acontainsKey+putpair. - If you only need counts and not ordering,
HashMapis 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 asName: <name>, Age: <age>. Add three students to anArrayListand 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 overriddentoString,equalsandhashCode. Add five products to aHashSet, 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)andremove(0)on anArrayListboth 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 anArrayDequeor iterate backwards instead.- “Duplicate” is a business decision: here two products with the same ID are one product, so
equals/hashCodeuse onlyid. IfProductwere a recordProduct(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
adddoesn’t overwrite: the set keeps the old object ("Laptop", 1500.0). If you want “update if present”, use aMap<Integer, Product>andput. - The field used by
hashCode(id) isfinal;nameandpricecan change because they don’t affect the bucket. Lettingidchange 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,MaporQueuefor a requirement, and explain why you declare with the interface. - Explain the four steps of
HashSet.addand why a missinghashCodelets a set hold duplicates. - Know how to remove safely while iterating, and what
remove(1)on aList<Integer>removes. - Know when to use
getOrDefault,putIfAbsent,computeIfAbsentandmerge, and what anull-returning function does. - Know why
removeAll/retainAllcan 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 byhashCode+equals, onenullallowed.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 withcompareTo/the comparator, rejectsnullunder natural ordering, and offersfloor/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): returnsdfor a missing key and writes nothing.putIfAbsent(k, v): writesvwhen the key is absent (or mapped tonull);vis built even if it isn’t used.computeIfAbsent(k, fn): callsfnonly when the key is missing, which suits expensive values and multimaps (computeIfAbsent(k, x -> new ArrayList<>()).add(v)).merge(k, v, fn): putsvif absent, otherwise combines withfn, which suits counting and summing.- A function returning
nullincompute/mergeremoves 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,
ListorMap, so swapping the implementation is a one-line change.” - “
hashCodedecides which bucket to look in;equalsdecides 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.”
- “
getOrDefaultnever writes to the map; if I want the default stored, I usecomputeIfAbsent.” - “For counting,
mergewithInteger::sumreplaces the get-check-put dance with a single call.” - “Removing inside a for-each trips the fail-fast check, so I use
removeIfor the iterator’s ownremove.” - “
retainAllkeeps 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.