Lesson 6 of 12 · 9 min · Collections, streams and generics

List, Set and Map: choosing the right collection

Covers: Java 25 LTS (also valid on 21). Updated 13 Nov 2026. Part of the Java Full Stack Developer roadmap.

What you will learn

  • The three main collection types: List, Set and Map
  • The standard implementations and when to choose each
  • Time cost (Big-O) of the common operations
  • Immutable collections with List.of, Set.of and Map.of
  • Iterating safely and avoiding ConcurrentModificationException

In simple words

A collection is a container that holds many objects. A List is a numbered line of items where order matters and repeats are fine, like a to-do list. A Set is a bag with no repeats, like a list of unique email addresses. A Map is a dictionary: you look something up by a key and get its value, like a phone book. Choosing the right container makes code shorter and faster.

Words to know

  • Collection: an object that groups other objects.
  • Key and value: in a map, the item you search by and the item you get back.
  • Big-O: a way of describing how the time of an operation grows with the number of items.
  • Iterator: an object that walks through a collection one item at a time.

The framework at a glance

Iterable
  └── Collection
        ├── List   (ordered, allows duplicates)
        ├── Set    (no duplicates)
        └── Queue / Deque

Map  (key to value; not a Collection)

Always declare variables with the interface type and create the implementation on the right:

List<String> names = new ArrayList<>();
Set<String> cities = new HashSet<>();
Map<String, Integer> stock = new HashMap<>();

This lets you swap the implementation later without changing the rest of the code.

List

An ordered sequence with positions (index from 0).

List<String> skills = new ArrayList<>();
skills.add("sql");
skills.add("java");
skills.add(0, "python");            // insert at the start
skills.get(1);                       // "sql"
skills.remove("java");               // remove by value
skills.contains("sql");              // true
skills.size();                       // 2
  • ArrayList: backed by an array. get(i) is O(1), adding at the end is amortised O(1), inserting or removing in the middle is O(n). The default choice.
  • LinkedList: a doubly linked list. Adding or removing at the ends is O(1), but get(i) is O(n) and it uses more memory. It is rarely better than ArrayList in practice; for a queue, ArrayDeque is usually faster.
  • List.of(...) creates a fixed, immutable list.

Since Java 21, lists (and other ordered collections) have getFirst(), getLast(), addFirst, removeLast and reversed() through the SequencedCollection interface.

Set

A collection with no duplicates. It uses equals and hashCode (or comparison) to decide whether two items are the same.

Set<String> tags = new HashSet<>();
tags.add("sql");
tags.add("sql");                    // ignored: already present
System.out.println(tags.size());    // 1
Implementation Order add, contains, remove Use when
HashSet none guaranteed O(1) average you only need uniqueness and fast lookup
LinkedHashSet insertion order O(1) average you need uniqueness and predictable order
TreeSet sorted (natural or Comparator) O(log n) you need sorted order, ranges, first(), ceiling()

Common uses: remove duplicates from a list (new LinkedHashSet<>(list) keeps the order), membership tests (allowed.contains(user)), and set maths (retainAll for intersection, addAll for union, removeAll for difference).

Map

A map stores key-value pairs with unique keys.

Map<String, Integer> stock = new HashMap<>();
stock.put("pen", 100);
stock.put("book", 40);
stock.get("pen");                         // 100
stock.get("bag");                         // null: key not present
stock.getOrDefault("bag", 0);             // 0
stock.containsKey("book");                // true
stock.remove("book");
stock.put("pen", 90);                     // replaces the value for an existing key

Handy modern methods:

stock.putIfAbsent("bag", 5);
stock.merge("pen", 10, Integer::sum);                   // add 10 to pen, or set it to 10 if absent
stock.computeIfAbsent("cap", k -> 0);                   // create a value when missing
stock.forEach((item, qty) -> System.out.println(item + " = " + qty));

A classic counting pattern:

Map<String, Integer> counts = new HashMap<>();
for (String word : words) {
    counts.merge(word, 1, Integer::sum);
}
Implementation Order get, put Notes
HashMap none guaranteed O(1) average the default; allows one null key
LinkedHashMap insertion (or access) order O(1) can implement an LRU cache
TreeMap sorted by key O(log n) firstKey(), headMap(), range queries
ConcurrentHashMap none O(1) safe for many threads; no null keys or values
EnumMap enum order O(1) very compact when keys are an enum

Iterate over a map with entrySet():

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

keySet() and values() give views. The next lesson explains how HashMap works inside.

Immutable collections

List<String> days = List.of("Mon", "Tue");
Set<Integer> primes = Set.of(2, 3, 5);
Map<String, Integer> codes = Map.of("IN", 91, "US", 1);
List<String> copy = List.copyOf(otherList);

Calling add throws UnsupportedOperationException; they also reject null elements. Use them for constants and for returning data you do not want changed. Collections.unmodifiableList(list) is only a view: it changes if the original list changes.

Iterating and removing safely

Removing from a list inside a for-each loop throws ConcurrentModificationException:

for (String s : names) {
    if (s.isEmpty()) names.remove(s);        // throws
}

Use removeIf, an explicit Iterator, or build a new collection:

names.removeIf(String::isEmpty);

Choosing a collection

Need Use
ordered items, access by position ArrayList
no duplicates, fastest lookup HashSet
no duplicates, keep insertion order LinkedHashSet
sorted unique items TreeSet
look up a value by a key HashMap
key lookup in sorted order TreeMap
a queue or a stack ArrayDeque
shared by many threads ConcurrentHashMap, CopyOnWriteArrayList

Common mistakes

  • Declaring variables as ArrayList instead of List.
  • Using LinkedList because "insertion is faster" without measuring.
  • Modifying a collection while iterating over it.
  • Using a List.contains check in a big loop (O(n) each time); use a Set.
  • Relying on HashMap iteration order.
  • Using mutable objects as keys or set members.
  • Forgetting that Arrays.asList and List.of are fixed-size or immutable.

Try it yourself

  1. Count the frequency of each word in a sentence with a HashMap and merge, then print it sorted by key using a TreeMap.
  2. Remove duplicates from a list while keeping the order.
  3. Use removeIf to delete all blank strings from a list.
  4. Compare the time of List.contains and Set.contains for 100,000 items.
  5. Build an EnumMap counting orders by an enum Status.

Check yourself

What is the difference between a List and a Set?

A list keeps insertion order, allows duplicates and has positions; a set contains unique elements, and its order depends on the implementation.

When would you choose TreeMap over HashMap?

When you need keys in sorted order or range queries; HashMap is faster for plain lookups.

Why does removing elements in a for-each loop fail?

The collection detects that it was modified during iteration and throws ConcurrentModificationException; use removeIf or an iterator instead.

What does Map.merge(key, 1, Integer::sum) do?

It puts 1 if the key is absent, otherwise adds 1 to the existing value, a compact way to count.

Interview questions

ArrayList versus LinkedList: which do you use and why?

Almost always ArrayList: constant-time index access, compact memory and cache-friendly. LinkedList only helps for frequent add or remove at both ends with an iterator, and even then ArrayDeque is usually better.

What is the difference between HashMap, LinkedHashMap and TreeMap?

HashMap has no guaranteed order and O(1) lookup; LinkedHashMap keeps insertion (or access) order; TreeMap keeps keys sorted with O(log n) operations.

How do you make a collection thread-safe?

Use concurrent collections such as ConcurrentHashMap or CopyOnWriteArrayList, or wrap with Collections.synchronizedList; better still, share immutable data.

Summary

  • List is ordered with duplicates, Set is unique, Map is key to value; program to the interface.
  • Defaults: ArrayList, HashSet, HashMap; use the Linked and Tree variants for order or sorting.
  • Use List.of, Set.of and Map.of for immutable data, merge and computeIfAbsent for maps, removeIf for safe removal.
  • Pick by the operation you do most; use sets for membership tests.

Going deeper

See how much of this you can explain

A free mock interview asks you new questions on Core Java: OOP, collections and exceptions for Java Full Stack Developer and scores every answer, with what to fix.