Collections Framework in Java

The Java Collections Framework provides ready-made data structures for groups of objects. Every collection implements a core interface — List, Set, Queue or Map — so you can swap one implementation for another by changing a single new expression. Examples are single files run with the JDK 21 source launcher (java File.java).

Collection
├── List   — ordered, duplicates allowed   (ArrayList, LinkedList)
├── Set    — no duplicates                 (HashSet, LinkedHashSet, TreeSet)
└── Queue  — processing order              (ArrayDeque, PriorityQueue)

Map        — unique keys → values          (HashMap, LinkedHashMap, TreeMap)

ArrayList

ArrayList is a resizable array: the default choice for an ordered list.

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

public class Lists {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Alice", "Bob", "Charlie"));
        names.add(1, "Dave");                 // insert, shifting the rest right
        System.out.println(names + " size=" + names.size());
        System.out.println("index of Bob: " + names.indexOf("Bob"));

        names.set(0, "Alicia");
        names.remove("Dave");                 // by value
        names.remove(0);                      // by index
        System.out.println(names);

        names.sort(null);                     // natural order
        System.out.println(names);
    }
}

$ java Lists.java
[Alice, Dave, Bob, Charlie] size=4
index of Bob: 2
[Bob, Charlie]
[Bob, Charlie]

remove is overloaded: remove("Dave") removes by value, remove(0) by index. With a List<Integer> that difference bites — the next example shows it.

Two classic List traps

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

public class ListTraps {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(List.of(10, 20, 30));
        nums.remove(1);                       // index 1, not the value 1
        System.out.println(nums);
        nums.remove(Integer.valueOf(10));     // the value 10
        System.out.println(nums);

        List<String> fixed = List.of("a", "b");
        fixed.add("c");
    }
}

$ java ListTraps.java
[10, 30]
[30]
Exception in thread "main" java.lang.UnsupportedOperationException
	at java.base/java.util.ImmutableCollections.uoe(ImmutableCollections.java:142)
	at java.base/java.util.ImmutableCollections$AbstractImmutableCollection.add(ImmutableCollections.java:147)
	at ListTraps.main(ListTraps.java:13)

remove(1) with an int picks remove(int index); pass an Integer to remove by value. List.of returns an immutable list, so add throws — that is why the earlier example wrapped it in new ArrayList<>(...).

Sets: HashSet, LinkedHashSet, TreeSet

All three reject duplicates. They differ only in iteration order.

import java.util.*;

public class Sets {
    public static void main(String[] args) {
        List<String> input = List.of("pear", "apple", "fig", "apple", "banana");
        Set<String> hash   = new HashSet<>(input);
        Set<String> linked = new LinkedHashSet<>(input);
        Set<String> tree   = new TreeSet<>(input);
        System.out.println("HashSet:       " + hash);
        System.out.println("LinkedHashSet: " + linked);
        System.out.println("TreeSet:       " + tree);
        System.out.println("add apple again? " + hash.add("apple"));
    }
}

$ java Sets.java
HashSet:       [banana, apple, pear, fig]
LinkedHashSet: [pear, apple, fig, banana]
TreeSet:       [apple, banana, fig, pear]
add apple again? false

HashSet’s order comes from hash codes — don’t rely on it. LinkedHashSet keeps insertion order, TreeSet sorted order. add returns false when the element was already present, which is a cheap way to detect duplicates.

Set operations and TreeSet range queries

import java.util.*;

public class SetOps {
    public static void main(String[] args) {
        Set<Integer> a = new TreeSet<>(Set.of(1, 2, 3, 4));
        Set<Integer> b = new TreeSet<>(Set.of(3, 4, 5, 6));

        Set<Integer> union = new TreeSet<>(a);        union.addAll(b);
        Set<Integer> inter = new TreeSet<>(a);        inter.retainAll(b);
        Set<Integer> diff  = new TreeSet<>(a);        diff.removeAll(b);
        System.out.println(union + " " + inter + " " + diff);

        TreeSet<Integer> t = new TreeSet<>(Set.of(5, 2, 8, 1, 9, 3));
        System.out.println("floor(4)=" + t.floor(4) + " ceiling(4)=" + t.ceiling(4));
        System.out.println("headSet(5)=" + t.headSet(5) + " tailSet(5)=" + t.tailSet(5));
    }
}

$ java SetOps.java
[1, 2, 3, 4, 5, 6] [3, 4] [1, 2]
floor(4)=3 ceiling(4)=5
headSet(5)=[1, 2, 3] tailSet(5)=[5, 8, 9]

addAll, retainAll and removeAll change the set they are called on, which is why each operation starts from a copy of a. headSet excludes its bound and tailSet includes it.

HashMap

import java.util.*;

public class Maps {
    public static void main(String[] args) {
        Map<String, Integer> scores = new HashMap<>();
        scores.put("Alice", 95);
        scores.put("Bob", 87);
        Integer old = scores.put("Alice", 98);
        System.out.println("replaced " + old + " -> " + scores.get("Alice"));
        System.out.println("Dave: " + scores.get("Dave") + " / " + scores.getOrDefault("Dave", 0));

        scores.merge("Alice", 5, Integer::sum);
        scores.computeIfAbsent("Eve", k -> 100);
        scores.computeIfPresent("Eve", (k, v) -> v + 10);

        for (Map.Entry<String, Integer> e : new TreeMap<>(scores).entrySet()) {
            System.out.println(e.getKey() + " = " + e.getValue());
        }
    }
}

$ java Maps.java
replaced 95 -> 98
Dave: null / 0
Alice = 103
Bob = 87
Eve = 110

put returns the previous value, and get on a missing key returns null — getOrDefault avoids that. merge adds 5 to the existing 98. Copying into a TreeMap before printing gives a stable, sorted order.

Counting and grouping with merge and computeIfAbsent

These two methods replace the “check, then put” pattern.

import java.util.*;

public class WordStats {
    public static void main(String[] args) {
        String[] words = "the cat and the hat and the bat".split(" ");
        Map<String, Integer> counts = new TreeMap<>();
        Map<Integer, List<String>> byLength = new TreeMap<>();
        for (String w : words) {
            counts.merge(w, 1, Integer::sum);
            byLength.computeIfAbsent(w.length(), k -> new ArrayList<>()).add(w);
        }
        System.out.println(counts);
        System.out.println(byLength);
    }
}

$ java WordStats.java
{and=2, bat=1, cat=1, hat=1, the=3}
{3=[the, cat, and, the, hat, and, the, bat]}

merge(w, 1, Integer::sum) stores 1 for a new word and adds 1 to an existing count. computeIfAbsent creates the list the first time a length appears and returns it either way — every word here has three letters, so they all land in one list.

TreeMap and LinkedHashMap

import java.util.*;

public class OrderedMaps {
    public static void main(String[] args) {
        Map<String, Integer> tree = new TreeMap<>();
        Map<String, Integer> linked = new LinkedHashMap<>();
        for (String k : List.of("Charlie", "Alice", "Bob")) {
            tree.put(k, k.length());
            linked.put(k, k.length());
        }
        System.out.println(tree);
        System.out.println(linked);
        TreeMap<String, Integer> t = (TreeMap<String, Integer>) tree;
        System.out.println(t.firstKey() + " " + t.headMap("C"));
    }
}

$ java OrderedMaps.java
{Alice=5, Bob=3, Charlie=7}
{Charlie=7, Alice=5, Bob=3}
Alice {Alice=5, Bob=3}

TreeMap sorts by key; LinkedHashMap remembers insertion order. headMap("C") returns the keys strictly less than "C".

ArrayDeque as a queue and a stack

ArrayDeque is the default for both FIFO queues and LIFO stacks (prefer it over the legacy Stack class).

import java.util.ArrayDeque;
import java.util.Deque;

public class Deques {
    public static void main(String[] args) {
        Deque<String> queue = new ArrayDeque<>();
        queue.offer("first"); queue.offer("second"); queue.offer("third");
        System.out.println("peek " + queue.peek() + ", poll " + queue.poll() + ", left " + queue);

        Deque<String> stack = new ArrayDeque<>();
        stack.push("bottom"); stack.push("middle"); stack.push("top");
        System.out.println("pop " + stack.pop() + ", left " + stack);

        System.out.println("poll on empty: " + new ArrayDeque<String>().poll());
        new ArrayDeque<String>().remove();
    }
}

$ java Deques.java
peek first, poll first, left [second, third]
pop top, left [middle, bottom]
poll on empty: null
Exception in thread "main" java.util.NoSuchElementException
	at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:361)
	at java.base/java.util.ArrayDeque.remove(ArrayDeque.java:522)
	at Deques.main(Deques.java:15)

offer/poll work at opposite ends (FIFO); push/pop both work at the head (LIFO). Each operation comes in two flavours: poll returns null on an empty deque, remove throws.

PriorityQueue

A PriorityQueue always hands back the smallest element (a min-heap), or the “best” one according to a Comparator.

import java.util.*;

public class Priorities {
    public static void main(String[] args) {
        PriorityQueue<Integer> min = new PriorityQueue<>(List.of(5, 1, 3, 2));
        System.out.println("toString: " + min);
        StringBuilder sb = new StringBuilder();
        while (!min.isEmpty()) sb.append(min.poll()).append(' ');
        System.out.println("polled:   " + sb);

        PriorityQueue<String> byLength = new PriorityQueue<>(Comparator.comparingInt(String::length).reversed());
        byLength.addAll(List.of("fig", "banana", "kiwi"));
        System.out.println("longest first: " + byLength.poll());
    }
}

$ java Priorities.java
toString: [1, 2, 3, 5]
polled:   1 2 3 5
longest first: banana

Only poll() order is guaranteed. toString shows the internal heap array, which merely happened to look sorted here; with other input it will not be.

Choosing a collection

Project: library checkout

A Map finds books by ISBN, a Set records which are out, and a Map of Deques holds each book’s waitlist.

import java.util.*;

public class Library {
    private final Map<String, String> catalog = new HashMap<>();
    private final Set<String> checkedOut = new HashSet<>();
    private final Map<String, Deque<String>> waitlists = new HashMap<>();

    void checkout(String isbn, String patron) {
        if (checkedOut.add(isbn)) {
            System.out.println(patron + " checked out " + catalog.get(isbn));
        } else {
            waitlists.computeIfAbsent(isbn, k -> new ArrayDeque<>()).offer(patron);
            System.out.println(patron + " waits for " + catalog.get(isbn));
        }
    }

    void giveBack(String isbn) {
        checkedOut.remove(isbn);
        String next = waitlists.getOrDefault(isbn, new ArrayDeque<>()).poll();
        if (next != null) checkout(isbn, next);
        else System.out.println(catalog.get(isbn) + " back on the shelf");
    }

    public static void main(String[] args) {
        Library lib = new Library();
        lib.catalog.put("978-1", "Effective Java");
        lib.checkout("978-1", "Alice");
        lib.checkout("978-1", "Bob");
        lib.giveBack("978-1");
        lib.giveBack("978-1");
    }
}

$ java Library.java
Alice checked out Effective Java
Bob waits for Effective Java
Bob checked out Effective Java
Effective Java back on the shelf

checkedOut.add(isbn) both tests and marks in one call, because Set.add returns false for an element already present. The waitlist is a Deque used as a FIFO queue, so patrons are served in the order they asked.

Practice

1. Count how many times each character appears in "mississippi" and print the counts in alphabetical order.

import java.util.Map;
import java.util.TreeMap;

public class CharCount {
    public static void main(String[] args) {
        Map<Character, Integer> counts = new TreeMap<>();
        for (char c : "mississippi".toCharArray()) counts.merge(c, 1, Integer::sum);
        System.out.println(counts);
    }
}

$ java CharCount.java
{i=4, m=1, p=2, s=4}

2. Remove duplicates from [3, 1, 3, 2, 1] while keeping the first-seen order.

import java.util.*;

public class Dedupe {
    public static void main(String[] args) {
        List<Integer> input = List.of(3, 1, 3, 2, 1);
        List<Integer> unique = new ArrayList<>(new LinkedHashSet<>(input));
        System.out.println(unique);
    }
}

$ java Dedupe.java
[3, 1, 2]

3. Use a stack to check whether the brackets in "{[()]}" and "{[(])}" are balanced.

import java.util.ArrayDeque;
import java.util.Deque;

public class Brackets {
    public static void main(String[] args) {
        for (String s : new String[] {"{[()]}", "{[(])}"}) System.out.println(s + " " + balanced(s));
    }

    static boolean balanced(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if ("([{".indexOf(c) >= 0) stack.push(c);
            else {
                if (stack.isEmpty()) return false;
                char open = stack.pop();
                if ("([{".indexOf(open) != ")]}".indexOf(c)) return false;
            }
        }
        return stack.isEmpty();
    }
}

$ java Brackets.java
{[()]} true
{[(])} false

4. Given tasks with priorities ("deploy", 2), ("fix bug", 1), ("write docs", 3), process them lowest number first with a PriorityQueue of records.

import java.util.Comparator;
import java.util.PriorityQueue;

public class Tasks {
    record Task(String name, int priority) {}

    public static void main(String[] args) {
        PriorityQueue<Task> pq = new PriorityQueue<>(Comparator.comparingInt(Task::priority));
        pq.add(new Task("deploy", 2));
        pq.add(new Task("fix bug", 1));
        pq.add(new Task("write docs", 3));
        while (!pq.isEmpty()) System.out.println(pq.poll());
    }
}

$ java Tasks.java
Task[name=fix bug, priority=1]
Task[name=deploy, priority=2]
Task[name=write docs, priority=3]