Choosing the right Java collection

The problem: a collection chosen by habit

A reporting endpoint loads a few thousand order lines and, for each one, checks whether the product id is in a List<String> of discontinued products. It works in tests with ten rows. With real data the endpoint becomes noticeably slow, because List.contains scans the list from the start every time: n lines times m discontinued products. Changing the list to a HashSet<String> turns each check into a single hash lookup, and the code does not get longer.

The lesson is not "always use HashSet". It is that every collection makes some operations cheap and others expensive, and the right choice follows from how you will access the data. This article gives you a way to decide.

Start with the question, not the class

Ask these in order:

1. Do I need to look things up by key? Then a Map.
2. Do I only need to know whether something is present, without duplicates? Then a Set.
3. Does order matter, and do I need access by position? Then a List.
4. Do I add and remove at the ends, as a queue or a stack? Then a Deque (ArrayDeque).
5. Does the order of iteration matter? Insertion order, sorted order, or "don't care" each point to different implementations.

Programming against the interface (List, Set, Map) keeps the choice of implementation local to one line.

Map<String, Customer> byId = new HashMap<>();List<OrderLine> lines = new ArrayList<>();Deque<Task> work = new ArrayDeque<>();

List: ArrayList versus LinkedList

ArrayList stores elements in a contiguous array. Access by index is constant time, appending is cheap on average, and iteration is friendly to the CPU cache because the elements are close together in memory. Inserting or removing in the middle costs shifting the elements after it.

LinkedList stores each element in a node with pointers to its neighbours. Inserting at a position you already hold an iterator for is cheap in theory, but reaching that position means walking the nodes, and every node is a separate object with its own memory overhead. In practice, for most workloads ArrayList is as fast or faster, even for many insertions, because of memory locality. LinkedList rarely wins on a real service workload; as a queue, ArrayDeque is usually the better tool.

Set and Map: three flavours

HashSet and HashMap give expected constant-time add, remove and lookup. They do not promise any iteration order, and they depend on a correct equals and hashCode contract.

LinkedHashMap (and LinkedHashSet) behave like their hash counterparts but remember insertion order, so iteration is predictable. With the access-order constructor they can also back a small LRU cache by overriding removeEldestEntry.

TreeMap (and TreeSet) keep keys sorted using Comparable or a Comparator. Operations cost logarithmic time, but you get range queries and navigation: firstKey, floorKey, headMap, subMap. Choose it when you need "the next value at or after X" or sorted iteration, not just because sorted output looks tidy.

var rates = new TreeMap<LocalDate, BigDecimal>();rates.put(LocalDate.of(2026, 1, 1), new BigDecimal("1.70"));rates.put(LocalDate.of(2026, 6, 1), new BigDecimal("1.72"));// the rate valid on a given day = the latest entry at or before itBigDecimal rate = rates.floorEntry(LocalDate.of(2026, 3, 15)).getValue();

The same lookup in a HashMap would require scanning all keys.

Deque for queues and stacks

ArrayDeque supports efficient add and remove at both ends. Use it as a stack (push, pop, peek) instead of the legacy Stack class, and as a queue (offer, poll) instead of LinkedList. Note that ArrayDeque does not allow null elements and is not thread-safe. For concurrent hand-off between threads, look at the java.util.concurrent queues, discussed in concurrency basics.

Immutable collections

List.of, Set.of and Map.of (Java 9+) create unmodifiable collections. They reject null elements, and Set.of and Map.of throw on duplicates at creation. Their iteration order for sets and maps is intentionally unspecified and can differ between runs, so never rely on it.

List<String> roles = List.of("USER", "ADMIN");roles.add("AUDITOR");              // UnsupportedOperationExceptionList<String> copy = List.copyOf(source);   // defensive snapshot

Two details deserve attention. Collections.unmodifiableList(list) is only a read-only view: if someone keeps the original list and changes it, the view changes too. List.copyOf makes a real copy. And "unmodifiable" is shallow: the elements themselves can still be mutable objects.

Returning immutable collections from your methods prevents callers from changing your internal state by accident, and makes sharing between threads safer.

A decision table

Common mistakes

• Using List.contains or list.remove(object) inside a loop over a large list. Convert to a Set or Map first.
• Choosing LinkedList because "inserts are O(1)" without measuring or considering that finding the position is O(n).
• Mutating a list while iterating with a for-each loop, which throws ConcurrentModificationException. Use removeIf or an Iterator.
• Relying on HashMap or HashSet iteration order in tests or output.
• Exposing a mutable internal collection from a getter. Return List.copyOf(items) or an unmodifiable view deliberately.
• Sharing a plain HashMap between threads. Results range from lost updates to corrupted state; use a concurrent map or confine it to one thread.
• Passing a negative or huge initial capacity without thinking; if you know the size, new ArrayList<>(n) avoids repeated resizing, but it is an optimisation, not a necessity.

Trade-offs

Hash-based structures trade ordering for speed. Tree-based ones trade some speed for sorted access. Linked-hash variants trade a little memory for predictable output. Immutable collections trade flexibility for safety and clearer reasoning. The cheapest decision to reverse is the implementation class behind an interface, so do not over-agonise; the more expensive mistake is the wrong kind of structure, such as scanning a list where a map belongs.

Also remember that the asymptotic cost is only part of the story. For small collections of a few dozen elements the difference between implementations is usually irrelevant, and clarity of intent should win.

Checklist

• State the main access pattern in a sentence before choosing.
• Declare variables with the interface type.
• Use Set/Map for membership and key lookups.
• Use ArrayDeque, not Stack or LinkedList, for queues and stacks.
• Return immutable or copied collections from public methods.
• Never share non-concurrent collections between threads.

Where to go next

Read about stream pipelines and collectors to see how groupingBy and toMap build maps from lists, and about concurrency basics for thread-safe collections. The junior Java developer roadmap shows where collections fit among the other core skills.