Java Collections Framework: List, Set, Map

The Collections Framework is one of Java’s strongest selling points: a small set of interfaces, many implementations, and consistent semantics. The catch is choosing the right implementation. The default in most code should be ArrayList, HashSet, and HashMap, but the moment you need ordering, sorting, or thread safety, the rest of the family earns its keep.

The hierarchy at a glance

Top level interfaces:

• Collection is the root of single-value containers.
• List is an ordered collection with indexed access.
• Set is a collection with no duplicates.
• Queue and Deque are for FIFO and double ended access.
• Map is not a Collection; it stores key value pairs.

List

ArrayList is the default. It is backed by an array, gives O(1) random access, and O(1) amortized append at the end.

import java.util.*;

List<String> langs = new ArrayList<>();
langs.add("Java");
langs.add("Kotlin");
langs.add(0, "Scala");      // insert at index, O(n)
String first = langs.get(0); // O(1)

LinkedList is rarely the right answer. It uses more memory per element and loses cache locality. The one case it shines is when you frequently add to and remove from both ends, but ArrayDeque is usually faster for that too.

Deque<String> queue = new ArrayDeque<>();
queue.addLast("a");
queue.addFirst("z");
String head = queue.pollFirst();

Use ArrayDeque whenever you would have reached for Stack or LinkedList. Stack is legacy and synchronized; do not use it for new code.

Set

HashSet gives O(1) average add, remove, and contains. Order is not guaranteed.

Set<String> seen = new HashSet<>();
seen.add("a");
seen.add("a");           // no-op
System.out.println(seen.contains("a"));  // true

LinkedHashSet preserves insertion order with a tiny overhead. Use it when you want set semantics and predictable iteration.

TreeSet keeps elements sorted, either by natural order or a Comparator. Operations are O(log n).

TreeSet<Integer> sorted = new TreeSet<>();
sorted.addAll(List.of(3, 1, 4, 1, 5));
System.out.println(sorted);            // [1, 3, 4, 5]
System.out.println(sorted.first());    // 1
System.out.println(sorted.higher(3));  // 4

For HashSet and HashMap to work, your element keys must implement equals and hashCode consistently. Records do this for free.

Map

HashMap is the default for key value lookup.

Map<String, Integer> counts = new HashMap<>();
counts.put("apple", 1);
counts.put("apple", counts.getOrDefault("apple", 0) + 1);

Better: use merge or compute.

counts.merge("apple", 1, Integer::sum);

LinkedHashMap preserves insertion order (or access order, useful for LRU caches).

Map<String, String> lru = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> e) {
        return size() > 100;
    }
};

TreeMap keeps keys sorted and offers range queries via headMap, tailMap, and subMap.

ConcurrentHashMap is the thread safe map you actually want. Hashtable is legacy.

Iteration

Three common forms:

for (String s : list) {
    System.out.println(s);
}

list.forEach(System.out::println);

for (var entry : map.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

If you modify a collection while iterating it, most implementations throw ConcurrentModificationException. The fix is to use the iterator’s own remove method or collect changes and apply them after.

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().isEmpty()) {
        it.remove();   // safe
    }
}

Even cleaner with removeIf:

list.removeIf(String::isEmpty);

Immutable collections

Since Java 9, factory methods return small immutable collections:

List<String> tags = List.of("java", "jvm", "tutorial");
Set<Integer> primes = Set.of(2, 3, 5, 7);
Map<String, Integer> ages = Map.of("Ada", 36, "Linus", 55);

They are compact, thread safe by construction, and throw UnsupportedOperationException on any modification. Use them anywhere you would have written a defensive copy.

To take a snapshot of a mutable collection, use copyOf:

List<String> snapshot = List.copyOf(mutableList);

Sorting

Collections.sort(list) uses natural ordering. For custom orders, pass a Comparator.

List<String> names = new ArrayList<>(List.of("Charlie", "Alice", "Bob"));
names.sort(Comparator.naturalOrder());
names.sort(Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));

For records, you can chain comparators on accessors:

record User(String name, int age) {}
users.sort(Comparator.comparingInt(User::age).reversed());

Choosing quickly

A cheat sheet for the everyday case:

• Need a sequence with random access? ArrayList.
• Need a queue or stack? ArrayDeque.
• Need uniqueness? HashSet. Need ordered? TreeSet. Need insertion order? LinkedHashSet.
• Need key value? HashMap. Sorted keys? TreeMap. LRU or insertion order? LinkedHashMap. Concurrent? ConcurrentHashMap.

Boxing pitfall

Collections store references, so primitives are boxed: List<Integer> holds Integer objects, not int. For performance critical code over millions of primitives, drop down to plain arrays or use a library like Eclipse Collections.

Wrap up

Pick the implementation that matches your access pattern, prefer immutable collections at API boundaries, and never modify a collection while iterating it. Next, learn how to write functions over these containers in Java Generics and Streams and Lambdas.