Collections Framework

The Java Collections Framework (JCF) is a unified architecture that provides ready-made, high-performance data structures — lists, sets, maps, queues, and more — along with the algorithms that operate on them. Instead of reinventing the wheel every time you need to store or process a group of objects, you pick the right collection for the job and get production-quality behaviour for free.

Note: The Collections Framework lives in the java.util package. Most classes and interfaces you’ll use are right there — no extra dependency needed.

Why Collections?

Before the Collections Framework (introduced in Java 1.2), Java developers had to use plain arrays or the outdated Vector/Hashtable classes. Arrays are fixed-size and lack built-in search or sort helpers. The JCF solved both problems and added a consistent API across every data structure.

Key benefits at a glance:

Without JCF	With JCF
Fixed-size arrays	Dynamically sized structures
Manual resize/copy code	Handled automatically
No shared contract	Unified interfaces (List, Set, Map, …)
Ad-hoc algorithms	Built-in sort, search, shuffle via Collections
Thread safety — your problem	Concurrent variants provided

The Big Picture: Core Interfaces

The framework is built around a small set of interfaces. Understanding the hierarchy is the key to choosing the right type.

Iterable
  └── Collection
        ├── List        (ordered, allows duplicates)
        ├── Set         (no duplicates)
        │     └── SortedSet → NavigableSet
        └── Queue       (FIFO / priority ordering)
              └── Deque (double-ended queue / stack)

Map                     (key-value pairs, separate hierarchy)
  └── SortedMap → NavigableMap

• List — You care about order and position. Duplicates are fine.
• Set — You care only about membership. No duplicates allowed.
• Queue / Deque — You process elements in a specific order (FIFO, LIFO, priority).
• Map — You look things up by a unique key.

A Quick Taste

Here is a short example that touches several core types so you can see how consistent the API feels:

import java.util.*;

public class CollectionsOverview {
    public static void main(String[] args) {
        // List — ordered, indexed, duplicates allowed
        List<String> languages = new ArrayList<>();
        languages.add("Java");
        languages.add("Python");
        languages.add("Java"); // duplicate is fine
        System.out.println("List: " + languages);

        // Set — no duplicates
        Set<String> unique = new HashSet<>(languages);
        System.out.println("Set: " + unique);

        // Map — key → value
        Map<String, Integer> scores = new HashMap<>();
        scores.put("Alice", 95);
        scores.put("Bob", 87);
        System.out.println("Map: " + scores);

        // Queue — FIFO
        Queue<String> queue = new LinkedList<>();
        queue.offer("first");
        queue.offer("second");
        System.out.println("Poll: " + queue.poll());
    }
}

Output:

List: [Java, Python, Java]
Set: [Java, Python]
Map: {Alice=95, Bob=87}
Poll: first

Choosing the Right Collection

This decision table covers the most common choices:

Need	Best Choice
Fast random access by index	ArrayList
Frequent insert/delete in the middle	LinkedList
Fast membership test, no order needed	HashSet
Membership test + insertion order	LinkedHashSet
Sorted unique elements	TreeSet
Key→value lookup, no order	HashMap
Key→value + insertion order	LinkedHashMap
Key→value + sorted keys	TreeMap
FIFO queue	ArrayDeque
Priority-based processing	PriorityQueue
Thread-safe list	CopyOnWriteArrayList
Thread-safe map	ConcurrentHashMap

Tip: When you only know you need a List, declare the variable as List<String> (the interface), not ArrayList<String>. This makes it trivial to swap the implementation later without touching calling code.

Generics and Type Safety

All modern collection classes are generic. You parameterise them with a type in angle brackets (<>), and the compiler enforces that you only put the right type of objects in:

List<Integer> numbers = new ArrayList<>();
numbers.add(42);
numbers.add(7);
// numbers.add("hello"); // compile error — caught at compile time, not runtime
int sum = numbers.get(0) + numbers.get(1);
System.out.println(sum); // 49

Without generics (pre-Java 5), everything was stored as Object and you had to cast — a common source of ClassCastException at runtime. See Generics for the full story.

Iterating Over Collections

Every Collection implements Iterable, so you can use the for-each loop directly:

List<String> cities = List.of("London", "Tokyo", "Nairobi");
for (String city : cities) {
    System.out.println(city);
}

For more control — like removing elements while iterating — use an explicit Iterator:

List<Integer> nums = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
Iterator<Integer> it = nums.iterator();
while (it.hasNext()) {
    if (it.next() % 2 == 0) {
        it.remove(); // safe removal during iteration
    }
}
System.out.println(nums); // [1, 3, 5]

Warning: Never modify a collection directly (e.g. list.remove(...)) while iterating over it with a for-each loop — you’ll get a ConcurrentModificationException. Use Iterator.remove() or a removeIf() call instead.

Under the Hood

Fail-Fast Iterators

Most JDK collections maintain an internal modCount counter that increments on every structural change (add, remove, clear). When an iterator is created, it snapshots this value. On each next() call, it compares the current modCount against its snapshot — if they differ, it throws ConcurrentModificationException immediately. This “fail-fast” design surfaces bugs early rather than silently returning garbage data.

Memory Layout

• ArrayList and ArrayDeque back their elements in a contiguous Object[]. This gives CPU-cache-friendly access — iterating is very fast because adjacent elements sit in adjacent memory locations.
• LinkedList, HashMap, TreeMap use heap-allocated node objects with pointer fields, which means more memory overhead and less cache locality.
• HashMap stores entries in an array of buckets. Since Java 8, each bucket can hold a red-black tree (instead of a plain linked list) once it reaches 8 entries, keeping worst-case lookup at O(log n) rather than O(n).

Performance Complexity (Common Operations)

Operation	ArrayList	LinkedList	HashSet/HashMap	TreeSet/TreeMap
get(index)	O(1)	O(n)	—	—
add (end)	O(1) amortised	O(1)	O(1) avg	O(log n)
add (middle)	O(n)	O(1)*	—	—
contains	O(n)	O(n)	O(1) avg	O(log n)
remove	O(n)	O(1)*	O(1) avg	O(log n)

* After you already hold the node reference; finding the node is O(n).

Unmodifiable and Immutable Views

Java 9+ factory methods (List.of(...), Set.of(...), Map.of(...)) return truly immutable collections — attempting to call add or put throws UnsupportedOperationException. They are also more memory-efficient than wrapping with Collections.unmodifiableList(...) because the JDK uses compact internal representations.

List<String> immutable = List.of("a", "b", "c");
// immutable.add("d"); // throws UnsupportedOperationException

In This Section

• Collection Interface — The root interface shared by List, Set, and Queue; learn the core contract every collection must honour.
• List Interface — Ordered, index-based sequences that allow duplicate elements; the most-used collection type in everyday Java.
• ArrayList — The go-to resizable array implementation of List with O(1) random access and amortised O(1) appends.
• LinkedList — A doubly-linked list that also implements Deque; ideal when you need frequent insertions or removals at both ends.
• ArrayList vs LinkedList — A head-to-head comparison of time complexity, memory, and practical use cases to help you pick the right one.
• Vector — The legacy thread-safe list from Java 1.0; understand when (rarely) it’s still appropriate.
• ArrayList vs Vector — Why ArrayList replaced Vector for almost all use cases, and when the old class still appears in codebases.
• Stack — LIFO stack built on Vector; learn its API and why ArrayDeque is usually preferred in modern code.
• Set Interface — A collection that guarantees no duplicate elements; the contract shared by HashSet, LinkedHashSet, and TreeSet.
• HashSet — The fastest general-purpose Set backed by a HashMap; O(1) average add/contains/remove.
• LinkedHashSet — A HashSet that remembers insertion order, giving you uniqueness without losing sequence.
• TreeSet — A sorted Set backed by a red-black tree; elements are always in natural or comparator order.
• Queue & PriorityQueue — FIFO queues and heap-backed priority queues for task scheduling and ordered processing.
• Deque & ArrayDeque — A double-ended queue that outperforms both Stack and LinkedList for stack/queue workloads.
• Map Interface — The contract for key-value stores; understand the methods every Map must provide.
• HashMap — The workhorse key-value store with O(1) average lookup; learn its bucket, load-factor, and resize mechanics.
• Working of HashMap (Internals) — A deep dive into hashing, bucket arrays, linked-list-to-tree treeification, and Java 8 improvements.
• LinkedHashMap — A HashMap that preserves insertion (or access) order; great for LRU caches.
• TreeMap — A sorted Map backed by a red-black tree; supports range queries like subMap, headMap, and tailMap.
• Hashtable — The original synchronised map from Java 1.0; understand its limitations and why HashMap or ConcurrentHashMap is preferred.
• HashMap vs Hashtable — Synchronisation, null handling, and performance differences explained side-by-side.
• Iterator — The standard cursor for traversing any collection safely, including safe removal during iteration.
• Comparable — How to give your objects a natural ordering by implementing compareTo.
• Comparator — How to define external, reusable ordering strategies, especially useful with Java 8 lambda syntax.
• Comparable vs Comparator — When to bake ordering into the class vs. when to supply it from the outside.
• Collections Utility Class — The static helper methods sort, shuffle, reverse, binarySearch, frequency, and more.
• Sorting Collections — How to sort Lists with natural order, Comparators, and the Stream API.
• Properties Class — A specialised Map for string key-value pairs, commonly used for configuration files.
• EnumSet & EnumMap — Ultra-efficient set and map implementations purpose-built for enum constants.
• Concurrent Collections — Thread-safe structures like ConcurrentHashMap, CopyOnWriteArrayList, and blocking queues for multi-threaded code.

Related Topics

• Generics — Collections are generic; understanding type parameters makes the whole framework click.
• Iterators — Learn the cursor that powers every for-each loop under the hood.
• Stream API — Process collections with filter, map, and reduce using a functional pipeline.
• Sorting Collections — Practical patterns for sorting Lists and Maps in modern Java.
• Concurrent Collections — The thread-safe variants you need when multiple threads share data.
• Arrays Utility Class — The java.util.Arrays counterpart for fixed-size array operations.