Chapter 7: Java Collections — The Interview Guide

Objective

This chapter covers everything you need to know about Java Collections for an interview: when to use what, the differences between List.of() and new ArrayList<>(), common pitfalls, and classic questions.

---

1. The Collections Hierarchy

                    Iterable
                       │
                   Collection
                  ╱    │     ╲
               List   Set    Queue
              ╱  │      │  ╲     │
      ArrayList  │   HashSet  │  LinkedList
      LinkedList │   TreeSet  │  PriorityQueue
                 │  LinkedHashSet
              Vector
              (legacy)

                    Map (not a Collection!)
                   ╱    │     ╲
              HashMap  TreeMap  LinkedHashMap
                │
           ConcurrentHashMap

---

2. List.of() vs new ArrayList — Mutable vs Immutable

The Fundamental Difference

Creation	Type	Modifiable?	Accepts null?
List.of("a", "b")	Immutable list	No	No
new ArrayList<>(List.of("a", "b"))	Mutable list	Yes	Yes
Collections.unmodifiableList(list)	Immutable view	No (but the original yes)	Yes
List.copyOf(list)	Immutable copy	No	No

Concrete Examples

// IMMUTABLE — cannot be modified
List<String> immutable = List.of("a", "b", "c");
immutable.add("d");     // 💥 UnsupportedOperationException
immutable.remove(0);    // 💥 UnsupportedOperationException
immutable.set(0, "x");  // 💥 UnsupportedOperationException

// MUTABLE — can be modified
List<String> mutable = new ArrayList<>();
mutable.add("a");       // ✅ OK
mutable.add("b");       // ✅ OK
mutable.remove(0);      // ✅ OK
mutable.set(0, "x");    // ✅ OK

// Create a mutable list from an immutable one
List<String> mutable2 = new ArrayList<>(List.of("a", "b", "c"));
mutable2.add("d");      // ✅ OK

Map.of() and Set.of() — Same Principle

// Immutable Map
Map<String, Integer> map = Map.of("a", 1, "b", 2);
map.put("c", 3);  // 💥 UnsupportedOperationException

// Mutable Map
Map<String, Integer> map2 = new HashMap<>(Map.of("a", 1, "b", 2));
map2.put("c", 3);  // ✅ OK

// Immutable Set
Set<String> set = Set.of("a", "b", "c");
set.add("d");  // 💥 UnsupportedOperationException

// Mutable Set
Set<String> set2 = new HashSet<>(Set.of("a", "b", "c"));
set2.add("d");  // ✅ OK

Collections.emptyList() vs List.of()

// Both return an immutable empty list
List<String> empty1 = Collections.emptyList();  // Java 5+
List<String> empty2 = List.of();                 // Java 9+ (preferred)

// Both are equivalent, List.of() is more modern

When to Use What?

Situation	Use	Why
Constants, configurations	List.of()	Immutable, thread-safe
Building a list progressively	new ArrayList<>()	Need to add elements
Method return (empty case)	List.of() or Collections.emptyList()	Never return null
DTO / Records	List.copyOf()	Defensive copy, ensures immutability
Unit tests	List.of()	Concise and clear

Interview Phrase

"List.of() creates an immutable list — it's compact, null-safe, and thread-safe. new ArrayList<>() creates a mutable list that I can modify. I use List.of() for constants and return values, ArrayList for building collections."

---

3. ArrayList vs LinkedList

ArrayList (dynamic array) :
┌───┬───┬───┬───┬───┬───┬───┬   ┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │...│  ← direct access by index
└───┴───┴───┴───┴───┴───┴───┴   ┘

LinkedList (doubly linked list) :
null ← [A] ⇄ [B] ⇄ [C] ⇄ [D] → null

Operation	ArrayList	LinkedList
get(index)	O(1)	O(n)
add(element) (end)	O(1) amortized	O(1)
add(index, element) (middle)	O(n)	O(1) if node is known
remove(index)	O(n)	O(1) if node is known
Memory	Compact	Heavier (pointers)
CPU Cache	Good (contiguous elements)	Poor (scattered elements)

In Practice

Use ArrayList in 99% of cases. LinkedList is rarely faster in practice due to CPU cache locality. Even for frequent insertions, ArrayList is often faster.

Interview Phrase

"I almost always use ArrayList. LinkedList has better theoretical complexity for insertions, but ArrayList wins in practice due to CPU cache locality. LinkedList is useful as a Queue (FIFO) via the Deque interface."

---

4. HashMap — How It Works

Internal Structure

HashMap (Java 8+) :
┌──────────────────────────────┐
│ Buckets (array)              │
├──────┬───────────────────────┤
│  [0] │ null                  │
│  [1] │ → Entry(key1, val1)   │
│  [2] │ null                  │
│  [3] │ → Entry(key2, val2) → Entry(key3, val3)  ← collision!
│  [4] │ null                  │
│  ... │                       │
│  [n] │ → Entry(keyN, valN)   │
└──────┴───────────────────────┘

If a linked list in a bucket exceeds 8 elements → converted to a red-black tree (O(log n))

How It Works?

Map<String, Integer> map = new HashMap<>();
map.put("Alice", 25);

// Step 1: hashCode("Alice") → 63650026
// Step 2: 63650026 % array_size → bucket index
// Step 3: Store Entry("Alice", 25) in this bucket

Collision = Same Bucket

// If two keys have the same bucket index:
map.put("Alice", 25);   // bucket 3
map.put("Bob", 30);     // also bucket 3 (collision)

// Java creates a linked list in bucket 3:
// bucket[3] → Entry("Alice", 25) → Entry("Bob", 30)
// To find "Bob", Java traverses the list and uses equals()

Complexities

Operation	Average Case	Worst Case (many collisions)
put()	O(1)	O(log n) (tree since Java 8)
get()	O(1)	O(log n)
remove()	O(1)	O(log n)
containsKey()	O(1)	O(log n)
containsValue()	O(n)	O(n)

---

5. HashMap vs TreeMap vs LinkedHashMap

Map	Order	Complexity	When to Use
HashMap	No guaranteed order	O(1)	Default, fastest
TreeMap	Sorted by key (natural or Comparator)	O(log n)	Need sorted keys
LinkedHashMap	Insertion order	O(1)	Need insertion order

Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("banana", 2);
hashMap.put("apple", 1);
hashMap.put("cherry", 3);
// Iteration: arbitrary order

Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("banana", 2);
treeMap.put("apple", 1);
treeMap.put("cherry", 3);
// Iteration: apple → banana → cherry (alphabetical)

Map<String, Integer> linkedMap = new LinkedHashMap<>();
linkedMap.put("banana", 2);
linkedMap.put("apple", 1);
linkedMap.put("cherry", 3);
// Iteration: banana → apple → cherry (insertion order)

---

6. HashSet vs TreeSet vs LinkedHashSet

Set	Order	Duplicates	Complexity
HashSet	None	No	O(1)
TreeSet	Sorted	No	O(log n)
LinkedHashSet	Insertion order	No	O(1)

// HashSet = most used
Set<String> unique = new HashSet<>(List.of("b", "a", "c", "a"));
// → [a, b, c] (no duplicates, arbitrary order)

// TreeSet = automatically sorted
Set<String> sorted = new TreeSet<>(List.of("banana", "apple", "cherry"));
// → [apple, banana, cherry]

Reminder

HashSet uses hashCode() and equals() to detect duplicates. If your custom objects don't implement these methods, the Set won't work correctly.

---

7. Queue and Deque

// Queue (FIFO: First In, First Out) — waiting line
Queue<String> queue = new LinkedList<>();
queue.offer("first");    // add to the end
queue.offer("second");
queue.offer("third");
queue.poll();            // remove from the start → "first"

// Deque (Double-Ended Queue) — stack or queue
Deque<String> deque = new ArrayDeque<>();

// As Stack (LIFO):
deque.push("a");
deque.push("b");
deque.pop();   // → "b" (last in, first out)

// As Queue (FIFO):
deque.offerLast("a");
deque.offerLast("b");
deque.pollFirst();  // → "a" (first in, first out)

Do Not Use Stack

java.util.Stack is a legacy class (Java 1.0) unnecessarily synchronized. Use ArrayDeque instead.

// ❌ Legacy
Stack<String> stack = new Stack<>();

// ✅ Modern
Deque<String> stack = new ArrayDeque<>();

---

8. Iterating Over Collections

The 5 Ways to Iterate

List<String> names = List.of("Alice", "Bob", "Charlie");

// 1. For-each (most common)
for (String name : names) {
    System.out.println(name);
}

// 2. Stream API (functional)
names.stream()
    .filter(n -> n.startsWith("A"))
    .forEach(System.out::println);

// 3. forEach with lambda
names.forEach(name -> System.out.println(name));

// 4. Iterator (when you need to remove while iterating)
Iterator<String> it = names.iterator();
while (it.hasNext()) {
    String name = it.next();
    if (name.equals("Bob")) it.remove();
}

// 5. Classic for with index (only ArrayList)
for (int i = 0; i < names.size(); i++) {
    System.out.println(names.get(i));
}

Pitfall: ConcurrentModificationException

// ❌ ERROR — modifying a list during a for-each
List<String> list = new ArrayList<>(List.of("a", "b", "c"));
for (String s : list) {
    if (s.equals("b")) list.remove(s);  // 💥 ConcurrentModificationException
}

// ✅ Solution 1: Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("b")) it.remove();  // OK
}

// ✅ Solution 2: removeIf (Java 8+)
list.removeIf(s -> s.equals("b"));  // OK, more concise

// ✅ Solution 3: Stream + filter (creates a new list)
List<String> filtered = list.stream()
    .filter(s -> !s.equals("b"))
    .toList();

Interview Phrase

"You can't modify a collection while iterating with for-each. I use Iterator.remove(), removeIf(), or streams to safely remove elements during iteration."

---

9. Thread-safe Collections

Collection	Thread-safe?	Thread-safe Alternative
ArrayList	No	CopyOnWriteArrayList or Collections.synchronizedList()
HashMap	No	ConcurrentHashMap
HashSet	No	ConcurrentHashMap.newKeySet()
LinkedList	No	ConcurrentLinkedQueue

// ❌ HashMap is NOT thread-safe
Map<String, Integer> map = new HashMap<>();

// ✅ ConcurrentHashMap is thread-safe WITHOUT global synchronization
Map<String, Integer> map = new ConcurrentHashMap<>();

// ❌ Hashtable is thread-safe but LEGACY and slow (synchronized everywhere)
Map<String, Integer> map = new Hashtable<>();  // DO NOT USE

Interview Phrase

"For concurrent access, I use ConcurrentHashMap instead of HashMap — it uses lock striping for better throughput than the legacy synchronized Hashtable."

---

10. Stream API — Quick Summary

List<User> users = getUsers();

// Filter
List<User> active = users.stream()
    .filter(User::isActive)
    .toList();

// Transform
List<String> emails = users.stream()
    .map(User::getEmail)
    .toList();

// Sort
List<User> sorted = users.stream()
    .sorted(Comparator.comparing(User::getName))
    .toList();

// Group
Map<String, List<User>> byRole = users.stream()
    .collect(Collectors.groupingBy(User::getRole));

// Reduce (sum, max, min)
double totalSalary = users.stream()
    .mapToDouble(User::getSalary)
    .sum();

// Check
boolean anyAdmin = users.stream().anyMatch(u -> "ADMIN".equals(u.getRole()));
boolean allActive = users.stream().allMatch(User::isActive);
boolean noneBlocked = users.stream().noneMatch(User::isBlocked);

The Operations

Type	Examples	Returns
Intermediate (lazy)	filter, map, sorted, distinct, limit, skip	Stream
Terminal (execute)	toList, collect, forEach, count, sum, reduce, anyMatch	Result

Interview Phrase

"Streams are lazy — intermediate operations like filter and map don't execute until a terminal operation like toList() is called. I use streams for declarative, readable data processing."

---

Summary Table — Which Collection to Use?

Need	Collection	Why
Ordered list, index access	ArrayList	O(1) for get/set
No duplicates	HashSet	O(1) for add/contains
No duplicates + sorted order	TreeSet	O(log n), sorted
Key → Value	HashMap	O(1) for put/get
Key → Value, sorted by key	TreeMap	O(log n), sorted
FIFO (queue)	ArrayDeque	Faster than LinkedList
LIFO (stack)	ArrayDeque	Replaces Stack (legacy)
Thread-safe Map	ConcurrentHashMap	Lock striping
Immutable list	List.of()	Thread-safe, compact

---

⬅️ Chapter 6: Java Gotchas | ⬅️ Back to Module 18