Java Collections Framework

The Java Collections Framework is a unified set of interfaces and classes for storing, retrieving, and manipulating groups of objects. Rather than writing your own resizable array or hash table from scratch, you reach for a small number of well-tested interfaces — List, Set, Map, and Queue — backed by proven implementations like ArrayList, HashSet, and HashMap. Almost every real Java program manipulates data in bulk, so knowing how these types behave internally, and which one to reach for, is one of the highest-leverage skills a Java developer can build. This lesson covers the whole framework: the interface hierarchy, the major implementations, how they work under the hood, and the mistakes that trip up even experienced programmers.

Overview / How It Works

At the top of the framework sits the Iterable interface, which guarantees that any implementing type can be walked with a for-each loop. Collection extends Iterable and adds the core operations every collection shares: add, remove, size, contains, isEmpty, and iterator. Three sibling interfaces extend Collection, each with a different contract:

  • List — an ordered sequence that allows duplicate elements and lets you access items by numeric index, similar to an array that can grow.
  • Set — a collection that forbids duplicate elements, modeling mathematical set semantics.
  • Queue (and its sub-interface Deque) — a collection designed for holding elements prior to processing, typically in first-in-first-out or last-in-first-out order.

Map is deliberately not part of the Collection hierarchy, because it stores key-value pairs rather than single elements — but it is still considered part of the Collections Framework, and every Map exposes its keys, values, and entries as Set and Collection views so you can iterate over them.

Every one of these interfaces is generic, written as List<E>, Set<E>, Map<K, V>, and so on, where E, K, and V are type parameters you supply. This gives you compile-time type safety: a List<String> simply cannot accept an Integer, and the compiler inserts the necessary casts for you when you read elements back out, so you never see a ClassCastException from correctly-typed generic code. Because primitives cannot be used as generic type arguments, collections of numbers actually store the boxed wrapper types (Integer, Double, and so on); Java automatically converts between primitive and wrapper via autoboxing and unboxing, which is convenient but has real performance and memory costs for large collections of numbers.

The framework also ships a utility class, java.util.Collections, with static helper methods — Collections.sort, Collections.reverse, Collections.unmodifiableList, Collections.max, and more — that operate on any collection through its interface, regardless of the concrete implementation behind it.

Syntax

Collections are almost always declared using the interface type on the left and a concrete implementation on the right — a practice called "programming to the interface":

InterfaceType<ElementType> variableName = new ImplementationClass<>();

The empty angle brackets <> on the right side use the diamond operator, which tells the compiler to infer the generic type from the left-hand side instead of repeating it. The table below summarizes the main interfaces, their common implementations, and their behavior around ordering, duplicates, and null.

Interface Common Implementations Ordering Duplicates Null Elements
List ArrayList, LinkedList Insertion order, indexable Allowed Allowed
Set HashSet, LinkedHashSet, TreeSet None / insertion / sorted Not allowed HashSet allows one; TreeSet does not
Map HashMap, LinkedHashMap, TreeMap None / insertion / sorted by key Keys unique, values may repeat HashMap allows one null key; TreeMap does not
Queue / Deque LinkedList, ArrayDeque, PriorityQueue FIFO, LIFO, or priority order Allowed (usually) Generally disallowed

Examples

Example 1: List basics with ArrayList

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

public class Main {
    public static void main(String[] args) {
        List<String> fruits = new ArrayList<>();
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Cherry");
        fruits.add(1, "Blueberry");

        System.out.println("Fruits: " + fruits);
        System.out.println("Size: " + fruits.size());
        System.out.println("First: " + fruits.get(0));

        fruits.remove("Banana");
        System.out.println("After removal: " + fruits);

        for (String fruit : fruits) {
            System.out.println("- " + fruit);
        }
    }
}

Output:

Fruits: [Apple, Blueberry, Banana, Cherry]
Size: 4
First: Apple
After removal: [Apple, Blueberry, Cherry]
- Apple
- Blueberry
- Cherry

This shows the core List operations: add appends to the end, the overloaded add(index, element) inserts at a specific position and shifts later elements right, get(index) retrieves by position, and remove(Object) removes the first matching element by value (there is also a remove(int index) overload that removes by position — a frequent source of confusion with Integer lists).

Example 2: Set uniqueness and ordering with HashSet and TreeSet

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

public class Main {
    public static void main(String[] args) {
        Set<Integer> hashSet = new HashSet<>();
        hashSet.add(42);
        hashSet.add(7);
        hashSet.add(19);
        hashSet.add(7); // duplicate, silently ignored

        Set<Integer> treeSet = new TreeSet<>(hashSet);

        System.out.println("HashSet: " + hashSet);
        System.out.println("TreeSet (sorted): " + treeSet);
        System.out.println("Contains 19? " + treeSet.contains(19));
    }
}

Output:

HashSet: [19, 7, 42]
TreeSet (sorted): [7, 19, 42]
Contains 19? true

Adding 7 a second time has no effect — Set silently ignores duplicates instead of throwing. HashSet gives no ordering guarantee at all (the order shown here comes from how Integer hash codes map to internal buckets, and is an implementation detail you should never rely on); if you need sorted order, wrap or copy into a TreeSet, which keeps elements sorted at all times using their natural ordering or a supplied Comparator.

Example 3: Map basics with HashMap

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

public class Main {
    public static void main(String[] args) {
        String text = "the quick brown fox jumps over the lazy dog the fox runs";
        String[] words = text.split(" ");

        Map<String, Integer> frequency = new HashMap<>();
        for (String word : words) {
            frequency.put(word, frequency.getOrDefault(word, 0) + 1);
        }

        System.out.println("Unique words: " + frequency.size());
        System.out.println("Count of 'the': " + frequency.get("the"));
        System.out.println("Count of 'fox': " + frequency.get("fox"));
        System.out.println("Count of 'dog': " + frequency.get("dog"));
    }
}

Output:

Unique words: 9
Count of 'the': 3
Count of 'fox': 2
Count of 'dog': 1

This is the classic word-frequency-counter pattern, and it’s the single most useful trick to know with Map: getOrDefault(key, 0) reads the current count (or 0 if the key hasn’t been seen yet) so you never need to check containsKey first. put both inserts new keys and overwrites the value of existing ones, which is exactly what makes running totals like this work in a single line.

How It Works Step by Step / Under the Hood

ArrayList is backed by a plain Object[] array. When you construct it with no arguments, it starts empty and allocates a default-capacity array (historically 10) lazily on the first insert. When the backing array fills up, ArrayList allocates a new array roughly 1.5x the size, copies every element across with System.arraycopy, and discards the old array. This means get(index) is O(1) (direct array access), appending is amortized O(1) (occasional resizes are spread across many cheap inserts), but inserting or removing from the middle or front is O(n) because everything after the index has to shift.

LinkedList instead stores each element in its own node object holding a reference to the previous and next node (a doubly linked list). This makes adding or removing from either end O(1) and makes it a good Deque implementation, but random access via get(index) is O(n) because the list must be walked node by node from whichever end is closer.

HashMap (and HashSet, which is literally implemented as a HashMap under the hood with dummy values) stores entries in an array of "buckets." When you call put(key, value), Java computes key.hashCode(), spreads those bits with an internal mixing function, and uses the result modulo the array length to pick a bucket index. Each bucket holds a small linked list of entries that landed in the same slot; if a bucket ever accumulates 8 or more entries (a rare but possible hash-collision scenario) and the table is large enough, Java 8+ converts that bucket into a balanced red-black tree so worst-case lookup stays O(log n) instead of degrading to O(n). When the map’s load factor (default 0.75, meaning it’s 75% full) is exceeded, the entire table doubles in size and every entry is rehashed into the new, larger array. Two objects are only ever treated as the "same key" if both equals() returns true and hashCode() returns the same value — which is why overriding one without the other breaks HashMap and HashSet silently.

TreeMap and TreeSet use a self-balancing red-black tree instead of a hash table, keeping every key in sorted order at all times at the cost of O(log n) for insert, lookup, and delete rather than HashMap’s average O(1).

Finally, most collection iterators are fail-fast: every structural change (add or remove, but not set) increments an internal counter called modCount. Each call to the iterator’s next() checks that modCount still matches the value recorded when iteration started; if it doesn’t, the iterator throws ConcurrentModificationException rather than silently returning corrupted results. This is a deliberate safety feature, not a bug — it exists to catch exactly the mistake shown below.

Common Mistakes

Mistake 1: Forgetting to override equals() and hashCode()

Custom classes used as Set elements or Map keys must override both equals() and hashCode(), or every instance is compared by object identity instead of by its field values:

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

class Point {
    int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }
}

public class Main {
    public static void main(String[] args) {
        Set<Point> points = new HashSet<>();
        points.add(new Point(1, 2));
        points.add(new Point(1, 2));
        System.out.println("Size: " + points.size());
    }
}

Output:

Size: 2

Even though both points hold the same coordinates, Point inherits Object‘s default equals(), which only returns true for the exact same reference. The fix is to override both methods so equal field values produce equal hash codes and report as equal:

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

class Point {
    int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof Point)) return false;
        Point other = (Point) obj;
        return x == other.x && y == other.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

public class Main {
    public static void main(String[] args) {
        Set<Point> points = new HashSet<>();
        points.add(new Point(1, 2));
        points.add(new Point(1, 2));
        System.out.println("Size: " + points.size());
    }
}

Output:

Size: 1

Mistake 2: Removing from a List while iterating with for-each

Calling a collection’s own remove method during a for-each loop modifies the list out from under the active iterator:

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

public class Main {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        names.add("Ann");
        names.add("Bob");
        names.add("Cid");
        names.add("Dan");

        for (String name : names) {
            if (name.equals("Bob")) {
                names.remove(name);
            }
        }
        System.out.println(names);
    }
}

Output:

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java)
	at Main.main(Main.java)

The for-each loop uses a hidden Iterator whose fail-fast check trips the moment names.remove(...) changes modCount. The fix is to remove through the iterator itself, which is allowed to update its own bookkeeping safely:

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

public class Main {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        names.add("Ann");
        names.add("Bob");
        names.add("Cid");
        names.add("Dan");

        Iterator<String> it = names.iterator();
        while (it.hasNext()) {
            String name = it.next();
            if (name.equals("Bob")) {
                it.remove();
            }
        }
        System.out.println(names);
    }
}

Output:

[Ann, Cid, Dan]

Best Practices

  • Declare variables using the interface type (List, Set, Map) and construct with a concrete class, so you can swap implementations later without touching calling code.
  • Default to ArrayList for lists, HashMap for maps, and HashSet for sets unless you specifically need insertion order (LinkedHashSet / LinkedHashMap) or sorted order (TreeSet / TreeMap).
  • Always override equals() and hashCode() together on any class you plan to store in a HashSet or use as a HashMap key.
  • Never structurally modify a collection while iterating it with for-each; use Iterator.remove(), a ListIterator, or removeIf() instead.
  • Prefer removeIf(predicate) over manual iteration when you just need to delete elements matching a condition — it’s shorter and avoids the comodification trap entirely.
  • Use Collections.unmodifiableList() or the List.of(...) / Map.of(...) factory methods to create read-only collections when data shouldn’t change after construction.
  • When you know the approximate final size in advance, construct the collection with an initial-capacity hint (for example new ArrayList<>(1000)) to avoid repeated resizing.
  • Avoid boxing overhead in hot numeric loops by considering specialized structures or primitive arrays instead of List<Integer> when performance is critical.

Practice Exercises

  • Write a program that reads a sentence from the user with Scanner, splits it into words, and uses a HashMap<String, Integer> to print how many times each distinct word appears.
  • Create a TreeSet<Integer>, insert ten random or user-supplied numbers (including some duplicates), and print the set to confirm duplicates were dropped and the values are sorted ascending.
  • Given a List<Integer> of exam scores, use Iterator (not for-each) to remove every score below 60, then print the remaining passing scores.

Summary

  • The Collections Framework centers on four interfaces: List (ordered, duplicates allowed), Set (no duplicates), Map (key-value pairs), and Queue/Deque (processing order).
  • ArrayList is a growable array with fast random access; LinkedList is a doubly linked list with fast insertion at the ends.
  • HashMap/HashSet use hash buckets built from hashCode() for near O(1) average performance; overriding equals() without hashCode() (or vice versa) silently breaks them.
  • TreeMap/TreeSet keep elements sorted using a red-black tree, at O(log n) cost per operation.
  • Iterators are fail-fast: structurally modifying a collection outside the iterator during iteration throws ConcurrentModificationException; use Iterator.remove() or removeIf() instead.
  • Program to the interface, choose the implementation that matches your ordering and performance needs, and always pair equals() with hashCode().