Collections Framework

What is the Collections Framework?

The Java Collections Framework is a unified set of interfaces and implementations for storing, retrieving, and manipulating groups of objects. It ships with the JDK — no dependencies needed — and covers virtually every data structure you'll encounter in production: dynamic lists, unique sets, key-value maps, queues, and deques.

The problem it solves: arrays are fixed-size and offer almost no built-in operations. Before the Collections Framework (pre-Java 2), every developer wrote their own resizable list or hash table — incompatible with everyone else's. The framework provides a common API so that any code accepting a List works with ArrayList, LinkedList, or any other implementation, without changes.

// Arrays: fixed size, no built-in operations
String[] names = new String[3];
names[0] = "Alice";
// Need a 4th name? Allocate a new array, copy everything. No remove, no contains.

// Collections: dynamic, rich API, type-safe
List<String> names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
names.remove("Alice");
names.contains("Bob");   // true
names.size();             // 1 — grows and shrinks automatically

/*
 *  The Collections hierarchy:
 *
 *  Iterable
 *  └── Collection
 *      ├── List      — ordered, allows duplicates
 *      │   ├── ArrayList    O(1) get, O(n) insert/delete middle
 *      │   └── LinkedList   O(1) insert/delete head/tail, O(n) get
 *      │
 *      ├── Set       — no duplicates
 *      │   ├── HashSet      O(1) add/contains, no order
 *      │   ├── LinkedHashSet O(1) add/contains, insertion order
 *      │   └── TreeSet      O(log n) add/contains, sorted
 *      │
 *      └── Queue     — ordered for processing
 *          ├── LinkedList   FIFO queue
 *          ├── ArrayDeque   fast deque, prefer over LinkedList
 *          └── PriorityQueue min-heap, poll() returns smallest
 *
 *  Map (NOT a Collection, but part of the framework)
 *      ├── HashMap      O(1) get/put, no order
 *      ├── LinkedHashMap O(1) get/put, insertion order
 *      └── TreeMap      O(log n) get/put, sorted by key
 */

// ❌ Locks you to ArrayList — hard to swap implementation later
ArrayList<String> names = new ArrayList<>();

// ✅ Depends on the contract — swap implementation without touching callers
List<String> names = new ArrayList<>();
List<String> names = new LinkedList<>();       // one word change
List<String> names = new CopyOnWriteArrayList<>(); // thread-safe, one word change

List — Ordered, Allows Duplicates

A List is the most-used collection type. It maintains insertion order, allows duplicates, and provides index-based access. Use it as your default unless you have a specific reason for another type.

ArrayList vs LinkedList

List<String> users = new ArrayList<>();

// Add
users.add("Alice");
users.add("Bob");
users.add(0, "Zara");      // insert at index 0

// Read
users.get(0);              // "Zara"
users.size();              // 3
users.contains("Bob");    // true
users.indexOf("Alice");  // 1

// Update
users.set(1, "Anna");     // replaces "Alice" with "Anna"

// Remove
users.remove("Bob");      // by value
users.remove(0);          // by index — careful: remove(0) vs remove(Integer.valueOf(0))

// Iterate
for (String u : users) { System.out.println(u); }
users.forEach(System.out::println);  // Java 8+

// Sort
users.sort(Comparator.naturalOrder());
users.sort(Comparator.comparing(String::length));

// Immutable list (Java 9+) — no add/remove allowed
List<String> fixed = List.of("A", "B", "C");

Set — No Duplicates

A Set guarantees uniqueness — adding the same element twice has no effect. Use it when you need to eliminate duplicates or test membership efficiently.

// Deduplication: convert List → Set
List<String> withDupes = List.of("a", "b", "a", "c");
Set<String> unique = new HashSet<>(withDupes);  // {a, b, c}

// Fast membership test — use Set, not List, for contains() at scale
Set<String> allowedRoles = Set.of("ADMIN", "EDITOR", "VIEWER");
if (allowedRoles.contains(user.getRole())) { ... }
// List.contains() is O(n). Set.contains() is O(1). Huge difference at scale.

// TreeSet: sorted, supports range operations
TreeSet<Integer> scores = new TreeSet<>(Set.of(50, 80, 30, 90, 70));
scores.first();              // 30
scores.last();               // 90
scores.headSet(70);         // {30, 50} — elements < 70
scores.tailSet(70);         // {70, 80, 90}
scores.subSet(50, 85);      // {50, 70, 80}

// Immutable set (Java 9+)
Set<String> fixed = Set.of("A", "B", "C");

Map — Key-Value Pairs

Map is not a Collection but is central to the framework. It maps unique keys to values — like a dictionary. Keys must be unique; values can repeat. null as a value is allowed in HashMap; as a key, only in HashMap (one null key).

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

// Put / update
scores.put("Alice", 95);
scores.put("Bob", 82);
scores.put("Alice", 97);   // overwrites 95

// Get
scores.get("Alice");          // 97
scores.get("Unknown");        // null — missing key
scores.getOrDefault("Unknown", 0);  // 0 — safe fallback

// Check
scores.containsKey("Bob");   // true
scores.containsValue(82);    // true
scores.size();                 // 2

// Iterate
for (Map.Entry<String, Integer> e : scores.entrySet()) {
    System.out.println(e.getKey() + " → " + e.getValue());
}
scores.forEach((k, v) -> System.out.println(k + " → " + v)); // Java 8+

// Powerful Map operations (Java 8+)
scores.putIfAbsent("Carol", 88);                   // only if key absent
scores.merge("Alice", 5, Integer::sum);           // 97 + 5 = 102
scores.computeIfAbsent("Dan", k -> fetchScore(k));  // compute and store if absent
scores.replaceAll((k, v) -> v + 10);               // bonus for everyone

// Word frequency — classic Map pattern
Map<String, Long> freq = new HashMap<>();
for (String word : words) {
    freq.merge(word, 1L, Long::sum);  // cleaner than getOrDefault pattern
}

// Immutable map (Java 9+)
Map<String, Integer> fixed = Map.of("A", 1, "B", 2);

Queue and Deque

A Queue processes elements in order — typically FIFO. A Deque (double-ended queue) supports insertion and removal at both ends. Prefer ArrayDeque over LinkedList for both — it's faster and uses less memory.

// Queue — FIFO processing (task queues, BFS)
Queue<String> queue = new ArrayDeque<>();
queue.offer("first");    // add to tail (prefer offer over add — no exception on full)
queue.offer("second");
queue.peek();             // "first" — look without removing
queue.poll();             // "first" — remove from head (returns null if empty, unlike remove())

// Deque — stack (LIFO) or double-ended queue
Deque<String> deque = new ArrayDeque<>();
deque.push("a");         // push to head (stack behaviour)
deque.push("b");
deque.pop();              // "b" — LIFO

// PriorityQueue — min-heap: poll() always returns the smallest element
Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1); pq.offer(3);
pq.poll();  // 1 — always the minimum
pq.poll();  // 3

// Max-heap: reverse comparator
Queue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

Choosing the Right Collection

Common Pitfalls

// ❌ Modifying a collection while iterating it with for-each
List<String> list = new ArrayList<>(List.of("a", "b", "c"));
for (String s : list) {
    if (s.equals("b")) list.remove(s);  // ConcurrentModificationException!
}

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

// ✅ Option 2: removeIf (Java 8+) — cleanest
list.removeIf(s -> s.equals("b"));

List<String> fixed = List.of("a", "b");
fixed.add("c");  // UnsupportedOperationException — not just unmodifiable, immutable

// ✅ If you need a mutable copy:
List<String> mutable = new ArrayList<>(List.of("a", "b"));

// ❌ Two threads writing to HashMap simultaneously → data corruption, infinite loops
Map<String, Integer> map = new HashMap<>();  // NOT thread-safe

// ✅ For concurrent access:
Map<String, Integer> map = new ConcurrentHashMap<>();

// ✅ For read-heavy, rare writes:
Map<String, Integer> map = Collections.synchronizedMap(new HashMap<>());

Senior Topics: Performance and Internals

HashMap internals — why initial capacity matters

// HashMap internally uses an array of buckets.
// Default capacity: 16. Load factor: 0.75 → resizes at 12 entries.
// Resize = new array (2x size) + rehash all entries = O(n) operation.

// ❌ If you know you'll store ~1000 entries, default capacity causes ~6 resizes
Map<String, User> cache = new HashMap<>();

// ✅ Set initial capacity to avoid resizes: size / loadFactor + 1
Map<String, User> cache = new HashMap<>(1334);  // 1000 / 0.75 ≈ 1334

// Java 8+: buckets with 8+ entries convert from linked list to red-black tree
// → worst-case O(n) degrades to O(log n) even with hash collisions

LinkedHashMap as LRU cache

// LinkedHashMap with accessOrder=true moves accessed entries to tail.
// Override removeEldestEntry() to evict when size exceeds limit.
int MAX = 100;
Map<String, User> lruCache = new LinkedHashMap<>(MAX, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, User> eldest) {
        return size() > MAX;  // evict oldest-accessed when over limit
    }
};
// Production: prefer Caffeine or Guava Cache for proper LRU with TTL support

Collections with Stream API

List<User> users = getUsers();

// Group by department → Map<String, List<User>>
Map<String, List<User>> byDept = users.stream()
    .collect(Collectors.groupingBy(User::getDepartment));

// Count per department → Map<String, Long>
Map<String, Long> countByDept = users.stream()
    .collect(Collectors.groupingBy(User::getDepartment, Collectors.counting()));

// Partition into active/inactive → Map<Boolean, List<User>>
Map<Boolean, List<User>> partitioned = users.stream()
    .collect(Collectors.partitioningBy(User::isActive));

// Collect to unmodifiable list (Java 16+)
List<String> names = users.stream().map(User::getName).toList();

Interview Questions