The Collections Framework

This section documents the current Java release line, with Java 25 LTS as the reference point (no specific patch version is pinned), as published at the Java developer portal, the Java Tutorials, and the Java SE API specification — which are the references these pages are written and verified against.

This content was generated with the assistance of AI and should be verified against the official documentation before being relied on in production.

This section’s bibliography lists the reference material consulted while preparing these pages.

The collections framework in java.util is a small set of interfaces for groups of objects together with several general-purpose implementations of each. The rule of thumb is: declare variables and parameters with the interface type (List, Set, Map), and choose the implementation for its performance and ordering behaviour. This page follows dev.java: The Collections Framework and the Java Tutorials Collections trail; each type links to its java.util Javadoc.

The Interface Hierarchy

Iterable<T> is the root: anything iterable works with the enhanced for loop. Collection<T> adds size, membership, and bulk operations, and splits into List (ordered, indexed, duplicates allowed), Set (no duplicates), and Queue / Deque (ends-oriented). Map<K, V> is not a Collection — it maps keys to values — but its keySet(), values(), and entrySet() views are. See the Collection Interfaces lesson.

import java.util.*;

// declare as the interface, assign a concrete implementation
List<String> names          = new ArrayList<>();
Set<Integer> ids            = new HashSet<>();
Map<String, Integer> scores = new HashMap<>();
Deque<String> stack         = new ArrayDeque<>();

names.add("Ada");
ids.add(42);
scores.put("Ada", 9);
stack.push("top");

// a method that accepts the interface works for every implementation
static long size(Collection<?> c) {
    return c.size();
}

long total = size(names) + size(ids) + size(scores.values());

Coding to the interface lets you swap ArrayList for LinkedList, or HashMap for TreeMap, without touching the callers.

Choosing an Implementation

import java.util.*;

// ArrayList: array-backed. Fast random access and iteration, cheap append. The default List.
List<Integer> list = new ArrayList<>();

// LinkedList: doubly-linked nodes. O(1) insert/remove once positioned, no cheap indexing.
// Worth using only as a Deque, rarely as a List.
Deque<Integer> nodes = new LinkedList<>();

// HashSet: unordered, near-O(1) membership. LinkedHashSet keeps insertion order.
// TreeSet: kept sorted (natural order or a Comparator), O(log n) operations.
Set<String> seen                = new HashSet<>();
Set<String> inInsertionOrder    = new LinkedHashSet<>();
NavigableSet<String> sortedSet  = new TreeSet<>();

// HashMap: unordered. LinkedHashMap: insertion (or access) order. TreeMap: keys sorted,
// with floorKey/ceilingKey/headMap/tailMap navigation.
Map<String, Integer> counts            = new HashMap<>();
NavigableMap<String, Integer> byKey    = new TreeMap<>();

// ArrayDeque: the modern stack and queue -- faster than the legacy Stack or LinkedList.
Deque<Integer> dq = new ArrayDeque<>();
dq.push(1);
int top = dq.pop();

// PriorityQueue: a binary heap; poll() returns the head per the ordering.
Queue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
pq.add(3); pq.add(1); pq.add(2);
int largest = pq.poll();   // 3

Approximate costs for the common operations (average case; HashMap/HashSet degrade to O(n) only under pathological hashing):

operation              ArrayList     LinkedList    HashMap/HashSet   TreeMap/TreeSet   ArrayDeque
random access get(i)    O(1)          O(n)          n/a               n/a               n/a
insert / remove at end  O(1) amort.   O(1)          n/a               n/a               O(1) amort.
insert / remove at head O(n)          O(1)          n/a               n/a               O(1) amort.
contains / get by key   O(n)          O(n)          O(1)              O(log n)          O(n)
iteration order         insertion     insertion     unspecified       sorted by key     head-to-tail

Default to ArrayList and HashMap. Choose a Linked* variant when you need predictable iteration order, a Tree* variant when you need sorting or range queries, and ArrayDeque for stack/queue work.

Iterating

Every Collection supplies an Iterator, which the enhanced for loop uses under the hood. See dev.java: Iterating over the Elements.

var list = new ArrayList<>(List.of("a", "b", "c", "d"));

// idiomatic read-only traversal
for (var s : list) {
    System.out.println(s);
}

// explicit Iterator when you must remove during traversal
for (var it = list.iterator(); it.hasNext(); ) {
    if (it.next().equals("b")) {
        it.remove();          // safe; list.remove(...) inside the loop is not
    }
}

// removeIf: the concise equivalent of the loop above
list.removeIf(s -> s.compareTo("c") >= 0);

// ListIterator: bidirectional, with set() and add()
for (var lit = list.listIterator(); lit.hasNext(); ) {
    lit.set(lit.next().toUpperCase());
}

Structurally modifying a collection during a for loop — through anything other than the loop’s own iterator — makes the iterator fail-fast: the next next() throws ConcurrentModificationException. It is a best-effort bug detector, not a concurrency guarantee.

for (String s : list) {
    if (s.isBlank()) {
        list.remove(s);       // throws ConcurrentModificationException on the next iteration
    }
}

Utilities and Immutable Factories

java.util.Collections holds static helpers; the List.of / Set.of / Map.of factories (Java 9) build compact, unmodifiable, null-hostile collections. See Implementations and dev.java: Creating Immutable Collections.

import java.util.*;

var nums = new ArrayList<>(List.of(3, 1, 2));
Collections.sort(nums);                               // in place -> [1, 2, 3]
Collections.sort(nums, Comparator.reverseOrder());    // -> [3, 2, 1]
int threes           = Collections.frequency(nums, 3);
List<String> nothing = Collections.emptyList();
List<Integer> view   = Collections.unmodifiableList(nums);   // live read-only view

// immutable factories: fixed size, reject null, throw on any mutator
List<String> days   = List.of("Mon", "Tue", "Wed");
Set<Integer> primes = Set.of(2, 3, 5, 7);
Map<String, Integer> ages = Map.of("Ada", 36, "Bo", 24);
Map<String, Integer> more = Map.ofEntries(
        Map.entry("Ada", 36),
        Map.entry("Bo", 24));

// unmodifiable snapshot detached from the source
List<String> snapshot = List.copyOf(days);

unmodifiableList wraps a collection that someone else can still change; List.copyOf copies the elements so the result is independent.

Sequenced Collections (Java 21)

SequencedCollection, SequencedSet, and SequencedMap give every collection with a defined encounter order the same first/last vocabulary and a reversed() view. See dev.java: Sequenced Collections.

import java.util.*;

SequencedCollection<String> sc = new ArrayList<>(List.of("a", "b", "c"));
sc.addFirst("start");                 // [start, a, b, c]
sc.addLast("end");                    // [start, a, b, c, end]
String head = sc.getFirst();          // "start"
String tail = sc.getLast();           // "end"
SequencedCollection<String> back = sc.reversed();   // reverse-ordered view

SequencedMap<String, Integer> sm = new LinkedHashMap<>();
sm.putFirst("a", 1);
sm.putLast("z", 26);
Map.Entry<String, Integer> first = sm.firstEntry();
SequencedMap<String, Integer> smReversed = sm.reversed();

List, Deque, LinkedHashSet, TreeSet, LinkedHashMap, and TreeMap all implement the sequenced interfaces. reversed() returns a view — writes through it are reflected in the backing collection.

The equals / hashCode Contract

Hash-based collections locate an element by its hashCode(), then confirm the match with equals(Object). Override both together, from the same fields, or lookups fail silently. The full contract is on Inheritance and Polymorphism.

import java.util.*;

// a record derives a correct equals/hashCode/toString from its components
record Point(int x, int y) { }

Set<Point> points = new HashSet<>();
points.add(new Point(1, 2));
boolean here = points.contains(new Point(1, 2));   // true -- value equality

// TreeSet/TreeMap order by a Comparator or Comparable, not by equals
NavigableSet<Point> byX = new TreeSet<>(
        Comparator.comparingInt(Point::x).thenComparingInt(Point::y));
byX.add(new Point(3, 0));
byX.add(new Point(1, 9));
Point smallest = byX.first();                       // Point[x=1, y=9]

An object whose equals/hashCode fields mutate while it sits in a hash collection becomes unreachable — keep keys and set elements immutable. Building multi-key orderings with Comparator factories (comparing, thenComparing, reversed) is covered on Interfaces.

The Hierarchy at a Glance

The diagram shows Iterable at the root of Collection, the List / Set / Queue / Deque branches with their sorted sub-interfaces, and Map drawn separately because it does not extend Collection:

Collections framework interfaces: Iterable to Collection to List, Set to SortedSet to NavigableSet, and Queue to Deque, with common classes ArrayList, LinkedList, HashSet, LinkedHashSet, TreeSet, PriorityQueue and ArrayDeque hung under each interface; Map to SortedMap to NavigableMap drawn separately with HashMap, LinkedHashMap and TreeMap

See Also

  • Streams and Collectors — processing the contents of a collection with a lazy pipeline instead of an explicit loop.

  • Generics — the type parameters (List<E>, Map<K, V>, bounded wildcards) that every collection interface is built on.

  • Interfaces — Comparable vs. Comparator and the factory methods used to sort TreeSet, TreeMap, and PriorityQueue.

  • Inheritance and Polymorphism — the full equals/hashCode contract that hash-based collections depend on.