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

1. Short Answer

Java's Collection Framework organises its interfaces into three main groups:

• List — ordered, index-based, allows duplicates. Primary implementation: ArrayList.
• Set — unordered (or sorted with TreeSet), no duplicates. Primary implementation: HashSet.
• Map — key-value pairs, keys are unique, values can repeat. Primary implementation: HashMap. (Map does not extend Collection.)

2. Detailed Explanation

2.1 List Interface

The java.util.List interface extends Collection and represents an ordered sequence of elements. Key characteristics:

• Elements maintain their insertion order.
• Duplicate values are permitted — the same object can appear multiple times.
• Elements are accessible by zero-based integer index via get(int index).
• Allows null values (multiple nulls in ArrayList).

Main implementations:

• ArrayList — backed by a dynamic array; O(1) random access, O(n) insert/delete in the middle.
• LinkedList — doubly-linked list; O(1) insert/delete at ends, O(n) random access.
• Vector — legacy, synchronized version of ArrayList.
• CopyOnWriteArrayList — thread-safe variant for concurrent reads.

2.2 Set Interface

The java.util.Set interface extends Collection and models a mathematical set — a group with no duplicate members. Key characteristics:

• No duplicate elements; add() returns false if the element already exists.
• Uniqueness is determined by hashCode() and equals().
• Most implementations (HashSet) do not guarantee insertion order.
• At most one null is allowed (in HashSet).

Main implementations:

• HashSet — hash table; O(1) average add/contains/remove.
• LinkedHashSet — HashSet + doubly-linked list; maintains insertion order.
• TreeSet — Red-Black tree; O(log n) operations; elements sorted naturally or by Comparator.
• EnumSet — ultra-fast bit-vector implementation for enum types.

2.3 Map Interface

The java.util.Map interface is not a subtype of Collection. It maps unique keys to values. Key characteristics:

• Keys must be unique; duplicate keys overwrite the existing value.
• Values can be duplicated.
• Provides three views: keySet(), values(), entrySet().
• One null key allowed in HashMap; TreeMap does not allow null keys.

Main implementations:

• HashMap — hash table; O(1) average get/put.
• LinkedHashMap — HashMap + linked list; maintains insertion order.
• TreeMap — Red-Black tree; O(log n); keys in sorted order.
• Hashtable — legacy, synchronized; does not allow null keys/values.
• ConcurrentHashMap — thread-safe, high-concurrency HashMap.

3. Code Example

import java.util.*;

public class CollectionDemo {
    public static void main(String[] args) {

        // ---- LIST ----
        List<String> list = new ArrayList<>();
        list.add("Apple");
        list.add("Banana");
        list.add("Apple");   // duplicate allowed
        list.add(null);      // null allowed
        System.out.println("List: " + list);
        // Output: [Apple, Banana, Apple, null]
        System.out.println("Element at index 1: " + list.get(1)); // Banana

        // ---- SET ----
        Set<String> set = new HashSet<>();
        set.add("Apple");
        set.add("Banana");
        boolean added = set.add("Apple"); // returns false — duplicate ignored
        System.out.println("Set: " + set);          // [Banana, Apple] (order not guaranteed)
        System.out.println("Apple added again? " + added); // false

        // LinkedHashSet preserves insertion order
        Set<String> linked = new LinkedHashSet<>(list);
        System.out.println("LinkedHashSet: " + linked); // [Apple, Banana, null]

        // TreeSet sorts elements
        Set<String> sorted = new TreeSet<>(Arrays.asList("Cherry", "Apple", "Banana"));
        System.out.println("TreeSet: " + sorted); // [Apple, Banana, Cherry]

        // ---- MAP ----
        Map<String, Integer> map = new HashMap<>();
        map.put("Alice", 90);
        map.put("Bob",   85);
        map.put("Alice", 95);  // overwrites previous value for key "Alice"
        System.out.println("Map: " + map);                  // {Alice=95, Bob=85}
        System.out.println("Alice's score: " + map.get("Alice")); // 95

        // Iterating a Map
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }

        // Map.getOrDefault — safe retrieval
        int score = map.getOrDefault("Charlie", 0);
        System.out.println("Charlie's score: " + score); // 0
    }
}

4. Time Complexity Comparison

Hash-based structures have O(n) worst-case complexity if many keys collide, but this is extremely rare with a good hashCode() implementation.

5. When to Use Each

5.1 Use List When

• You need to preserve the order elements were inserted.
• Duplicate values are expected or required (e.g., shopping cart items).
• You need index-based access (get(2)).
• You are building a stack, queue, or ordered sequence.

5.2 Use Set When

• You need to enforce uniqueness (e.g., unique usernames, visited URLs).
• You need fast membership testing (contains()).
• You need mathematical set operations (union, intersection) — use retainAll(), addAll().
• Order does not matter (or use TreeSet / LinkedHashSet when it does).

5.3 Use Map When

• You need to associate a value with a unique key (dictionary, cache).
• You need fast key-based lookup without scanning all elements.
• Examples: word frequency count, student grades by name, config settings.
• Use TreeMap when you need the keys in sorted order.

6. Interview Context

This question tests whether a candidate understands the Java Collections hierarchy and can choose the right data structure for a problem. Interviewers often follow up with:

• "If I need to count word frequencies in a document, which would you use?" → HashMap<String, Integer>
• "How do you remove duplicates from a List?" → Convert to HashSet (loses order) or LinkedHashSet (preserves order).
• "Can a Map have duplicate values?" → Yes, only keys must be unique.
• "What happens if you add a duplicate to a HashSet?" → add() returns false, set is unchanged.
• "Why does Map not extend Collection?" → Because Map models key-value associations, not a sequence of individual elements. The interface contract is fundamentally different.

7. Common Pitfalls

7.1 Mutating Keys in a HashMap

If a key object's hashCode() changes after it is inserted, the entry becomes unreachable.

// BAD: using a mutable list as a Map key
List<String> key = new ArrayList<>(Arrays.asList("a", "b"));
Map<List<String>, Integer> map = new HashMap<>();
map.put(key, 1);
key.add("c");  // hashCode of key changed!
System.out.println(map.get(key)); // null — entry lost!

// GOOD: use immutable keys (String, Integer, record, etc.)
Map<String, Integer> safe = new HashMap<>();
safe.put("ab", 1);

7.2 Forgetting to Override equals/hashCode

Custom objects used in a HashSet or as HashMap keys must override both hashCode() and equals(). Without this, two logically equal objects are treated as different.

class Point {
    int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Point)) return false;
        Point p = (Point) o;
        return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

Set<Point> points = new HashSet<>();
points.add(new Point(1, 2));
System.out.println(points.contains(new Point(1, 2))); // true (with overrides)

7.3 ConcurrentModificationException

Modifying a collection while iterating it with a for-each loop throws ConcurrentModificationException. Use Iterator.remove() or collect elements to remove separately.

List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));

// BAD
// for (String s : list) { if (s.equals("b")) list.remove(s); } // throws CME

// GOOD
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("b")) it.remove(); // safe
}
System.out.println(list); // [a, c]

8. Conclusion

List, Set, and Map serve distinct purposes in Java's Collections Framework:

• List — ordered sequences with duplicates; use ArrayList for most cases.
• Set — unique elements; use HashSet for speed, LinkedHashSet for order, TreeSet for sorting.
• Map — key-to-value associations; use HashMap for speed, TreeMap for sorted keys, LinkedHashMap for insertion-order iteration.

Choosing the right interface up front leads to cleaner code and better performance. In interviews, demonstrate understanding by tying your choice to concrete requirements, not just naming the class.