List, Set, and Map

List, Set, and Map

Almost every program keeps groups of things: orders, user IDs, settings, counts. Java's Collections Framework gives you three core kinds of container, and choosing between them is one of the most frequent decisions in everyday code:

• A List is an ordered sequence that allows duplicates, and you access elements by position. "The items in this cart, in the order added."
• A Set holds unique elements, so adding a duplicate does nothing. "The tags on this post."
• A Map associates keys with values, with unique keys. "Each user ID's profile." (Map isn't technically a Collection, but it's part of the same framework.)

Always declare variables by the interface (List, Set, Map) and choose the implementation (ArrayList, HashSet, HashMap, …) only where the object is created. Code that uses the collection then doesn't depend on the implementation.

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

List

List<String> steps = new ArrayList<>();
steps.add("build");
steps.add("test");
steps.add("build");               // duplicates allowed
steps.get(1);                      // "test" — access by index
steps.set(0, "compile");          // replace by index
steps.remove("build");            // removes the FIRST matching element
steps.indexOf("test");            // position, or -1

Default to ArrayList. In practice it beats LinkedList even in most situations textbooks suggest otherwise, because of CPU caching. For a queue or deque, use ArrayDeque, not LinkedList.

Gotcha, remove(int) vs remove(Object): on a List<Integer>, list.remove(1) removes the element at index 1, not the value 1. Use list.remove(Integer.valueOf(1)) for the value.

Set

Set<String> seen = new HashSet<>();
seen.add("a");                    // true
seen.add("a");                    // false — already present, set unchanged
seen.contains("a");               // fast membership test

The classic use is removing duplicates (new LinkedHashSet<>(list) keeps the first occurrence of each, in order) and fast "have I seen this?" checks. list.contains is O(n), while set.contains is O(1). Switching a hot membership check from a list to a set is one of the easiest big performance wins.

Map

Map<String, Integer> wordCount = new HashMap<>();
wordCount.put("java", 1);
wordCount.get("java");                          // 1
wordCount.get("python");                        // null — absent key
wordCount.getOrDefault("python", 0);            // 0
wordCount.merge("java", 1, Integer::sum);       // increment-or-insert in one call → 2
wordCount.computeIfAbsent("spring", k -> 0);    // insert a default only if absent
wordCount.containsKey("java");                  // true

for (Map.Entry<String, Integer> e : wordCount.entrySet()) {   // iterate keys and values together
    System.out.println(e.getKey() + " = " + e.getValue());
}

The merge, computeIfAbsent and getOrDefault methods (Java 8+) replace the error-prone "get, check for null, then put" dance. How HashMap works internally (buckets, hashing, resizing, tree bins) is covered in HashMap Deep Dive.

Choosing quickly

Keys and elements must behave

HashSet and HashMap find elements using hashCode() and equals(). TreeSet and TreeMap use compareTo() or the supplied comparator. So:

• Classes used as keys or set elements must implement equals and hashCode consistently (see equals() and hashCode()). Records do this automatically.
• Don't mutate an object while it's inside a hash-based collection in a way that changes its hash. It becomes unfindable ("lost"), even though it's still there.
• A TreeSet treats elements that compare as equal (compareTo = 0) as duplicates, even if equals says they differ. Comparators must be consistent with the intended notion of equality.

Immutable collections and views

List<String> fixed = List.of("a", "b");          // Java 9+: immutable, rejects nulls
Map<String, Integer> m = Map.of("x", 1, "y", 2);
List<String> copy = List.copyOf(mutableList);     // immutable snapshot
List<String> view = Collections.unmodifiableList(mutableList);   // read-only VIEW: changes to the original show through

List.of and friends throw UnsupportedOperationException on modification and NullPointerException on null elements. Know this before passing them to code that expects to add to the list. Arrays.asList(array) is a fixed-size view backed by the array: you can set elements, but not add or remove.

Modifying while iterating

for (String s : list) if (s.isBlank()) list.remove(s);    // ❌ ConcurrentModificationException

list.removeIf(String::isBlank);                           // ✅ Java 8+
Iterator<String> it = list.iterator();                    // ✅ classic way
while (it.hasNext()) if (it.next().isBlank()) it.remove();

Collections detect structural changes made outside the iterator and fail fast, rather than silently skipping elements.

Follow-up questions this topic invites — and their answers

Q: ArrayList vs LinkedList: when would you choose LinkedList? A: Rarely. It helps only when you frequently insert or remove in the middle through an iterator you already hold, or need a deque and can't use ArrayDeque. ArrayList wins on indexed access, iteration speed and memory, and ArrayDeque is the better queue or stack.

Q: How does a HashSet guarantee uniqueness? A: It's backed by a HashMap whose keys are the elements. Adding computes hashCode() to find a bucket, then uses equals() to check for an equal element already there. If one exists, nothing is added.

Q: HashMap vs TreeMap vs LinkedHashMap? A: HashMap gives average O(1) operations with no ordering guarantee. LinkedHashMap gives the same speed plus insertion-order (or access-order) iteration. TreeMap gives O(log n) operations, keeps keys sorted, and supports navigation such as floor, ceiling and sub-maps.

Q: Why does List.of(...).add(x) throw? A: List.of returns an immutable list. Use new ArrayList<>(List.of(...)) when you need a mutable list initialized with values.

Q: What happens if you change a field used in hashCode() after adding the object to a HashSet? A: The object stays in the bucket for its old hash. Lookups compute the new hash, look in a different bucket, and don't find it, so contains returns false, and remove fails. It's effectively leaked in the set. Use immutable keys.