What questions do you ask yourself to decide between a List, a Set, and a Map for a given task?
answer
- List = order + duplicates + index
- Set = uniqueness, membership question
- Map = key → value lookup
- Interface = meaning, class = cost
- Order is a separate axis (Linked/Tree)
basics
~20 sUse a List when you need ordered items and duplicates are fine. Use a Set when you need unique items only. Use a Map when you look things up by a key. Pick based on whether you have keys, need uniqueness, or care about order.
solid answer
~40 sStart from the access pattern. If you store a sequence and access by position or just iterate, and duplicates are allowed, use a List (ArrayList by default). If you only need membership/uniqueness and don't care about order, use a Set (HashSet). If you associate values with lookup keys, use a Map (HashMap). The three answer different questions: List = 'what is at index i / what's the order?', Set = 'have I seen x?', Map = 'what value goes with key k?'. After choosing the interface, pick the implementation by ordering needs (insertion order, sorted), null tolerance, and concurrency. The interface is the contract; the class is the cost profile.
code
java · 12 lines// Same data, three questions:
List<String> lines = new ArrayList<>(); // ordered, duplicates OK
Set<String> distinctWords = new HashSet<>(); // uniqueness / membership
Map<String, Integer> counts = new HashMap<>(); // key -> value lookup
for (String line : lines) {
for (String w : line.split("\\s+")) {
distinctWords.add(w); // dedupe
counts.merge(w, 1, Integer::sum); // count by key
}
}
// Anti-pattern: lines.contains(w) is O(n); distinctWords.contains(w) is O(1)go deeper
Knows the three families by example and can map a plain-English requirement (unique tags, key lookup, ordered list) to List/Set/Map.
Articulates the access-pattern checklist, knows Map is not a Collection, and avoids O(n) List.contains for membership.
Separates the interface (meaning) from the implementation (cost), explains how uniqueness relies on equals/hashCode or comparison, and chooses order via the implementation axis.
Frames collection choice as part of API and data-model design — exposes the right interface type in signatures, considers immutability/concurrency, and reasons about cost profiles at scale.
## The three core abstractions The Java Collections Framework gives you a set of interfaces (contracts describing *what* a collection does) and classes (implementations describing *how*, with specific speed and memory costs). The first decision is always which **interface** family fits, because that captures the meaning of your data. - A **List** is an *ordered sequence* that **allows duplicates** and gives **positional access** (you can ask for the element at index `i`). Examples: a to-do list, lines of a file, a shopping cart. Implementations: `ArrayList`, `LinkedList`. - A **Set** is a collection of **unique** elements — adding the same element twice has no effect. It answers the membership question *'is x in here?'* fast. It does **not** give positional access. Examples: the set of user IDs that have voted, distinct tags. Implementations: `HashSet`, `LinkedHashSet`, `TreeSet`. - A **Map** is **not** a `Collection`; it stores **key → value** associations where keys are unique. It answers *'what value is stored under key k?'*. Examples: word → count, userId → user object. Implementations: `HashMap`, `LinkedHashMap`, `TreeMap`. ## The decision checklist Ask, in order: 1. **Do I look things up by a key (an identifier separate from the value)?** → **Map**. (word counts, caches, indexes) 2. **Do I need elements to be unique, and I don't look them up by a separate key?** → **Set**. (deduplication, membership tests) 3. **Otherwise** (a plain ordered bag of items, duplicates fine, possibly accessed by position) → **List**. ## Why uniqueness matters `Set` enforces uniqueness via `equals()`/`hashCode()` (for hash-based sets) or `compareTo()`/a `Comparator` (for sorted sets). If your elements are custom objects, you *must* implement `equals`/`hashCode` correctly or the Set won't dedupe as you expect. A List never calls those for storage — it just appends. ## Order is a separate axis Whether you need order is independent of List/Set/Map. A List is inherently ordered. For Set/Map, you choose the *implementation* to get order: hash variant (no order guarantee), `LinkedHash*` (insertion order), `Tree*` (sorted order). So the interface answers 'do I need keys / uniqueness?', and the class answers 'do I need order, and what cost can I pay?' ## A worked example Counting word frequencies: you look up by the word (the key) and store a count (the value) → **Map** (`HashMap<String,Integer>`). Listing the file's lines in order → **List** (`ArrayList<String>`). Collecting the distinct words seen → **Set** (`HashSet<String>`). The same raw data drives three different structures depending on the question you're asking. Getting this first cut right (interface family by meaning) is more important than micro-optimizing the implementation — a wrong family makes the code awkward and often slow (e.g. using `list.contains()` for membership is O(n) when a Set is O(1)).
- Is Map a subtype of Collection?No. Map is a separate top-level interface. Collection (List, Set, Queue) holds single elements; Map holds key→value entries. You can view a Map's keys (keySet()), values (values()), or entries (entrySet()) as collections, but Map itself does not extend Collection.
- When would you use a List even though elements are unique?When order/position matters more than the uniqueness guarantee, or duplicates are merely currently absent but allowed in principle, and you don't need fast membership tests. If you frequently call contains(), switch to a Set.
A List is a numbered line of people at a bus stop (order matters, twins allowed). A Set is a guest list checked at the door (each name once, no seat numbers). A Map is a coat-check: you hand over a ticket (key) and get back your coat (value).
saying these in an interview costs you the question
- Saying Map extends Collection — it does not.
- Using List.contains() for membership checks (O(n)) when a Set would be O(1).
- Thinking a Set is automatically sorted — only TreeSet is; HashSet has no order.
- Putting custom objects in a HashSet without overriding equals/hashCode and expecting deduplication.