Junior Level

The Collection Framework is a set of interfaces and classes in Java for working with groups of objects.

Main interfaces:

Interface	What it does	Examples
List	Ordered list, allows duplicates	ArrayList, LinkedList
Set	Only unique elements	HashSet, TreeSet
Queue	Queue (FIFO)	PriorityQueue, ArrayDeque
Map	Key-value pairs	HashMap, TreeMap

Map technically does NOT inherit from Collection (it’s a parallel interface), but is included in the Collection Framework for completeness.

Simple analogy:

• List = shopping list (order matters, repetitions allowed)
• Set = set of unique keys (order doesn’t matter, no repetitions)
• Queue = line at a store (first come, first served)
• Map = dictionary (word -> definition)

Example:

List<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Apple");  // Duplicates allowed

Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Apple");  // Won't be added (already exists)

**How Set detects duplicates:** `HashSet` calls `hashCode()` to find the "bucket" and `equals()` to check for a match within it. That's why elements must correctly implement `hashCode()` and `equals()`.

Map<String, Integer> map = new HashMap<>();
map.put("Apple", 1);
map.put("Banana", 2);

---

Middle Level

Interface Hierarchy

Iterable<E>
  └── Collection<E>
       ├── List<E>         ← Ordered, duplicates OK
       │    ├── ArrayList
       │    └── LinkedList
       ├── Set<E>          ← Unique elements
       │    ├── HashSet
       │    ├── LinkedHashSet
       │    └── TreeSet (SortedSet)
       └── Queue<E>        ← Queue
            ├── PriorityQueue
            └── Deque
                 └── ArrayDeque

Map<K,V> (NOT inherited from Collection!)
  ├── HashMap
  ├── LinkedHashMap
  └── TreeMap (SortedMap)

Key Features

List:

• Access by index: list.get(0)
• Preserves insertion order
• Allows duplicates

Set:

• Uniqueness via equals() and hashCode()
• HashSet: order not guaranteed
• LinkedHashSet: insertion order
• TreeSet: sorted

Queue:

• FIFO (First-In-First-Out)
• Methods: offer(), poll(), peek()
• PriorityQueue: extraction by priority

Map:

• Key-value pairs
• Keys are unique
• get(key), put(key, value)

Marker Interfaces

RandomAccess — a marker interface with no methods. It simply tells the JDK: “this list supports fast random access by index”, so it can choose the optimal algorithm (e.g., for sorting).

// RandomAccess — fast access by index
ArrayList implements RandomAccess   // get(i) = O(1)
LinkedList                          // get(i) = O(n), no RandomAccess

// NavigableSet — navigation over elements
TreeSet implements NavigableSet
  → lower(e), floor(e), ceiling(e), higher(e)

Fail-Fast vs Fail-Safe

Fail-Fast = the collection tracks modifications via modCount (modification counter) and throws ConcurrentModificationException when changes are detected during iteration. This is a single-threaded bug detector, not a synchronization mechanism.

Fail-Safe = the iterator works with a copy of the data (snapshot), so changes to the original don’t affect iteration. Never throws ConcurrentModificationException.

// Fail-Fast (ArrayList, HashMap)
List<String> list = new ArrayList<>();
Iterator<String> it = list.iterator();
list.add("new");    // Modification
it.next();          // → ConcurrentModificationException!

// Fail-Safe (CopyOnWriteArrayList, ConcurrentHashMap)
List<String> safe = new CopyOnWriteArrayList<>();
Iterator<String> safeIt = safe.iterator();
safe.add("new");    // Modification
safeIt.next();      // → Works (iterator over a copy)

---

Senior Level

Java 21: Sequenced Collections (JEP 431)

Most production systems run on Java 11/17, where SequencedCollection is unavailable. Use concrete types (ArrayList, LinkedList) with methods like get(0)/get(size-1).

// New interface for collections with predictable iteration order
SequencedCollection<E>
  → addFirst(e), addLast(e)
  → getFirst(), getLast()
  → reversed()      // Reverse-order view

// Inheritors: List, Deque

SequencedSet<E>
  → Implementations: LinkedHashSet, SortedSet

SequencedMap<K, V>
  → firstEntry(), lastEntry()
  → reversed()
  → Implementations: LinkedHashMap, SortedMap

Before Java 21: No common interface for “first/last element” After Java 21: Unified contract for all ordered collections

Spliterator (Java 8+)

// Iterator replacement for Stream API
Spliterator<E> spliterator = list.spliterator();

// Characteristics:
// IMMUTABLE    → collection doesn't change
// CONCURRENT   → can be modified concurrently
// DISTINCT     → all elements are unique
// SORTED       → elements are sorted
// ORDERED      → order matters

// Stream API uses these characteristics for parallel processing optimizations
// (e.g., DISTINCT avoids redundant checks, SORTED skips re-sorting)
spliterator.trySplit()  // Split for parallel processing

Under the Hood: RandomAccess Optimization

// JDK checks RandomAccess to choose algorithm
Collections.binarySearch(list, key);

// Inside JDK:
if (list instanceof RandomAccess) {
    // Binary search by index → O(log n)
    for (int i = 0; i < size; i++) { ... }
} else {
    // Iteration → O(n log n) for LinkedList!
    ListIterator<E> it = list.listIterator();
}

Map: Why NOT a Collection?

Map works with PAIRS (Key-Value)
Collection works with SINGLE elements

Map.Entry<K,V> — inner interface for a pair
  → getKey(), getValue(), setValue()

Therefore Map is a parallel branch, not a Collection!

Optional Operations

// Many Collection methods = "optional operation"
// Unmodifiable collections throw UnsupportedOperationException

list.add(e)      // May throw!
list.remove(e)   // May throw!
list.clear()     // May throw!

// Why? To support immutable collections:
List<String> unmodifiable = Collections.unmodifiableList(list);
unmodifiable.add("x");  // → UnsupportedOperationException!

Production Experience

Real scenario: LinkedList killed performance

• Application: 1 million elements in LinkedList
• Problem: 10 seconds for iteration, 500 MB memory
• Solution: replaced with ArrayList
• Result: 50 ms, 50 MB (200x speedup!)

Best Practices

1. Interface in signature: List<String>, not ArrayList<String>
2. Collection if only iteration is needed
3. SequencedCollection (Java 21) for first/last access
4. RandomAccess check for for-i loops
5. Fail-Safe collections for multi-threading
6. Avoid Vector, Stack, Hashtable (legacy)
7. Spliterator for custom parallel streams

Senior Summary

• JCF = unified architecture for collections
• SequencedCollection (Java 21) = new standard for ordered collections
• RandomAccess = marker for algorithm optimization
• Spliterator = foundation of parallel Stream API
• Optional operations = support for unmodifiable collections
• Map != Collection (pairs vs single elements)
• Fail-Fast = modification -> exception
• Legacy (Vector/Stack) = avoid

---

Interview Cheat Sheet

Must know:

• Collection Framework = Iterable -> Collection (List, Set, Queue) + Map (parallel branch)
• Map does NOT inherit from Collection — works with Key-Value pairs, not single elements
• List = ordered, duplicates OK; Set = unique elements; Queue = FIFO
• Fail-Fast = modification during iteration -> ConcurrentModificationException (via modCount)
• Fail-Safe = iterator over a copy (snapshot), never throws exception
• RandomAccess — marker interface with no methods, signals fast index-based access
• Java 21: SequencedCollection unifies first/last/reversed access for List and Deque
• Spliterator — Iterator replacement for Stream API, contains characteristics for parallel optimization

Common follow-up questions:

• Why is Map not part of Collection? — Map works with pairs (K,V), Collection works with single elements
• How does Fail-Fast differ from Fail-Safe? — Fail-Fast throws exception on modification, Fail-Safe works with a copy
• What is RandomAccess for? — JDK uses it to choose algorithm (binary search by index vs iteration)
• What are optional operations? — Methods like add()/remove() may throw UnsupportedOperationException for unmodifiable collections

Red flags (DO NOT say):

• “Map inherits from Collection” — it’s a parallel branch
• “Vector is a good choice for multi-threading” — it’s legacy, use CopyOnWriteArrayList or ConcurrentHashMap
• “Fail-Fast guarantees thread-safety” — it’s a single-threaded bug detector, not synchronization
• “Spliterator is the same as Iterator” — Spliterator supports parallel processing via trySplit()

Related topics:

• [[2. What is the difference between List, Set and Queue]]
• [[7. What is Vector and how does it differ from ArrayList]]
• [[9. What is Queue and what implementations exist]]
• [[5. What is the time complexity of operations in ArrayList]]