11.1 Collection Framework Overview

Why Collections?

Arrays are Java's most basic way to store multiple values, but they have a critical limitation: their size is fixed at creation. If you create an array for 10 students and an 11th enrolls, you must create a new larger array and copy everything over.

The Java Collection Framework solves this by providing a unified set of interfaces and classes for storing and manipulating groups of objects — with dynamic sizing, rich operations, and well-defined behavioral contracts.

---

1. Collection Framework Hierarchy

The framework is organized around a set of core interfaces:

java.lang.Iterable
    └── java.util.Collection
            ├── List         (ordered, allows duplicates)
            │     ├── ArrayList
            │     ├── LinkedList
            │     └── Vector (legacy)
            ├── Set          (no duplicates)
            │     ├── HashSet
            │     ├── LinkedHashSet
            │     └── TreeSet
            └── Queue        (FIFO / priority)
                  ├── LinkedList
                  ├── PriorityQueue
                  └── Deque
                        └── ArrayDeque

java.util.Map  (key-value pairs — NOT a Collection)
      ├── HashMap
      ├── LinkedHashMap
      └── TreeMap

Map does not extend Collection, but it is part of the collection framework and works closely with it.

---

2. Core Interfaces

List — Ordered, Allows Duplicates

import java.util.List;
import java.util.ArrayList;

List<String> names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
names.add("Alice"); // duplicates allowed

System.out.println(names.get(0)); // Alice  — access by index
System.out.println(names.size()); // 3
System.out.println(names);        // [Alice, Bob, Alice]

Set — Unordered, No Duplicates

import java.util.Set;
import java.util.HashSet;

Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("spring");
tags.add("java"); // duplicate — silently ignored

System.out.println(tags.size()); // 2
System.out.println(tags.contains("java")); // true

Map — Key-Value Pairs

import java.util.Map;
import java.util.HashMap;

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 95);
scores.put("Bob", 87);

System.out.println(scores.get("Alice")); // 95
System.out.println(scores.containsKey("Bob")); // true
System.out.println(scores.size()); // 2

Queue — FIFO Processing

import java.util.Queue;
import java.util.LinkedList;

Queue<String> queue = new LinkedList<>();
queue.offer("First");
queue.offer("Second");
queue.offer("Third");

System.out.println(queue.poll()); // First (removed)
System.out.println(queue.peek()); // Second (not removed)

---

3. Generics — Type-Safe Collections

Before Java 5, collections stored Object references, requiring casts and risking ClassCastException at runtime. Generics solve this by specifying the element type at compile time:

import java.util.ArrayList;
import java.util.List;

// Without generics (Java 1.4 and older — avoid!)
List rawList = new ArrayList();
rawList.add("text");
rawList.add(42); // compiles, but mixing types is dangerous
String s = (String) rawList.get(1); // ClassCastException at runtime!

// With generics (modern Java)
List<String> typedList = new ArrayList<>();
typedList.add("text");
// typedList.add(42); // compile error — caught early!
String result = typedList.get(0); // no cast needed

Generic syntax:

List<String>            list;   // List of Strings
Map<String, Integer>    map;    // Map: String keys, Integer values
Set<Double>             set;    // Set of Doubles

// Multiple type parameters
Map<String, List<Integer>> mapOfLists = new HashMap<>();

// Diamond operator (Java 7+): type inferred from declaration
List<String> names = new ArrayList<>();  // type inferred

---

4. Iterator — Traversal

Every Collection implements Iterable, giving it an iterator() method for traversal. Modern Java uses the enhanced for-each loop, which calls the iterator internally:

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

List<String> fruits = new ArrayList<>(List.of("apple", "banana", "cherry"));

// Enhanced for-each (recommended)
for (String fruit : fruits) {
    System.out.println(fruit);
}

// Explicit Iterator (needed when removing during iteration)
Iterator<String> it = fruits.iterator();
while (it.hasNext()) {
    String fruit = it.next();
    if (fruit.startsWith("b")) {
        it.remove(); // safe removal during iteration
    }
}
System.out.println(fruits); // [apple, cherry]

// forEach with lambda (Java 8+)
fruits.forEach(f -> System.out.println(f.toUpperCase()));
fruits.forEach(System.out::println); // method reference

warning

Never modify a collection while iterating with a for-each loop— it causes ConcurrentModificationException. Use Iterator.remove() or removeIf() instead.

---

5. Choosing the Right Collection

Need	Best Choice	Reason
Ordered list, fast random access	ArrayList	O(1) get by index
Ordered list, frequent insert/delete at ends	LinkedList (as Deque)	O(1) add/remove at head/tail
Fast lookup, no duplicates	HashSet	O(1) average contains
No duplicates, maintain insertion order	LinkedHashSet	Ordered HashSet
No duplicates, sorted order	TreeSet	O(log n), natural sort
Fast key-value lookup	HashMap	O(1) average get/put
Key-value, insertion order preserved	LinkedHashMap	Ordered HashMap
Key-value, sorted by key	TreeMap	O(log n), natural sort
FIFO queue	ArrayDeque	Faster than LinkedList
Priority-based processing	PriorityQueue	Heap-based, O(log n) poll

---

6. Common Collection Methods

Most collections share these Collection interface methods:

import java.util.*;

List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6));

// Size and emptiness
System.out.println(list.size());     // 8
System.out.println(list.isEmpty());  // false

// Search
System.out.println(list.contains(5));   // true
System.out.println(list.indexOf(1));    // 1 (first occurrence)

// Modification
list.add(7);              // append
list.add(0, 0);           // insert at index 0
list.remove(Integer.valueOf(9)); // remove by value (not index!)
list.remove(0);           // remove by index

// Bulk operations
List<Integer> other = List.of(1, 2, 3);
list.containsAll(other);  // true if all elements of other are in list
list.addAll(other);       // append all elements
list.removeAll(other);    // remove all elements that exist in other
list.retainAll(other);    // keep only elements also in other

// Convert
Object[] array = list.toArray();          // to array
List<Integer> copy = new ArrayList<>(list); // defensive copy

// Clear
list.clear();
System.out.println(list.isEmpty()); // true

---

7. Immutable Collections (Java 9+)

Factory methods create compact, truly immutable collections:

import java.util.List;
import java.util.Set;
import java.util.Map;

// List.of — immutable, no nulls, preserves order
List<String> immutableList = List.of("apple", "banana", "cherry");

// Set.of — immutable, no duplicates, no nulls
Set<Integer> immutableSet = Set.of(1, 2, 3, 4, 5);

// Map.of — immutable, key-value pairs
Map<String, Integer> immutableMap = Map.of(
    "Alice", 95,
    "Bob",   87,
    "Carol", 92
);

// Attempting modification throws UnsupportedOperationException
// immutableList.add("date"); // throws!

// Create mutable copy when modification is needed
List<String> mutable = new ArrayList<>(immutableList);
mutable.add("date"); // OK

---

Pro Tips

Use interface types on the left side:

// GOOD: program to interface
List<String> list = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();

// BAD: unnecessarily specific
ArrayList<String> list = new ArrayList<>();

This makes it easy to swap implementations later without changing any other code.

Prefer List.copyOf(), Set.copyOf(), Map.copyOf() (Java 10+) for making immutable snapshots of existing collections:

List<String> original = new ArrayList<>(List.of("a", "b", "c"));
List<String> snapshot = List.copyOf(original); // immutable copy
original.add("d"); // does not affect snapshot