Java Collections Performance: Choosing the Right Data Structure (2026)

Using the wrong Java collection doesn't fail fast — it degrades gradually. LinkedList used as a stack is fine for 100 elements and catastrophic for 100,000. ArrayList with remove(0) in a loop is O(n²). HashMap with a poorly implemented hashCode() degrades to O(n) per lookup. The fix in each case is one line — but you have to know which line.

---

The Big-O Reference

---

ArrayList vs LinkedList: The Common Mistake

// SLOW — remove(0) shifts all elements: O(n) per call → O(n²) total
LinkedList<Task> queue = new LinkedList<>();
while (!queue.isEmpty()) {
    process(queue.remove(0));
}

// FAST for queue operations — use ArrayDeque
ArrayDeque<Task> queue = new ArrayDeque<>();
queue.offer(task);   // Enqueue
task = queue.poll(); // Dequeue — O(1), no shifting

Rule: for FIFO queues, use ArrayDeque, not LinkedList or ArrayList. ArrayDeque is faster than LinkedList (better cache locality) and faster than ArrayList.remove(0) (no shifting).

// For stack (LIFO), also use ArrayDeque
ArrayDeque<String> stack = new ArrayDeque<>();
stack.push("a");    // O(1)
stack.pop();         // O(1)
// Do NOT use Stack<T> — it's synchronized (legacy) and slow

---

HashMap: The hashCode() Trap

// BAD hashCode — all objects hash to same bucket → O(n) lookups
public class BadKey {
    private final String value;

    @Override
    public int hashCode() { return 1; }  // Everything in one bucket!
    @Override
    public boolean equals(Object o) { ... }
}

Map<BadKey, String> map = new HashMap<>();
// With 10,000 entries: every get() scans all 10,000 — O(n) not O(1)

// GOOD — use records or proper hashCode
public record OrderKey(Long orderId, String region) {}
// Records auto-generate correct hashCode and equals

// Or use Objects.hash()
@Override
public int hashCode() {
    return Objects.hash(orderId, region, customerId);
}

For critical hot paths, you can verify distribution: map.entrySet().stream().collect(Collectors.groupingBy(e -> System.identityHashCode(e.getKey()) % 16, Collectors.counting())) — buckets should be roughly equal.

---

When to Use TreeMap vs HashMap

// HashMap — O(1) operations, unordered
Map<String, Product> productById = new HashMap<>();
productById.get("prod-123");  // Fast lookup

// TreeMap — O(log n), sorted by key
TreeMap<LocalDate, SalesReport> reportsByDate = new TreeMap<>();
reportsByDate.get(date);       // Slower lookup
reportsByDate.subMap(           // ONLY possible with TreeMap
    LocalDate.of(2026, 1, 1),
    LocalDate.of(2026, 3, 31)
).values();  // Reports for Q1

Use TreeMap when: you need range queries, floor/ceiling operations, or sorted iteration. For everything else, HashMap is faster.

---

Concurrent Collections

// BAD — synchronized on every read AND write
Map<String, CacheEntry> cache = Collections.synchronizedMap(new HashMap<>());
// synchronized(map) wraps every get/put — contention under load

// GOOD — ConcurrentHashMap: reads don't lock, writes lock segment only
Map<String, CacheEntry> cache = new ConcurrentHashMap<>();
cache.computeIfAbsent(key, k -> loadFromDb(k));  // Atomic, efficient

// For read-heavy, rarely-modified lists
List<Listener> listeners = new CopyOnWriteArrayList<>();
listeners.add(listener);    // Creates new array copy — slow write
listeners.forEach(l -> l.notify(event));  // No lock needed — reads are snapshot

Use CopyOnWriteArrayList for:

• Listener/observer lists
• Config values read frequently, updated rarely
• Thread-safe iteration without ConcurrentModificationException

---

Java 21: SequencedCollection

// New in Java 21 — consistent API for collections with defined order
SequencedCollection<String> list = new ArrayList<>(List.of("a", "b", "c"));

list.getFirst();      // "a" — previously: list.get(0)
list.getLast();       // "c" — previously: list.get(list.size()-1)
list.addFirst("z");   // Add to front — previously: list.add(0, "z")
list.reversed();      // Reversed view — previously: Collections.reverse(copy)

// Works on List, Deque, LinkedHashSet, TreeSet
SequencedSet<String> set = new LinkedHashSet<>(Set.of("a", "b", "c"));
set.getFirst();  // "a" — first element by insertion order

---

Immutable Collections for Thread Safety

// Pre-Java 9 — verbose and still mutable if cast
List<String> list = Collections.unmodifiableList(new ArrayList<>(Arrays.asList("a", "b")));

// Java 9+ — truly immutable, no copy needed, memory-efficient
List<String> immutable = List.of("a", "b", "c");  // Compact, immutable
Map<String, Integer> map = Map.of("a", 1, "b", 2);
Set<String> set = Set.of("x", "y", "z");

// For large collections
List<String> copy = List.copyOf(mutableList);  // Defensive copy, immutable

Immutable collections from List.of() have a smaller memory footprint than ArrayList and are inherently thread-safe — no synchronization needed.

---

Common Mistakes to Avoid

• LinkedList as a general-purpose list — ArrayList beats LinkedList for almost everything due to better cache locality; only use LinkedList when you need O(1) head/tail additions with Deque interface
• Vector or Hashtable — legacy, fully synchronized on every operation; use ArrayList + ConcurrentHashMap instead
• new ArrayList<>(collection) when you only need read access — use List.copyOf(collection) for an immutable snapshot, or pass the collection directly if mutation isn't needed
• Not initializing HashMap capacity — new HashMap<>(expectedSize * 4 / 3 + 1) avoids rehashing for large maps; the default initial capacity of 16 with load factor 0.75 causes rehashing at 12 entries

---

Summary

Choose Java collections based on access patterns: ArrayList for indexed access, ArrayDeque for queues and stacks, HashMap for key lookup, TreeMap for sorted ranges, ConcurrentHashMap for concurrent maps, CopyOnWriteArrayList for read-heavy concurrent lists, and List.of() / Map.of() for immutable data. The wrong choice rarely breaks anything immediately — but it makes your application slower in proportion to its success.

---

Detect Collection Performance Issues

JOptimize detects LinkedList used as a general list, Vector/Hashtable usage, missing initial capacity on large HashMaps, and synchronization bottlenecks in concurrent code.

• IntelliJ Plugin — collection performance analysis inline: Install JOptimize for IntelliJ
• Web Dashboard — full data structure audit: Analyze your project free →

Pick the right collection once, save performance tuning forever.