Java collections: choosing List, Set and Map in practice

Java collections: choosing List, Set and Map in practice

We've all shipped code that worked but felt sluggish, only to discover we picked the wrong collection type for the job. The standard library gives us powerful tools—List, Set, Map and their implementations—but choosing the right one isn't always obvious. This article walks through real decisions we make in production: when to reach for ArrayList over LinkedList, why immutable factories matter, and how size hints can prevent hidden performance cliffs.

Quick guide: choose by access pattern

Collection choice comes down to your access pattern. Before reaching for code, ask yourself: how do I need to use this data?

Let's ground this in a real scenario. Suppose we're building a user activity dashboard for a ride-hailing service. We fetch user IDs, need to check if we've seen them before, and later display them in order. Here's what picking the right collection looks like:

// Wrong: LinkedList for checking seen users
LinkedList<String> seenUserIds = new LinkedList<>();
if (seenUserIds.contains(userId)) { // O(n)—slow for 100k users
    // ...
}

// Right: HashSet for membership tests
Set<String> seenUserIds = new HashSet<>();
if (seenUserIds.contains(userId)) { // O(1)—fast
    // ...
}
seenUserIds.add(userId);

// Later, display in insertion order
LinkedHashSet<String> userOrder = new LinkedHashSet<>(seenUserIds);
// or collect them into a sorted list
List<String> sortedIds = seenUserIds.stream()
    .sorted()
    .toList();

Notice we didn't use LinkedList. That's not accidental—we'll cover why in a moment.

Prefer immutable factories

Java 9 introduced factory methods List.of(), Set.of(), and Map.of() that create unmodifiable collections. In production code, these should be your default for fixed data.

// Old way: mutable by default, risk of accidental modification
List<String> statuses = new ArrayList<>();
statuses.add("pending");
statuses.add("confirmed");
statuses.add("completed");
return statuses; // Caller might modify it—bad

// Better: immutable, thread-safe to share, clear intent
List<String> statuses = List.of("pending", "confirmed", "completed");
return statuses; // Caller cannot modify; safe to share across threads

Why does this matter? In a microservice handling thousands of concurrent requests, immutable collections eliminate a whole class of race conditions. We've debugged issues where one thread modified a status list while another thread iterated it. Immutable factories make that impossible.

The factory methods also optimize for common cases. List.of() with 10 or fewer elements uses a compact internal representation. When you need to build a large collection incrementally, fall back to the mutable constructor and convert at the end:

// Building incrementally? Use mutable first
var riders = new ArrayList<Rider>();
for (var id : riderIds) {
    riders.add(fetchRider(id));
}

// Convert to immutable when done
List<Rider> immutableRiders = List.copyOf(riders);
// or, in newer code:
List<Rider> immutableRiders = Collections.unmodifiableList(riders);

Avoid LinkedList

LinkedList is the collection type we reach for when we think "linked list" in a data structures course. In practice, it almost never wins. Here's why: modern CPUs are cache-optimized. ArrayList stores elements contiguously in memory, so accessing element 0, then element 1, then element 2 is very fast—the CPU prefetches the next block. LinkedList scatters nodes across the heap, forcing cache misses on every traversal.

Let's benchmark a real scenario: filtering 100,000 ride requests by status.

List<RideRequest> requests = new ArrayList<>();
// populate with 100k requests...

// LinkedList: Looks good on paper, terrible in practice
long start = System.nanoTime();
LinkedList<RideRequest> filtered = new LinkedList<>();
for (var req : requests) {
    if (req.getStatus().equals("pending")) {
        filtered.add(req); // O(1) insertion at tail
    }
}
long linkedTime = System.nanoTime() - start;

// ArrayList: Cache-friendly, 5–10x faster
start = System.nanoTime();
ArrayList<RideRequest> filtered2 = new ArrayList<>();
for (var req : requests) {
    if (req.getStatus().equals("pending")) {
        filtered2.add(req); // Amortized O(1), cache hit
    }
}
long arrayTime = System.nanoTime() - start;

System.out.println("LinkedList: " + linkedTime + "ns");
System.out.println("ArrayList: " + arrayTime + "ns");
// Output: ArrayList wins decisively

The only legitimate use for LinkedList is if you're frequently removing elements from the middle or front (not the tail). In a CRM, if you're processing a queue of tasks and popping from the front repeatedly, LinkedList.removeFirst() is O(1). But even then, java.util.Deque backed by ArrayDeque is often faster.

// If you genuinely need queue-like behavior:
Deque<Task> tasks = new ArrayDeque<>();
tasks.addLast(newTask);
Task current = tasks.removeFirst(); // O(1), and faster than LinkedList

Rule of thumb: default to ArrayList. Switch to LinkedList only if you profile and prove it's faster for your specific access pattern.

Size hints matter

HashMap and ArrayList grow dynamically, but growth has a cost. When the internal array fills past a load factor threshold (75% for HashMap, 100% for ArrayList), the collection allocates a new, larger array and copies everything. In high-throughput systems—a SaaS analytics pipeline, a trading engine, a ride-hailing dispatch system—these resizing operations can cause latency spikes.

Providing an initial capacity avoids this:

// Without size hint: HashMap resizes multiple times as we add 50k users
Map<String, User> userCache = new HashMap<>();
for (var userId : userIds) { // 50,000 IDs
    userCache.put(userId, fetchUser(userId));
}

// With size hint: Allocated once at 50k capacity
Map<String, User> userCache = new HashMap<>(75000); // 50k / 0.75
for (var userId : userIds) {
    userCache.put(userId, fetchUser(userId));
}

The denominator (0.75) is the default load factor. If you expect 50,000 entries, allocate 50000 / 0.75 ≈ 67,000 initial capacity. The cost is slightly higher baseline memory, but you avoid GC pressure and latency from repeated resizing.

The same applies to ArrayList:

// Without size hint
List<String> logs = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    logs.add("Event " + i);
}

// With size hint: One allocation, no resizing
List<String> logs = new ArrayList<>(100000);
for (int i = 0; i < 100000; i++) {
    logs.add("Event " + i);
}

In our experience, this matters most in two places: hot request paths (every millisecond counts) and batch processing (GC pressure compounds). It's a small change with measurable impact.

Common mistakes

Using the wrong Map for sorted data: We've seen code that adds to a regular HashMap, then calls .entrySet().stream().sorted() on every read. If you need sorted access, use TreeMap from the start or sort once and cache the result.

// Mistake: Sort on every read
Map<String, Integer> scoreMap = new HashMap<>();
// ... populate ...
scoreMap.entrySet().stream()
    .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
    .forEach(System.out::println); // O(n log n) every time

// Better: TreeMap if you need sorted iteration
NavigableMap<String, Integer> scoreMap = new TreeMap<>(
    Comparator.comparingInt(scoreMap::get).reversed()
);
// Entries are always sorted; iteration is O(n)

Modifying a collection while iterating: This causes ConcurrentModificationException. Use an iterator or stream instead.

// Mistake
List<String> names = new ArrayList<>(Arrays.asList("alice", "bob", "charlie"));
for (String name : names) {
    if (name.equals("bob")) {
        names.remove(name); // Crash!
    }
}

// Right: Use iterator
for (var it = names.iterator(); it.hasNext();) {
    String name = it.next();
    if (name.equals("bob")) {
        it.remove();
    }
}

Assuming HashSet maintains insertion order: It doesn't. Use LinkedHashSet if you need that.

Forgetting to handle null keys/values: HashMap allows one null key and any number of null values. HashSet allows one null element. TreeMap and TreeSet do not (they need comparison, and null isn't comparable). This matters in production when data quality varies.

Key takeaways

• Choose ArrayList by default for ordered, index-based access. Its cache efficiency beats LinkedList in nearly all real-world scenarios.
• Use HashSet or LinkedHashSet for uniqueness checks and deduplication; membership testing is O(1).
• Reach for HashMap for key-value lookups; provide an initial capacity if you know the size to avoid resizing overhead.
• Use TreeMap when you need sorted iteration by key; it costs O(log n) per operation but maintains order.
• Prefer immutable factories (List.of, Set.of, Map.of) for thread safety and clarity; they're safe to share and prevent accidental modification.
• Avoid LinkedList unless you're profiling and genuinely need frequent removal from the head or middle. ArrayDeque is usually better for queue-like behavior.
• In hot paths and batch processing, provide size hints to collections to avoid GC pressure from repeated resizing.