Lesson 6 of 12 · 9 min · Collections, streams and generics
List, Set and Map: choosing the right collection
What you will learn
- The three main collection types:
List,SetandMap - The standard implementations and when to choose each
- Time cost (Big-O) of the common operations
- Immutable collections with
List.of,Set.ofandMap.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), butget(i)is O(n) and it uses more memory. It is rarely better thanArrayListin practice; for a queue,ArrayDequeis 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.
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
ArrayListinstead ofList. - Using
LinkedListbecause "insertion is faster" without measuring. - Modifying a collection while iterating over it.
- Using a
List.containscheck in a big loop (O(n) each time); use aSet. - Relying on
HashMapiteration order. - Using mutable objects as keys or set members.
- Forgetting that
Arrays.asListandList.ofare fixed-size or immutable.
Try it yourself
- Count the frequency of each word in a sentence with a
HashMapandmerge, then print it sorted by key using aTreeMap. - Remove duplicates from a list while keeping the order.
- Use
removeIfto delete all blank strings from a list. - Compare the time of
List.containsandSet.containsfor 100,000 items. - Build an
EnumMapcounting orders by an enumStatus.
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
Listis ordered with duplicates,Setis unique,Mapis 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.ofandMap.offor immutable data,mergeandcomputeIfAbsentfor maps,removeIffor safe removal. - Pick by the operation you do most; use sets for membership tests.
Going deeper
- dev.java: The Collections Framework: the official guide.
- The Java Tutorials: Collections: interfaces and implementations.
- Collections Framework overview: the reference description and algorithm costs.
- Map interface API: all methods.
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.