Java List vs Set vs Map

Three interfaces cover almost every collection decision in Java. List when order and position matter, Set when uniqueness matters, Map when lookup by a meaningful key matters. Getting this choice wrong produces correctness bugs, O(n) operations where O(1) is possible, or duplicate data appearing where it should not. The decision is architectural — it shapes how you model your data, not just which class name you type.

The Three Core Collection Interfaces

List, Set, and Map are the three fundamental contracts in the Java Collections Framework. Every concrete collection class you use — ArrayList, HashSet, HashMap, TreeMap — implements one of these.

java.util.Collection<E>               ← root of element-holding collections
    ├── java.util.List<E>             ← ordered, indexed, duplicates allowed
    │       ├── ArrayList             ← resizable array
    │       ├── LinkedList            ← doubly-linked nodes
    │       └── CopyOnWriteArrayList  ← thread-safe snapshot
    │
    └── java.util.Set<E>              ← unique elements, no duplicates
            ├── HashSet               ← O(1), no order
            ├── LinkedHashSet         ← O(1), insertion order
            └── TreeSet               ← O(log n), sorted order

java.util.Map<K, V>                   ← key-value pairs (NOT a Collection)
    ├── HashMap                       ← O(1), no order
    ├── LinkedHashMap                 ← O(1), insertion order
    ├── TreeMap                       ← O(log n), sorted by key
    └── ConcurrentHashMap             ← thread-safe, bucket-level locking

Basic Overview — The Three Contracts at a Glance

LIST                         SET                          MAP
---------------------------  ---------------------------  ---------------------------
Stores: elements             Stores: elements             Stores: key-value pairs
Order: YES — insertion order  Order: depends on impl       Order: depends on impl
Duplicates: ALLOWED           Duplicates: REJECTED         Keys: UNIQUE, values: any
Index access: YES (get(i))    Index access: NO             Key access: YES (get(key))
Null: allowed                 Null: 1 null (HashSet)       Null key: 1 (HashMap)
Primary use: ordered sequence Primary use: unique lookup   Primary use: key→value lookup
Core question:                Core question:               Core question:
  "What is at position i?"      "Have I seen this before?"   "What is the value for key X?"

SIZE: 3 elements             SIZE: 3 unique elements      SIZE: 3 key-value pairs
list = ["A","B","A"]         set  = {"A", "B"}            map  = {A→1, B→2, C→3}
list.size() = 3              set.size() = 2               map.size() = 3
list.get(1) = "B"            set.contains("A") = true     map.get("A") = 1
list.get(2) = "A"            (second "A" was rejected)    (each key maps to one value)

What Is List?

List<E> is an ordered, indexed sequence that allows duplicate elements. "Ordered" means elements stay in the position they were placed — iterating a List always produces elements in the same sequence. "Indexed" means you can retrieve any element directly by its zero-based position with get(int index). "Allows duplicates" means the same object can appear multiple times at different positions.

LIST CONTRACT:
  - Maintains insertion order
  - Elements accessible by index: get(0), get(1), ..., get(n-1)
  - Duplicates: allowed — "Java" can appear at index 0 AND index 5
  - Null: allowed
  - Interface methods beyond Collection: get(i), set(i,e), add(i,e), remove(i),
    indexOf(e), lastIndexOf(e), subList(from, to), listIterator()

COMMON IMPLEMENTATIONS:
  ArrayList   — O(1) get, O(n) add/remove at middle, cache-friendly
  LinkedList  — O(1) head/tail, O(n) get by index, implements Deque too
  Vector      — legacy, synchronised; use CopyOnWriteArrayList instead

What Is Set?

Set<E> enforces one rule above all: no duplicate elements. Adding an element that is already present returns false and leaves the set unchanged. The definition of "same element" is determined by equals() and hashCode() — any class used as a Set element must implement both correctly.

SET CONTRACT:
  - No duplicate elements — add() returns false for duplicates
  - No index access — cannot call get(i)
  - No guaranteed ordering (for HashSet), insertion order (LinkedHashSet),
    or sorted order (TreeSet)
  - Null: HashSet allows one null; TreeSet throws NPE on null
  - Interface methods: add(e), remove(e), contains(e), size(), iterator()

COMMON IMPLEMENTATIONS:
  HashSet       — O(1) add/remove/contains average, no order
  LinkedHashSet — O(1) operations, preserves insertion order
  TreeSet       — O(log n) operations, sorted ascending order,
                  adds: first(), last(), floor(), ceiling(), headSet(), tailSet()

What Is Map?

Map<K, V> stores key-value pairs where each key is unique. It is NOT a subtype of Collection — it has its own root interface. Maps answer the question "given this key, what is the value?" in O(1) average (HashMap) or O(log n) worst-case (TreeMap). Every HashMap.containsKey() is O(1); every ArrayList.contains() is O(n). That difference is why switching from a list-of-pairs to a Map is one of the most impactful performance improvements in production Java code.

MAP CONTRACT:
  - Unique keys — each key maps to at most one value
  - Values: not constrained, duplicates allowed, null allowed
  - Null keys: HashMap allows one; TreeMap/Hashtable do not
  - Not a Collection — no add(), no iterator() directly on map
  - Access via views: keySet(), values(), entrySet()
  - Interface methods: put(k,v), get(k), remove(k), containsKey(k),
    containsValue(v), putIfAbsent(k,v), computeIfAbsent(k,fn), merge(k,v,fn)

COMMON IMPLEMENTATIONS:
  HashMap       — O(1) average all key operations, no order
  LinkedHashMap — O(1) operations, insertion order preserved
  TreeMap       — O(log n) operations, sorted by key,
                  adds: firstKey(), lastKey(), floorKey(), ceilingKey(), subMap()
  ConcurrentHashMap — thread-safe, bucket-level locking, atomic compound ops

When to Use List, Set, or Map

This is the decision tree that every Java developer runs through when adding a new collection field.

START: What problem does this collection solve?

  → Need to remember position or order, and duplicates are natural?
      Use LIST
      Examples:
        — Shopping cart items (same product can appear multiple times)
        — Ordered search results (rank 1, rank 2, ...)
        — A message history (same message can repeat)
        — Steps in a pipeline (ordered execution)

  → Need to track whether something has been seen, with no duplicates?
      Use SET
      Examples:
        — Visited URLs in a web crawler
        — Unique tags on a blog post
        — Processed order IDs to prevent double-processing
        — Active user IDs in an online game

  → Need to look up a value by a meaningful key?
      Use MAP
      Examples:
        — User ID → UserProfile (user session cache)
        — Product SKU → Stock count (inventory)
        — Word → Count (word frequency)
        — City → Population (analytics lookup)
        — Request path → Handler (routing table)

  → None of the above fit cleanly?
      Combined structures are common:
        — Map<String, List<String>>  : tags grouped by category
        — Map<String, Set<String>>   : unique permissions per role
        — Set<Map.Entry<K,V>>        : same as Map.entrySet()
        — List<Map<String, Object>>  : rows in a query result

Core Differences — Head-to-Head Comparison

Core Operations with Examples

List — Ordered Access and Duplicate Handling

Output:
=== List — ordered, duplicates allowed ===
History  : [laptop, laptop stand, laptop, laptop bag, laptop cooling pad]
Size     : 5

get(0)   : laptop
get(2)   : laptop
indexOf(laptop)     : 0
lastIndexOf(laptop) : 2

Execution order: [VALIDATE_INPUT, AUTHENTICATE, AUTHORISE, PROCESS, RESPOND]
Step 3 is: AUTHORISE

Set — Uniqueness and Membership Testing

Output:
=== Set — deduplication ===
Raw tags    : [java, spring, java, hibernate, spring, kafka]
Unique tags : [java, spring, hibernate, kafka]
Size        : 4

=== Set — O(1) membership test ===
Already processed ORD-002? true
Already processed ORD-099? false

=== Set operations — skill matching ===
Matched  : [Spring, Java]
Missing  : [Kubernetes, Redis]

Map — Key-Based Lookup

Output:
=== Map — word frequency ===
  java         3
  spring       2
  hashmap      1
  hibernate    1

=== Map — O(1) role lookup ===
priya@example.com has role: ADMIN
unknown@x.com has role: GUEST

=== Map<String, List> — city zones ===
  Bengaluru: [Koramangala, Whitefield, Indiranagar]
  Mumbai: [Andheri, Bandra, Powai]

Real-World Example — Flipkart Product Search Pipeline

A product search at Flipkart demonstrates all three interfaces working together. A List holds the ordered search result set (ranking matters). A Set tracks which product IDs have already been seen to prevent duplicates in merged results from multiple sources. A Map holds the full product details so each result can be enriched without repeated database lookups.

Output:
======================================================================
  SEARCH RESULTS for: "laptop"  (5 results)
======================================================================
  1. [P003] HP Pavilion 15            Rs. 44999.00  4.4★  (Laptops)
  2. [P001] Lenovo ThinkPad E14      Rs. 52999.00  4.3★  (Laptops)
  3. [P004] Asus VivoBook 15         Rs. 41999.00  4.2★  (Laptops)
  4. [P002] Dell Inspiron 15         Rs. 48500.00  4.1★  (Laptops)
  5. [P005] Acer Aspire 5            Rs. 37999.00  3.9★  (Laptops)
======================================================================

Data structures used in this pipeline:
  Map<String, Product>        → product catalogue (O(1) enrichment)
  Set<String> (LinkedHashSet) → deduplication across result sources
  List<Product> (ArrayList)   → ordered results by rank

Performance Considerations

The O(n) contains trap: list.contains(element) scans every element linearly. For a list of 100,000 items, this is 100,000 comparisons per call. set.contains(element) or map.containsKey(key) is one or two comparisons per call. A very common production performance improvement is identifying a repeated list.contains() pattern and replacing the List with a Set or Map.

Best Practices

Start with the interface, not the implementation. Declare List<String> results = new ArrayList<>(), not ArrayList<String> results = new ArrayList<>(). This makes it trivial to swap implementations — ArrayList to LinkedList, HashSet to LinkedHashSet for ordered output — without changing any other code.

Choose Set over List for any "have I seen this?" pattern. If the code repeatedly checks list.contains(item) before deciding whether to add, that is O(n) per check — and the real intent is uniqueness, not order. A Set handles both deduplication and O(1) membership testing in one structure.

Use Map over parallel lists. Two lists maintained in lockstep — List<String> keys and List<Value> values where keys.get(i) corresponds to values.get(i) — are almost always a design smell. A Map<String, Value> is cleaner, faster on lookup, and impossible to corrupt by inserting in the wrong list.

Use Map<K, List<V>> for grouping. computeIfAbsent(key, k -> new ArrayList<>()).add(value) is the standard pattern for building a grouped index: category to product list, user to order list, date to event list. The inner List preserves insertion order within each group; the outer Map gives O(1) group lookup.

Common Mistakes

Mistake 1 — Using List.contains() in a Loop When Set Is Needed

Mistake 2 — Using a List of Pairs When Map Is the Correct Model

Mistake 3 — Using Set When Order Must Be Preserved

Mistake 4 — Using Map When the Value IS the Key (Should Be a Set)

Interview Questions

Q1. What is the difference between List, Set, and Map in Java?

List is an ordered, indexed sequence that allows duplicates — get(index) retrieves any element in O(1) (ArrayList). Set stores unique elements — no duplicates — with O(1) membership testing (HashSet); contains() on a Set is O(1) versus O(n) on a List. Map stores key-value pairs where keys are unique — get(key) retrieves any value in O(1) average (HashMap). The choice depends on the question your data needs to answer: "what is at position i?" → List; "have I seen this element?" → Set; "what is the value for this key?" → Map.

Q2. When should you use a Set instead of a List in Java?

Use a Set instead of a List when uniqueness is required and positional access by index is not needed. The critical performance signal: if the code calls list.contains(element) before adding (checking for duplicates), it is O(n) per check and O(n²) total. A Set handles uniqueness automatically — set.add(element) returns false for duplicates in O(1). Additional cases: membership testing (set.contains() is O(1) vs list.contains() O(n)), set algebra operations (union via addAll(), intersection via retainAll(), difference via removeAll()), and deduplication pipelines where first-occurrence order matters (use LinkedHashSet).

Q3. What is the difference between HashMap and HashSet internally?

HashSet is literally a thin wrapper around HashMap. When you call set.add(element), it internally calls map.put(element, PRESENT) where PRESENT is a shared static dummy Object. set.contains(element) calls map.containsKey(element). The entire HashSet implementation delegates to HashMap — same hash table, same bucket structure, same treeification at 8 entries. This is why both have the same O(1) average complexity and why both require equals() and hashCode() to be correctly implemented on elements/keys.

Q4. Can a Map be iterated like a List or Set?

Map does not implement Iterable directly. To iterate, use one of three views: map.keySet() returns a Set<K> of all keys; map.values() returns a Collection<V> of all values; map.entrySet() returns a Set<Map.Entry<K,V>> of all key-value pairs. entrySet() is the most efficient for accessing both key and value — it avoids the second hash lookup that keySet() + map.get(key) would require. map.forEach((k, v) -> ...) is the cleanest Java 8+ iteration pattern.

Q5. How do you choose between LinkedHashSet and TreeSet?

Both maintain order alongside uniqueness, but of different kinds. LinkedHashSet preserves insertion order — elements iterate in the order add() was first called, O(1) operations. TreeSet maintains sorted natural order (or Comparator order) — elements always iterate alphabetically or numerically, O(log n) operations. Use LinkedHashSet when "first seen" order or display consistency matters. Use TreeSet when sorted order is required, or when range operations (headSet(), tailSet(), floor(), ceiling()) are needed.

Q6. What is Map.Entry and when do you use it?

Map.Entry<K, V> is the interface representing a single key-value pair inside a Map. It is obtained by iterating map.entrySet(). entry.getKey() and entry.getValue() give both the key and value in one step — no second hash lookup. The entry.setValue(newValue) method updates the value in place within the live map. Map.Entry is also useful for sorting: Map.Entry.comparingByValue() gives a Comparator that sorts entries by value, enabling patterns like "top 5 words by frequency" via stream().sorted(Map.Entry.comparingByValue().reversed()).limit(5).

FAQs

What is the simplest rule for choosing between List, Set, and Map?

Three questions: Does order or position matter? → List. Does the data need to be unique? → Set. Does each item have a key you will look up by? → Map. Most data models fall cleanly into one of these. When multiple requirements exist — unique AND ordered, or key-lookup AND grouped — combine them: LinkedHashSet for unique+ordered, Map<K, List<V>> for grouped key-lookup.

Is Map a subtype of Collection in Java?

No. Map<K, V> is a completely separate hierarchy from Collection<E>. Collection contains elements. Map contains key-value pairs — a fundamentally different abstraction. You cannot pass a Map where a Collection is expected. The three views map.keySet(), map.values(), and map.entrySet() return Collection or Set objects that bridge between the two hierarchies.

Can a List contain duplicate elements?

Yes. List explicitly allows duplicate elements at any position. list.add("A"); list.add("A"); results in a list of size 2 with "A" at both index 0 and index 1. This contrasts with Set, which silently rejects the second add("A") and remains size 1. If you want a sequence that rejects duplicates, use LinkedHashSet (preserves order) or TreeSet (sorts).

What happens when you add a duplicate to a Set?

set.add(element) returns false and the Set is unchanged — no exception is thrown. The element is considered a duplicate when equals() returns true for an existing element. For TreeSet, the comparison uses compareTo() or the supplied Comparator instead. The set size does not increase and the existing element is not replaced.

What is the difference between Map.put() return value and Set.add() return value?

Set.add(element) returns boolean — true if the element was new, false if it was a duplicate. Map.put(key, value) returns V — the previous value associated with the key, or null if the key was absent. Both return values are meaningful and often underused. if (set.add(item)) is cleaner than if (!set.contains(item)) { set.add(item); }. String old = map.put(key, newValue) gives you the previous value for logging or undo without a separate get() call.

How do you convert a List to a Set and back?

Set<E> set = new HashSet<>(list) deduplicates in O(n) — no order preservation. Set<E> ordered = new LinkedHashSet<>(list) deduplicates while preserving first-occurrence order. List<E> back = new ArrayList<>(set) converts back to a List. The idiomatic one-liner for deduplication with order: new ArrayList<>(new LinkedHashSet<>(list)).

Summary

List, Set, and Map answer three distinct questions about data. List asks "what is at position i?" — ordered, indexed, duplicates allowed, ArrayList for most cases. Set asks "have I seen this before?" — unique elements, O(1) membership, HashSet for speed, LinkedHashSet for order, TreeSet for sorted access. Map asks "what is the value for key X?" — key-value pairs, O(1) lookup, HashMap for most cases, LinkedHashMap for insertion-order iteration, TreeMap for sorted keys.

The most impactful collection choice in production code is usually switching list.contains() inside a loop to a Set — that single change turns O(n²) into O(n). The second most common is replacing parallel lists with a Map. Get the choice right at design time and the implementation details follow naturally.

For interviews: know the exact API difference between each interface (get(index) on List, contains(element) on Set, get(key) on Map), explain that HashSet is backed by HashMap, describe when LinkedHashSet vs TreeSet is appropriate, and be ready to explain the grouping pattern Map<K, List<V>>. These questions distinguish developers who understand data structure design from those who simply know syntax.

What to Read Next