08 - Mastering Collections and Generics

A complete beginner-to-advanced guide to the Java Collections Framework and Generics, aligned with the Oracle Certified Professional: Java SE 21 Developer (1Z0-830) exam objectives.

Table of Contents

1. The Collections Framework
2. List vs Set vs Map vs Queue
3. List & ArrayList vs LinkedList
4. Set: HashSet vs LinkedHashSet vs TreeSet
5. Map: HashMap vs LinkedHashMap vs TreeMap
6. Queue & Deque
7. Comparable
8. Comparator
9. Generics From Scratch
10. Generic Methods & Bounded Types
11. Wildcards (?, extends, super)
12. Type Erasure
13. Collection Utilities
14. Performance Comparison Tables
15. Certification Traps
16. Common Mistakes
17. Interview Questions
18. Quick Revision Notes
19. One-Page Cheat Sheet

1. The Collections Framework

The Java Collections Framework (JCF) is a set of interfaces and classes for storing and manipulating groups of objects.

              Iterable
                 |
              Collection                         Map  (separate hierarchy!)
            /     |      \                       /  \
         List    Set     Queue            HashMap   TreeMap   LinkedHashMap
         /  \    /  \      |  \
  ArrayList  \  Hash TreeSet Deque PriorityQueue
       LinkedList Set        |
                        ArrayDeque

Key fact: Map is NOT a Collection. It's a separate root interface (it stores key-value pairs, not single elements).

Core Interfaces

2. List vs Set vs Map vs Queue

List<String> list = new ArrayList<>(List.of("a", "a", "b"));   // [a, a, b]
Set<String> set   = new HashSet<>(List.of("a", "a", "b"));     // [a, b]
Map<String,Integer> map = new HashMap<>();
map.put("a", 1); map.put("a", 2);                              // {a=2} (overwrites)
Queue<Integer> queue = new LinkedList<>();
queue.offer(1); queue.offer(2);                                // [1, 2] FIFO

3. List & ArrayList vs LinkedList

A List is an ordered collection allowing duplicates and index-based access.

List<String> fruits = new ArrayList<>();
fruits.add("Apple");
fruits.add("Banana");
fruits.add(1, "Mango");          // insert at index
System.out.println(fruits.get(0)); // Apple
fruits.set(0, "Orange");          // replace
fruits.remove("Banana");          // remove by value
System.out.println(fruits.size()); // 2

ArrayList vs LinkedList

// LinkedList can act as a Queue or Deque:
LinkedList<Integer> deque = new LinkedList<>();
deque.addFirst(1);
deque.addLast(2);
deque.removeFirst();

Rule of thumb: Default to ArrayList. Use LinkedList only when you do many additions/removals at the ends.

4. Set: HashSet vs LinkedHashSet vs TreeSet

A Set stores unique elements (no duplicates). Uniqueness uses equals() + hashCode() (or ordering for TreeSet).

Set<String> set = new HashSet<>();
set.add("A");
set.add("A");            // ignored — duplicate
set.add("B");
System.out.println(set.size());   // 2

Comparison

Set<Integer> tree = new TreeSet<>(List.of(5, 1, 3, 2));
System.out.println(tree);          // [1, 2, 3, 5] (sorted)

// TreeSet navigation methods:
TreeSet<Integer> ts = new TreeSet<>(List.of(10, 20, 30));
System.out.println(ts.first());     // 10
System.out.println(ts.last());      // 30
System.out.println(ts.ceiling(15)); // 20 (>= 15)
System.out.println(ts.floor(15));   // 10 (<= 15)
System.out.println(ts.higher(20));  // 30 (strictly >)
System.out.println(ts.lower(20));   // 10 (strictly <)

Trap: TreeSet throws NullPointerException on add(null) (it can't compare null). HashSet allows one null.

5. Map: HashMap vs LinkedHashMap vs TreeMap

A Map stores key → value pairs with unique keys.

Map<String, Integer> ages = new HashMap<>();
ages.put("Alice", 30);
ages.put("Bob", 25);
ages.put("Alice", 31);             // overwrites -> {Alice=31, Bob=25}
System.out.println(ages.get("Alice"));        // 31
System.out.println(ages.getOrDefault("X", 0)); // 0
System.out.println(ages.containsKey("Bob"));   // true

// Iterate
for (Map.Entry<String, Integer> e : ages.entrySet()) {
    System.out.println(e.getKey() + " = " + e.getValue());
}

Comparison

Useful Map Methods (Java 8+)

Map<String, Integer> map = new HashMap<>();
map.putIfAbsent("a", 1);
map.merge("a", 10, Integer::sum);          // a = 11
map.computeIfAbsent("b", k -> 0);          // b = 0
map.compute("a", (k, v) -> v + 1);         // a = 12
map.forEach((k, v) -> System.out.println(k + "=" + v));

Trap: TreeMap does not allow a null key (throws NPE), but HashMap allows one null key. All allow null values except as noted.

6. Queue & Deque

Queue (FIFO)

Queue<String> queue = new LinkedList<>();
queue.offer("A");          // add to tail (returns false if full)
queue.offer("B");
System.out.println(queue.peek());   // A (head, no removal)
System.out.println(queue.poll());   // A (head, removes)
System.out.println(queue.poll());   // B
System.out.println(queue.poll());   // null (empty)

Trap: add/remove/element throw exceptions when they fail; offer/poll/peek return false/null. Prefer the latter.

PriorityQueue

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(30); pq.offer(10); pq.offer(20);
System.out.println(pq.poll());   // 10 (smallest first — min-heap)

Deque (Double-Ended Queue)

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
System.out.println(deque.peekFirst()); // 1
System.out.println(deque.peekLast());  // 2

// Deque as a Stack (LIFO) — preferred over legacy Stack class:
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);
System.out.println(stack.pop());       // 2 (LIFO)

Use ArrayDeque for stacks/queues — it's faster than the legacy Stack and LinkedList for these uses.

7. Comparable

Comparable<T> defines a class's natural ordering via compareTo(). Implemented by the class itself.

class Student implements Comparable<Student> {
    String name; int age;
    Student(String name, int age) { this.name = name; this.age = age; }

    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.age, other.age);   // sort by age ascending
    }
    public String toString() { return name + "(" + age + ")"; }
}

List<Student> students = new ArrayList<>(List.of(
    new Student("Bob", 25), new Student("Alice", 20)));
Collections.sort(students);            // uses compareTo
System.out.println(students);          // [Alice(20), Bob(25)]

compareTo Return Values

Trap: Use Integer.compare(a, b) instead of a - b to avoid integer overflow bugs.

8. Comparator

Comparator<T> defines external/custom ordering — separate from the class. Useful for multiple sort orders.

List<Student> students = new ArrayList<>(/* ... */);

// Sort by name
students.sort(Comparator.comparing(s -> s.name));

// Sort by age descending
students.sort(Comparator.comparingInt((Student s) -> s.age).reversed());

// Chained: by age, then by name
students.sort(
    Comparator.comparingInt((Student s) -> s.age)
              .thenComparing(s -> s.name));

Comparable vs Comparator

Handy Comparator Factories

Comparator<String> byLength = Comparator.comparingInt(String::length);
Comparator<String> natural  = Comparator.naturalOrder();
Comparator<String> reverse  = Comparator.reverseOrder();
Comparator<Student> nullsFirst = Comparator.nullsFirst(Comparator.comparing(s -> s.name));

9. Generics From Scratch

Generics let you write classes/methods that work with any type while keeping compile-time type safety.

The Problem Generics Solve

// Without generics (pre-Java 5) — unsafe:
List list = new ArrayList();
list.add("hello");
String s = (String) list.get(0);   // manual cast, runtime risk

// With generics — safe:
List<String> safe = new ArrayList<>();
safe.add("hello");
String s2 = safe.get(0);           // no cast, compile-time checked
// safe.add(42);                   // COMPILE ERROR — caught early

Generic Class

class Box<T> {                      // T is a type parameter
    private T value;
    public void set(T value) { this.value = value; }
    public T get() { return value; }
}

Box<String> sb = new Box<>();
sb.set("Hello");
String result = sb.get();           // no cast needed

Common Type Parameter Names

The Diamond Operator

Map<String, List<Integer>> map = new HashMap<>();   // <> infers the types

10. Generic Methods & Bounded Types

Generic Method

public static <T> T firstElement(List<T> list) {
    return list.get(0);
}

String first = firstElement(List.of("a", "b"));   // T inferred as String

Bounded Type Parameters

Restrict the type with extends (upper bound):

// T must be Number or a subclass
public static <T extends Number> double sum(List<T> list) {
    double total = 0;
    for (T n : list) total += n.doubleValue();   // can call Number methods
    return total;
}

sum(List.of(1, 2, 3));       // OK (Integer)
sum(List.of(1.5, 2.5));      // OK (Double)
// sum(List.of("a", "b"));   // COMPILE ERROR (String is not a Number)

Multiple Bounds

// T must be a subtype of BOTH (class first, then interfaces)
public static <T extends Number & Comparable<T>> T max(T a, T b) {
    return a.compareTo(b) >= 0 ? a : b;
}

Rule: With multiple bounds, the class bound (if any) must come first, followed by interfaces.

11. Wildcards (?, extends, super)

Wildcards (?) provide flexibility when the exact type isn't known. Remember PECS: Producer extends, Consumer super.

Unbounded Wildcard <?>

public static void printAll(List<?> list) {       // any type
    for (Object o : list) System.out.println(o);
}
printAll(List.of(1, 2, 3));
printAll(List.of("a", "b"));

Upper-Bounded <? extends T> — Producer (READ)

// Accepts List<Number>, List<Integer>, List<Double>...
public static double sumList(List<? extends Number> list) {
    double sum = 0;
    for (Number n : list) sum += n.doubleValue();   // safe to READ as Number
    return sum;
    // list.add(1);   // COMPILE ERROR — cannot add (don't know exact type)
}

Lower-Bounded <? super T> — Consumer (WRITE)

// Accepts List<Integer>, List<Number>, List<Object>
public static void addNumbers(List<? super Integer> list) {
    list.add(1);          // safe to WRITE Integer
    list.add(2);
    // Integer i = list.get(0);   // ERROR — reads come back as Object
}

PECS Summary

        +----------------------------+----------------------------+
        |  ? extends T (upper bound) |  ? super T (lower bound)   |
        +----------------------------+----------------------------+
  READ  |  YES (as T)                |  only as Object            |
  WRITE |  NO (except null)          |  YES (T and subtypes)      |
        +----------------------------+----------------------------+
  Use   |  PRODUCER (you read from)  |  CONSUMER (you write to)   |

Trap: You cannot add elements (except null) to a List<? extends T> — the compiler doesn't know the exact subtype.

12. Type Erasure

Generics are a compile-time feature. At runtime, type parameters are erased (replaced with Object or the bound).

List<String> s = new ArrayList<>();
List<Integer> i = new ArrayList<>();
System.out.println(s.getClass() == i.getClass());   // true! Both are ArrayList

Consequences (Traps)

// if (obj instanceof List<String>) { }   // COMPILE ERROR
if (obj instanceof List<?>) { }            // OK

13. Collection Utilities

Factory Methods (Java 9+) — Immutable

List<Integer> list = List.of(1, 2, 3);          // immutable
Set<String> set    = Set.of("a", "b");          // immutable, no duplicates allowed
Map<String,Integer> map = Map.of("a", 1, "b", 2); // immutable

// list.add(4);   // UnsupportedOperationException at runtime!

Trap: List.of(), Set.of(), Map.of() return immutable collections — mutating them throws UnsupportedOperationException. They also reject null elements.

Collections Class

List<Integer> nums = new ArrayList<>(List.of(3, 1, 2));
Collections.sort(nums);                  // [1, 2, 3]
Collections.reverse(nums);               // [3, 2, 1]
Collections.shuffle(nums);
System.out.println(Collections.max(nums));
System.out.println(Collections.min(nums));
List<Integer> readOnly = Collections.unmodifiableList(nums);

Iterator & removeIf

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4));

// Safe removal during iteration:
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    if (it.next() % 2 == 0) it.remove();   // safe
}

// Or simpler (Java 8+):
list.removeIf(n -> n % 2 == 0);

Trap: Modifying a collection during a for-each loop throws ConcurrentModificationException. Use Iterator.remove() or removeIf().

14. Performance Comparison Tables

Lists

* amortized; ** O(1) at the node, O(n) to find it.

Sets

Maps

15. Certification Traps

16. Common Mistakes

17. Interview Questions

Q1. Is Map part of the Collection interface? No. Map is a separate root interface because it stores key-value pairs, not individual elements.

Q2. Difference between ArrayList and LinkedList? ArrayList uses a dynamic array (fast random access, slow middle inserts); LinkedList uses a doubly linked list (fast end inserts/deletes, slow random access).

Q3. Difference between HashSet and TreeSet? HashSet is unordered with O(1) operations; TreeSet keeps elements sorted with O(log n) operations and requires Comparable/Comparator.

Q4. Difference between HashMap and TreeMap? HashMap is unordered, O(1), allows a null key; TreeMap is sorted by key, O(log n), and rejects null keys.

Q5. Difference between Comparable and Comparator? Comparable defines a single natural ordering inside the class (compareTo); Comparator defines external, multiple custom orderings (compare).

Q6. What are generics and why use them? Parameterized types that provide compile-time type safety and remove the need for casts.

Q7. Explain PECS. Producer Extends, Consumer Super: use <? extends T> when reading from a structure, <? super T> when writing to it.

Q8. Why can't you add to a List<? extends Number>? The exact subtype is unknown, so the compiler can't guarantee type safety for additions (except null).

Q9. What is type erasure? The process where generic type information is removed at compile time, so generics exist only at compile time, not runtime.

Q10. How do you avoid ConcurrentModificationException? Use Iterator.remove(), removeIf(), or a concurrent collection, instead of modifying during a for-each loop.

Q11. Difference between offer/poll/peek and add/remove/element? The first set returns special values (false/null) on failure; the second set throws exceptions.

Q12. Why must you override both equals and hashCode? Hash-based collections use hashCode to locate buckets and equals to confirm matches; overriding only one breaks their contract.

18. Quick Revision Notes

• Iterable → Collection → List/Set/Queue; Map is separate.
• List: ordered, duplicates, index access.
• Set: unique elements; HashSet (unordered), LinkedHashSet (insertion), TreeSet (sorted).
• Map: key→value; HashMap (unordered), LinkedHashMap (insertion), TreeMap (sorted).
• TreeSet/TreeMap reject null keys and need ordering; HashSet/HashMap allow one null.
• ArrayList: fast random access; LinkedList: fast end inserts, also a Deque.
• Queue: offer/poll/peek (safe) vs add/remove/element (throw).
• ArrayDeque for stacks/queues (beats legacy Stack).
• Comparable = natural order (compareTo); Comparator = custom orders (compare).
• Generics = compile-time type safety; diamond <> infers types.
• Bounded: <T extends Number>; multiple bounds class-first.
• PECS: Producer extends (read), Consumer super (write).
• Type erasure: no new T(), new T[], List<int>, or instanceof List<String>.
• List.of/Set.of/Map.of are immutable and null-hostile.
• Use Iterator.remove/removeIf to avoid ConcurrentModificationException.

19. One-Page Cheat Sheet

==================== COLLECTIONS & GENERICS CHEAT SHEET ====================

HIERARCHY
  Iterable -> Collection -> List / Set / Queue
  Map = SEPARATE (not a Collection)

LIST (ordered, duplicates, index)
  ArrayList  -> array, get(i) O(1), middle insert O(n)  [DEFAULT]
  LinkedList -> nodes, end ops O(1), random O(n), is a Deque

SET (unique)
  HashSet       -> unordered, O(1), 1 null
  LinkedHashSet -> insertion order, O(1)
  TreeSet       -> sorted, O(log n), NO null, needs Comparable/Comparator
  nav: first last ceiling floor higher lower

MAP (key->value, unique keys)
  HashMap       -> unordered, O(1), 1 null key
  LinkedHashMap -> insertion order, O(1)
  TreeMap       -> sorted keys, O(log n), NO null key
  getOrDefault putIfAbsent merge computeIfAbsent compute forEach

QUEUE / DEQUE
  offer/poll/peek (safe: false/null) vs add/remove/element (throw)
  PriorityQueue -> min-heap, poll() smallest (iteration NOT sorted)
  ArrayDeque -> stack(push/pop) & queue ; beats legacy Stack

COMPARABLE vs COMPARATOR
  Comparable: compareTo(o), java.lang, natural order, in class
  Comparator: compare(a,b), java.util, custom/multiple, external
  Comparator.comparing(...).thenComparing(...).reversed()
  use Integer.compare(a,b) NOT a-b

GENERICS
  class Box<T>{T get();}  ; <T> T method(List<T>) ; diamond new ArrayList<>()
  bounded: <T extends Number> ; multiple: <T extends A & B> (class first)

WILDCARDS (PECS)
  <?>            any ; read as Object ; write only null
  <? extends T>  PRODUCER ; read as T ; CANNOT add (except null)
  <? super T>    CONSUMER ; write T ; read as Object

TYPE ERASURE
  List<String>.class == List<Integer>.class (true)
  NO new T(), new T[], List<int>, instanceof List<String>

UTILITIES
  List.of/Set.of/Map.of -> IMMUTABLE, no nulls (Unsupported... on mutate)
  Collections.sort/reverse/max/min/unmodifiableList
  removeIf / Iterator.remove -> avoid ConcurrentModificationException
===========================================================================

End of 08 - Mastering Collections and Generics.