Java Notes

Collections Framework Overview

Complete guide to Java Collections Framework covering hierarchy, interfaces, implementations, algorithms, and choosing the right collection for your use case.

What is the Java Collections Framework?

The Java Collections Framework (JCF) is a unified architecture introduced in Java 1.2 that provides:

Interfaces — Abstract data types representing collections (List, Set, Map, Queue)
Implementations — Concrete classes (ArrayList, HashMap, TreeSet, etc.)
Algorithms — Static methods in the Collections utility class (sort, search, shuffle)

Before JCF, developers used Vector, Hashtable, and raw arrays with no common interface. Switching data structures meant rewriting code. JCF solved this by programming to interfaces.

java example

// Programming to an interface — you can swap implementations easily
List<String> names = new ArrayList<>();  // Can change to LinkedList without breaking code
names.add("Alice");
names.add("Bob");

The Iterable Interface

Iterable<E> is the root of the collection hierarchy. Any class that implements Iterable can be used in a for-each loop.

java example

public interface Iterable<T> {
    Iterator<T> iterator();

    // Java 8 default methods
    default void forEach(Consumer<? super T> action) { ... }
    default Spliterator<T> spliterator() { ... }
}

The Collection Interface

Collection<E> extends Iterable<E> and defines the core operations shared by all collections (except Map):

java example

public interface Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    boolean add(E e);
    boolean remove(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    boolean retainAll(Collection<?> c);
    void clear();
    // Java 8+
    default Stream<E> stream() { ... }
    default Stream<E> parallelStream() { ... }
    default boolean removeIf(Predicate<? super E> filter) { ... }
}

List Interface — Detailed

An ordered collection (sequence) that allows duplicate elements and provides positional access.

Key Methods (beyond Collection)

java example

E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
List<E> subList(int fromIndex, int toIndex);

Implementations Comparison

Feature	ArrayList	LinkedList	Vector	Stack
Internal Structure	Dynamic array	Doubly-linked list	Dynamic array	Dynamic array
Random Access	O(1)	O(n)	O(1)	O(1)
Insert/Delete (middle)	O(n)	O(1)*	O(n)	O(n)
Insert (end)	O(1) amortized	O(1)	O(1) amortized	O(1) amortized
Thread-safe	No	No	Yes (synchronized)	Yes (synchronized)
Memory Overhead	Low	High (node pointers)	Low	Low

*O(1) if you already have a reference to the node; O(n) to find the node first.

Set Interface — Detailed

A collection that contains no duplicate elements. Mathematically models the set abstraction.

How Duplicates Are Detected

Sets use equals() and hashCode() (for hash-based sets) or compareTo() (for sorted sets) to determine uniqueness.

java example

Set<String> colors = new HashSet<>();
colors.add("Red");
colors.add("Blue");
colors.add("Red");  // Duplicate — not added
System.out.println(colors.size());  // Output: 2

Implementations Comparison

Feature	HashSet	LinkedHashSet	TreeSet
Internal Structure	HashMap	LinkedHashMap	Red-Black Tree
Ordering	None	Insertion order	Sorted (natural/comparator)
add/remove/contains	O(1)	O(1)	O(log n)
null elements	One null allowed	One null allowed	No (throws NPE)
Implements	Set	Set	NavigableSet, SortedSet

Map Interface — Detailed

Maps keys to values. Each key maps to at most one value. Map does not extend Collection.

Key Methods

java example

V put(K key, V value);
V get(Object key);
V remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K,V>> entrySet();
// Java 8+
V getOrDefault(Object key, V defaultValue);
V putIfAbsent(K key, V value);
V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction);
void forEach(BiConsumer<? super K, ? super V> action);

Implementations Comparison

Feature	HashMap	LinkedHashMap	TreeMap	Hashtable
Internal Structure	Array + LinkedList/Tree	HashMap + Doubly-linked list	Red-Black Tree	Array + LinkedList
Ordering	None	Insertion/Access order	Sorted by key	None
get/put	O(1)	O(1)	O(log n)	O(1)
null keys	One null key	One null key	No	No
null values	Allowed	Allowed	Allowed	No
Thread-safe	No	No	No	Yes (synchronized)

Queue and Deque Interface — Detailed

Queue Methods

Operation	Throws Exception	Returns Special Value
Insert	`add(e)`	`offer(e)`
Remove	`remove()`	`poll()`
Examine	`element()`	`peek()`

Deque Methods (Double-Ended Queue)

java example

// First element operations
void addFirst(E e);    /    boolean offerFirst(E e);
E removeFirst();       /    E pollFirst();
E getFirst();          /    E peekFirst();

// Last element operations
void addLast(E e);     /    boolean offerLast(E e);
E removeLast();        /    E pollLast();
E getLast();           /    E peekLast();

// Stack operations (Deque preferred over Stack class)
void push(E e);        // addFirst
E pop();               // removeFirst
E peek();              // peekFirst

The Collections Utility Class

java.util.Collections provides static methods that operate on or return collections:

java example

// Sorting
Collections.sort(list);
Collections.sort(list, comparator);

// Searching (list must be sorted)
int index = Collections.binarySearch(list, key);

// Extremes
Collections.min(collection);
Collections.max(collection);

// Reordering
Collections.reverse(list);
Collections.shuffle(list);
Collections.swap(list, i, j);
Collections.rotate(list, distance);

// Frequency and disjoint
int count = Collections.frequency(collection, element);
boolean noCommon = Collections.disjoint(c1, c2);

// Unmodifiable wrappers
List<String> readOnly = Collections.unmodifiableList(list);

// Synchronized wrappers
List<String> syncList = Collections.synchronizedList(new ArrayList<>());

// Singleton and empty collections
List<String> single = Collections.singletonList("only");
List<String> empty = Collections.emptyList();

// Fill and copy
Collections.fill(list, "default");
Collections.copy(dest, src);

Collection vs Collections

`Collection` (Interface)	`Collections` (Utility Class)
`java.util.Collection`	`java.util.Collections`
Root interface for List, Set, Queue	Final class with static utility methods
Defines add, remove, contains, etc.	Provides sort, search, synchronize, etc.
You implement this interface	You call its static methods

Choosing the Right Collection

Decision Flowchart

├── YES	Need sorted keys?
│ ├── YES	TreeMap
│ └── NO	Need insertion order?
│ ├── YES	LinkedHashMap
│ └── NO	HashMap
└── NO	Need unique elements?
├── YES	Need sorted?
│ ├── YES	TreeSet
│ └── NO	Need insertion order?
│ ├── YES	LinkedHashSet
│ └── NO	HashSet
└── NO	Need FIFO/priority?
├── YES	PriorityQueue or ArrayDeque
└── NO	Need fast random access?
├── YES	ArrayList
└── NO	Need fast insert/delete?
├── YES	LinkedList
└── NO	ArrayList (default choice)

Quick Reference

Use Case	Best Choice
General-purpose list	ArrayList
Frequent insert/delete at both ends	ArrayDeque
Need stack behavior	ArrayDeque (not Stack)
Unique elements, fast lookup	HashSet
Unique elements, sorted	TreeSet
Key-value lookup	HashMap
Key-value with sorted keys	TreeMap
LRU Cache	LinkedHashMap (access order)
Thread-safe map	ConcurrentHashMap
Producer-consumer pattern	BlockingQueue implementations

Thread Safety in Collections

Legacy Synchronized Collections

Vector, Hashtable, Stack — synchronized on every method (poor performance)

Synchronized Wrappers

java example

List<String> syncList = Collections.synchronizedList(new ArrayList<>());
// Still need external synchronization for iteration:
synchronized (syncList) {
    for (String s : syncList) { ... }
}

Concurrent Collections (java.util.concurrent)

java example

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<>();
BlockingQueue<String> bq = new LinkedBlockingQueue<>();

These offer better concurrency without locking the entire collection.

Fail-Fast vs Fail-Safe Iterators

Fail-Fast (most collections)

Throw ConcurrentModificationException if collection is modified during iteration
Use an internal modCount variable

java example

List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
for (String s : list) {
    if (s.equals("B")) {
        list.remove(s);  // Throws ConcurrentModificationException!
    }
}

Fail-Safe (concurrent collections)

Work on a clone or snapshot — never throw CME
May not reflect latest modifications

java example

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>(Arrays.asList("A", "B", "C"));
for (String s : list) {
    if (s.equals("B")) {
        list.remove(s);  // Safe — iterates over snapshot
    }
}

Java 9+ Factory Methods

java example

// Immutable collections (Java 9+)
List<String> list = List.of("A", "B", "C");
Set<String> set = Set.of("X", "Y", "Z");
Map<String, Integer> map = Map.of("one", 1, "two", 2);

// Characteristics:
// - Immutable (UnsupportedOperationException on modification)
// - No null elements/keys/values
// - Serializable
// - Value-based (no identity guarantees)

Common Mistakes to Avoid

1. Modifying Collection During Iteration

java example

// WRONG — ConcurrentModificationException
for (String item : list) {
    if (condition) list.remove(item);
}

// CORRECT — Use Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (condition) it.remove();
}

// CORRECT — Java 8+
list.removeIf(item -> condition);

2. Not Overriding hashCode() with equals()

java example

// BROKEN — objects won't be found in HashSet/HashMap
class Person {
    String name;
    @Override
    public boolean equals(Object o) { ... }
    // Missing hashCode()! Two equal objects may hash differently.
}

3. Using Raw Types

java example

// WRONG — loses type safety
List names = new ArrayList();
names.add("hello");
names.add(42);  // No compile error, but ClassCastException at runtime

// CORRECT
List<String> names = new ArrayList<>();

4. Assuming Sorted Order from HashSet/HashMap

These provide NO ordering guarantees. Use TreeSet/TreeMap or LinkedHashSet/LinkedHashMap.

Performance Comparison Summary

Operation	ArrayList	LinkedList	HashSet	TreeSet	HashMap	TreeMap
add	O(1)*	O(1)	O(1)	O(log n)	O(1)	O(log n)
get/contains	O(1)	O(n)	O(1)	O(log n)	O(1)	O(log n)
remove	O(n)	O(1)**	O(1)	O(log n)	O(1)	O(log n)
Iteration	O(n)	O(n)	O(capacity)	O(n)	O(capacity)	O(n)

*Amortized — resize is O(n) but happens rarely **O(1) if you have the node reference; O(n) to search first

Complete Working Example

Here is a comprehensive example demonstrating the core collections in action:

java example

import java.util.*;

public class CollectionsDemo {
    public static void main(String[] args) {
        // List - ordered, allows duplicates
        List<String> fruits = new ArrayList<>();
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Apple");  // duplicate allowed
        fruits.add("Cherry");
        System.out.println("List: " + fruits);
        System.out.println("Element at index 1: " + fruits.get(1));
        
        // Set - no duplicates
        Set<String> uniqueFruits = new HashSet<>(fruits);
        System.out.println("\nSet (no duplicates): " + uniqueFruits);
        System.out.println("Set size: " + uniqueFruits.size());
        
        // Map - key-value pairs
        Map<String, Integer> fruitPrices = new HashMap<>();
        fruitPrices.put("Apple", 150);
        fruitPrices.put("Banana", 40);
        fruitPrices.put("Cherry", 200);
        System.out.println("\nMap: " + fruitPrices);
        System.out.println("Price of Apple: " + fruitPrices.get("Apple"));
        
        // Queue - FIFO
        Queue<String> queue = new LinkedList<>();
        queue.offer("First");
        queue.offer("Second");
        queue.offer("Third");
        System.out.println("\nQueue: " + queue);
        System.out.println("Poll: " + queue.poll());
        System.out.println("Queue after poll: " + queue);
        
        // Sorting
        Collections.sort(fruits);
        System.out.println("\nSorted List: " + fruits);
        
        // Unmodifiable collection
        List<String> immutable = Collections.unmodifiableList(fruits);
        System.out.println("Unmodifiable List: " + immutable);
    }
}

Output

List: [Apple, Banana, Apple, Cherry]
Element at index 1: Banana

Set (no duplicates): [Apple, Banana, Cherry]
Set size: 3

Map: {Apple=150, Banana=40, Cherry=200}
Price of Apple: 150

Queue: [First, Second, Third]
Poll: First
Queue after poll: [Second, Third]

Sorted List: [Apple, Apple, Banana, Cherry]
Unmodifiable List: [Apple, Apple, Banana, Cherry]

Interview Questions

Q1: What is the difference between Collection and Collections?

A: Collection is the root interface for List, Set, and Queue. Collections is a utility class with static methods like sort(), synchronizedList(), unmodifiableList().

Q2: Why doesn't Map extend Collection?

A: Because Map deals with key-value pairs, not individual elements. The semantics don't align — what would add(element) mean for a Map?

Q3: How do you make a collection thread-safe?

A: Three approaches: (1) Use legacy synchronized classes (Vector, Hashtable), (2) Use Collections.synchronizedXxx() wrappers, (3) Use java.util.concurrent classes (preferred).

Q4: What is the difference between fail-fast and fail-safe iterators?

A: Fail-fast iterators throw ConcurrentModificationException if the collection is modified during iteration. Fail-safe iterators work on a copy/snapshot and never throw CME.

Q5: When would you use LinkedList over ArrayList?

A: When you frequently add/remove elements at the beginning or middle (and already have a reference to the node). For most general use cases, ArrayList outperforms LinkedList due to CPU cache locality.

Q6: What happens if you don't override hashCode() when you override equals()?

A: Objects that are logically equal may end up in different hash buckets, making them unfindable in HashMap/HashSet.

Q7: What is the difference between Iterator and ListIterator?

A: Iterator is unidirectional (forward only) and works on any Collection. ListIterator is bidirectional (forward and backward), works only on Lists, and supports add/set operations during iteration.

Q8: What is the time complexity of common operations in ArrayList vs LinkedList?

A: ArrayList: get() is O(1), add/remove at end is O(1) amortized, add/remove at middle is O(n). LinkedList: get() is O(n), add/remove at ends is O(1), add/remove at middle is O(1) if you have the node reference (O(n) to find it).

Q9: How does HashMap handle collisions in Java 8+?

A: In Java 8+, HashMap uses a linked list for collisions initially. When the number of entries in a single bucket exceeds 8 (and total capacity ≥ 64), the linked list is converted to a balanced Red-Black tree (treeification), improving worst-case lookup from O(n) to O(log n).

Q10: What is the difference between Comparable and Comparator?

A: Comparable defines natural ordering within the class itself (implements compareTo()). Comparator defines external ordering in a separate class (implements compare()). Comparable allows only one sort sequence; Comparator allows multiple custom sort sequences.

Q11: Why is ConcurrentHashMap preferred over Hashtable?

A: ConcurrentHashMap uses segment-level (Java 7) or node-level (Java 8+) locking, allowing concurrent reads and limited concurrent writes without blocking the entire map. Hashtable synchronizes every method on the entire object, creating a bottleneck.

Q12: What happens if you modify a collection while iterating with for-each loop?

A: A ConcurrentModificationException is thrown because the for-each loop internally uses a fail-fast iterator. To safely remove during iteration, use Iterator.remove() or Collection.removeIf() (Java 8+).

Summary

The Java Collections Framework is the backbone of Java programming. Master these key points:

Program to interfaces — declare variables as List, Set, Map, not ArrayList, HashSet, HashMap
Know the Big O — choose the right implementation based on your access patterns
Override equals() AND hashCode() — always together for hash-based collections
Prefer concurrent collections over synchronized wrappers for multi-threaded code
Use Java 8+ features — removeIf(), forEach(), stream(), computeIfAbsent()
Use ArrayDeque instead of Stack class for stack/queue operations

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Collections Framework Overview.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.

Search Terms

java-master-course, java master course, java, master, course, collections, framework, collection

Continue learning this concept

Collections FrameworkCollections Practice ProgramsComprehensive Java Collections practice programs covering List, Set, Map, Queue operations with solutions, explanations, and time complexity analysis.Collections FrameworkComparable vs Comparator in JavaDeep dive into Comparable and Comparator interfaces in Java — natural ordering, custom sorting, lambda expressions, method references, and practical comparisons with examples.Collections FrameworkGenerics in JavaComplete guide to Java Generics — type parameters, bounded types, wildcards, type erasure, generic methods, generic classes, and common patterns with practical examples.Collections FrameworkIterator in JavaComplete guide to Iterator, ListIterator, and Iterable interfaces in Java — internal working, fail-fast behavior, custom iterators, and enhanced for-each loop mechanics.Collections FrameworkArrayList in JavaLearn ArrayList in Java from the ground up with clear explanations, practical examples, internal working, performance analysis, common pitfalls, and interview-focused insights designed for students and developers.Collections FrameworkLinkedList in JavaComplete guide to Java LinkedList — internal working with doubly-linked nodes, performance analysis, Deque operations, comparison with ArrayList, and when to use LinkedList.

PreviousWrapper Class in Java NextCollections Practice Programs

Java Notes

Collections Framework Overview

Complete guide to Java Collections Framework covering hierarchy, interfaces, implementations, algorithms, and choosing the right collection for your use case.

What is the Java Collections Framework?

The Java Collections Framework (JCF) is a unified architecture introduced in Java 1.2 that provides:

Interfaces — Abstract data types representing collections (List, Set, Map, Queue)
Implementations — Concrete classes (ArrayList, HashMap, TreeSet, etc.)
Algorithms — Static methods in the Collections utility class (sort, search, shuffle)

Before JCF, developers used Vector, Hashtable, and raw arrays with no common interface. Switching data structures meant rewriting code. JCF solved this by programming to interfaces.

java example

// Programming to an interface — you can swap implementations easily
List<String> names = new ArrayList<>();  // Can change to LinkedList without breaking code
names.add("Alice");
names.add("Bob");

The Iterable Interface

Iterable<E> is the root of the collection hierarchy. Any class that implements Iterable can be used in a for-each loop.

java example

public interface Iterable<T> {
    Iterator<T> iterator();

    // Java 8 default methods
    default void forEach(Consumer<? super T> action) { ... }
    default Spliterator<T> spliterator() { ... }
}

The Collection Interface

Collection<E> extends Iterable<E> and defines the core operations shared by all collections (except Map):

java example

public interface Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    boolean add(E e);
    boolean remove(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    boolean retainAll(Collection<?> c);
    void clear();
    // Java 8+
    default Stream<E> stream() { ... }
    default Stream<E> parallelStream() { ... }
    default boolean removeIf(Predicate<? super E> filter) { ... }
}

List Interface — Detailed

An ordered collection (sequence) that allows duplicate elements and provides positional access.

Key Methods (beyond Collection)

java example

E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
List<E> subList(int fromIndex, int toIndex);

Implementations Comparison

Feature	ArrayList	LinkedList	Vector	Stack
Internal Structure	Dynamic array	Doubly-linked list	Dynamic array	Dynamic array
Random Access	O(1)	O(n)	O(1)	O(1)
Insert/Delete (middle)	O(n)	O(1)*	O(n)	O(n)
Insert (end)	O(1) amortized	O(1)	O(1) amortized	O(1) amortized
Thread-safe	No	No	Yes (synchronized)	Yes (synchronized)
Memory Overhead	Low	High (node pointers)	Low	Low

*O(1) if you already have a reference to the node; O(n) to find the node first.

Set Interface — Detailed

A collection that contains no duplicate elements. Mathematically models the set abstraction.

How Duplicates Are Detected

Sets use equals() and hashCode() (for hash-based sets) or compareTo() (for sorted sets) to determine uniqueness.

java example

Set<String> colors = new HashSet<>();
colors.add("Red");
colors.add("Blue");
colors.add("Red");  // Duplicate — not added
System.out.println(colors.size());  // Output: 2

Implementations Comparison

Feature	HashSet	LinkedHashSet	TreeSet
Internal Structure	HashMap	LinkedHashMap	Red-Black Tree
Ordering	None	Insertion order	Sorted (natural/comparator)
add/remove/contains	O(1)	O(1)	O(log n)
null elements	One null allowed	One null allowed	No (throws NPE)
Implements	Set	Set	NavigableSet, SortedSet

Map Interface — Detailed

Maps keys to values. Each key maps to at most one value. Map does not extend Collection.

Key Methods

java example

V put(K key, V value);
V get(Object key);
V remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K,V>> entrySet();
// Java 8+
V getOrDefault(Object key, V defaultValue);
V putIfAbsent(K key, V value);
V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction);
void forEach(BiConsumer<? super K, ? super V> action);

Implementations Comparison

Feature	HashMap	LinkedHashMap	TreeMap	Hashtable
Internal Structure	Array + LinkedList/Tree	HashMap + Doubly-linked list	Red-Black Tree	Array + LinkedList
Ordering	None	Insertion/Access order	Sorted by key	None
get/put	O(1)	O(1)	O(log n)	O(1)
null keys	One null key	One null key	No	No
null values	Allowed	Allowed	Allowed	No
Thread-safe	No	No	No	Yes (synchronized)

Queue and Deque Interface — Detailed

Queue Methods

Operation	Throws Exception	Returns Special Value
Insert	`add(e)`	`offer(e)`
Remove	`remove()`	`poll()`
Examine	`element()`	`peek()`

Deque Methods (Double-Ended Queue)

java example

// First element operations
void addFirst(E e);    /    boolean offerFirst(E e);
E removeFirst();       /    E pollFirst();
E getFirst();          /    E peekFirst();

// Last element operations
void addLast(E e);     /    boolean offerLast(E e);
E removeLast();        /    E pollLast();
E getLast();           /    E peekLast();

// Stack operations (Deque preferred over Stack class)
void push(E e);        // addFirst
E pop();               // removeFirst
E peek();              // peekFirst

The Collections Utility Class

java.util.Collections provides static methods that operate on or return collections:

java example

// Sorting
Collections.sort(list);
Collections.sort(list, comparator);

// Searching (list must be sorted)
int index = Collections.binarySearch(list, key);

// Extremes
Collections.min(collection);
Collections.max(collection);

// Reordering
Collections.reverse(list);
Collections.shuffle(list);
Collections.swap(list, i, j);
Collections.rotate(list, distance);

// Frequency and disjoint
int count = Collections.frequency(collection, element);
boolean noCommon = Collections.disjoint(c1, c2);

// Unmodifiable wrappers
List<String> readOnly = Collections.unmodifiableList(list);

// Synchronized wrappers
List<String> syncList = Collections.synchronizedList(new ArrayList<>());

// Singleton and empty collections
List<String> single = Collections.singletonList("only");
List<String> empty = Collections.emptyList();

// Fill and copy
Collections.fill(list, "default");
Collections.copy(dest, src);

Collection vs Collections

`Collection` (Interface)	`Collections` (Utility Class)
`java.util.Collection`	`java.util.Collections`
Root interface for List, Set, Queue	Final class with static utility methods
Defines add, remove, contains, etc.	Provides sort, search, synchronize, etc.
You implement this interface	You call its static methods

Choosing the Right Collection

Decision Flowchart

├── YES	Need sorted keys?
│ ├── YES	TreeMap
│ └── NO	Need insertion order?
│ ├── YES	LinkedHashMap
│ └── NO	HashMap
└── NO	Need unique elements?
├── YES	Need sorted?
│ ├── YES	TreeSet
│ └── NO	Need insertion order?
│ ├── YES	LinkedHashSet
│ └── NO	HashSet
└── NO	Need FIFO/priority?
├── YES	PriorityQueue or ArrayDeque
└── NO	Need fast random access?
├── YES	ArrayList
└── NO	Need fast insert/delete?
├── YES	LinkedList
└── NO	ArrayList (default choice)

Quick Reference

Use Case	Best Choice
General-purpose list	ArrayList
Frequent insert/delete at both ends	ArrayDeque
Need stack behavior	ArrayDeque (not Stack)
Unique elements, fast lookup	HashSet
Unique elements, sorted	TreeSet
Key-value lookup	HashMap
Key-value with sorted keys	TreeMap
LRU Cache	LinkedHashMap (access order)
Thread-safe map	ConcurrentHashMap
Producer-consumer pattern	BlockingQueue implementations

Thread Safety in Collections

Legacy Synchronized Collections

Vector, Hashtable, Stack — synchronized on every method (poor performance)

Synchronized Wrappers

java example

List<String> syncList = Collections.synchronizedList(new ArrayList<>());
// Still need external synchronization for iteration:
synchronized (syncList) {
    for (String s : syncList) { ... }
}

Concurrent Collections (java.util.concurrent)

java example

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<>();
BlockingQueue<String> bq = new LinkedBlockingQueue<>();

These offer better concurrency without locking the entire collection.

Fail-Fast vs Fail-Safe Iterators

Fail-Fast (most collections)

Throw ConcurrentModificationException if collection is modified during iteration
Use an internal modCount variable

java example

List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
for (String s : list) {
    if (s.equals("B")) {
        list.remove(s);  // Throws ConcurrentModificationException!
    }
}

Fail-Safe (concurrent collections)

Work on a clone or snapshot — never throw CME
May not reflect latest modifications

java example

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>(Arrays.asList("A", "B", "C"));
for (String s : list) {
    if (s.equals("B")) {
        list.remove(s);  // Safe — iterates over snapshot
    }
}

Java 9+ Factory Methods

java example

// Immutable collections (Java 9+)
List<String> list = List.of("A", "B", "C");
Set<String> set = Set.of("X", "Y", "Z");
Map<String, Integer> map = Map.of("one", 1, "two", 2);

// Characteristics:
// - Immutable (UnsupportedOperationException on modification)
// - No null elements/keys/values
// - Serializable
// - Value-based (no identity guarantees)

Common Mistakes to Avoid

1. Modifying Collection During Iteration

java example

// WRONG — ConcurrentModificationException
for (String item : list) {
    if (condition) list.remove(item);
}

// CORRECT — Use Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (condition) it.remove();
}

// CORRECT — Java 8+
list.removeIf(item -> condition);

2. Not Overriding hashCode() with equals()

java example

// BROKEN — objects won't be found in HashSet/HashMap
class Person {
    String name;
    @Override
    public boolean equals(Object o) { ... }
    // Missing hashCode()! Two equal objects may hash differently.
}

3. Using Raw Types

java example

// WRONG — loses type safety
List names = new ArrayList();
names.add("hello");
names.add(42);  // No compile error, but ClassCastException at runtime

// CORRECT
List<String> names = new ArrayList<>();

4. Assuming Sorted Order from HashSet/HashMap

These provide NO ordering guarantees. Use TreeSet/TreeMap or LinkedHashSet/LinkedHashMap.

Performance Comparison Summary

Operation	ArrayList	LinkedList	HashSet	TreeSet	HashMap	TreeMap
add	O(1)*	O(1)	O(1)	O(log n)	O(1)	O(log n)
get/contains	O(1)	O(n)	O(1)	O(log n)	O(1)	O(log n)
remove	O(n)	O(1)**	O(1)	O(log n)	O(1)	O(log n)
Iteration	O(n)	O(n)	O(capacity)	O(n)	O(capacity)	O(n)

*Amortized — resize is O(n) but happens rarely **O(1) if you have the node reference; O(n) to search first

Complete Working Example

Here is a comprehensive example demonstrating the core collections in action:

java example

import java.util.*;

public class CollectionsDemo {
    public static void main(String[] args) {
        // List - ordered, allows duplicates
        List<String> fruits = new ArrayList<>();
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Apple");  // duplicate allowed
        fruits.add("Cherry");
        System.out.println("List: " + fruits);
        System.out.println("Element at index 1: " + fruits.get(1));
        
        // Set - no duplicates
        Set<String> uniqueFruits = new HashSet<>(fruits);
        System.out.println("\nSet (no duplicates): " + uniqueFruits);
        System.out.println("Set size: " + uniqueFruits.size());
        
        // Map - key-value pairs
        Map<String, Integer> fruitPrices = new HashMap<>();
        fruitPrices.put("Apple", 150);
        fruitPrices.put("Banana", 40);
        fruitPrices.put("Cherry", 200);
        System.out.println("\nMap: " + fruitPrices);
        System.out.println("Price of Apple: " + fruitPrices.get("Apple"));
        
        // Queue - FIFO
        Queue<String> queue = new LinkedList<>();
        queue.offer("First");
        queue.offer("Second");
        queue.offer("Third");
        System.out.println("\nQueue: " + queue);
        System.out.println("Poll: " + queue.poll());
        System.out.println("Queue after poll: " + queue);
        
        // Sorting
        Collections.sort(fruits);
        System.out.println("\nSorted List: " + fruits);
        
        // Unmodifiable collection
        List<String> immutable = Collections.unmodifiableList(fruits);
        System.out.println("Unmodifiable List: " + immutable);
    }
}

Output

List: [Apple, Banana, Apple, Cherry]
Element at index 1: Banana

Set (no duplicates): [Apple, Banana, Cherry]
Set size: 3

Map: {Apple=150, Banana=40, Cherry=200}
Price of Apple: 150

Queue: [First, Second, Third]
Poll: First
Queue after poll: [Second, Third]

Sorted List: [Apple, Apple, Banana, Cherry]
Unmodifiable List: [Apple, Apple, Banana, Cherry]

Interview Questions

Q1: What is the difference between Collection and Collections?

A: Collection is the root interface for List, Set, and Queue. Collections is a utility class with static methods like sort(), synchronizedList(), unmodifiableList().

Q2: Why doesn't Map extend Collection?

A: Because Map deals with key-value pairs, not individual elements. The semantics don't align — what would add(element) mean for a Map?

Q3: How do you make a collection thread-safe?

A: Three approaches: (1) Use legacy synchronized classes (Vector, Hashtable), (2) Use Collections.synchronizedXxx() wrappers, (3) Use java.util.concurrent classes (preferred).

Q4: What is the difference between fail-fast and fail-safe iterators?

A: Fail-fast iterators throw ConcurrentModificationException if the collection is modified during iteration. Fail-safe iterators work on a copy/snapshot and never throw CME.

Q5: When would you use LinkedList over ArrayList?

Q6: What happens if you don't override hashCode() when you override equals()?

A: Objects that are logically equal may end up in different hash buckets, making them unfindable in HashMap/HashSet.

Q7: What is the difference between Iterator and ListIterator?

Q8: What is the time complexity of common operations in ArrayList vs LinkedList?

Q9: How does HashMap handle collisions in Java 8+?

Q10: What is the difference between Comparable and Comparator?

Q11: Why is ConcurrentHashMap preferred over Hashtable?

Q12: What happens if you modify a collection while iterating with for-each loop?

Summary

The Java Collections Framework is the backbone of Java programming. Master these key points:

Program to interfaces — declare variables as List, Set, Map, not ArrayList, HashSet, HashMap
Know the Big O — choose the right implementation based on your access patterns
Override equals() AND hashCode() — always together for hash-based collections
Prefer concurrent collections over synchronized wrappers for multi-threaded code
Use Java 8+ features — removeIf(), forEach(), stream(), computeIfAbsent()
Use ArrayDeque instead of Stack class for stack/queue operations

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Collections Framework Overview.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.

Search Terms

java-master-course, java master course, java, master, course, collections, framework, collection

Continue learning this concept

PreviousWrapper Class in Java NextCollections Practice Programs