Java Collections for LLD
Pick the right List, Map, Set, Queue, or concurrent collection — and know the tradeoffs cold.
Introduction
Java Collections are the default vocabulary for LLD interviews. A strong candidate does not merely say use a list or use a map. They explain the access pattern, ordering requirement, uniqueness rule, concurrency boundary, and Big-O tradeoff behind the choice.
For Amazon, Oracle, and Flipkart style rounds, collections often decide whether your design is clean or accidentally inefficient. LRU cache needs access-ordered LinkedHashMap. Task scheduling needs PriorityQueue. Membership checks need HashSet. Ordered leaderboards need TreeMap or TreeSet. Concurrent session registries need ConcurrentHashMap, not a synchronized wrapper around a random map.
Learning Objectives
Explain the Java Collection hierarchy and why Map is separate from Collection.
Choose between ArrayList and LinkedList using access, insertion, and memory tradeoffs.
Choose between HashSet, LinkedHashSet, and TreeSet using uniqueness, ordering, and lookup complexity.
Choose between HashMap, LinkedHashMap, TreeMap, and ConcurrentHashMap for LLD storage and indexing needs.
Use Queue, Deque, ArrayDeque, and PriorityQueue for FIFO, stack, double-ended, and priority-driven workflows.
Compare common collection operations using Big-O and state realistic average-case versus ordered-structure costs.
Apply LinkedHashMap access-order mode to design an LRU cache.
Explain Comparable versus Comparator, fail-fast iteration, and immutable collection factories such as List.of.
Core Theory
Collections are design decisions, not syntax shortcuts
In LLD, every collection should answer four questions:
- Access pattern: Do callers need index lookup, key lookup, sorted order, FIFO, or priority order?
- Mutation pattern: Are inserts mostly at the end, at both ends, or arbitrary positions?
- Ordering rule: Is order irrelevant, insertion order, access order, natural sorted order, or custom sorted order?
- Concurrency boundary: Is the collection private to one object, externally synchronized, or shared by many threads?
Program to interfaces in fields and method signatures, then choose concrete classes at construction. This keeps the design flexible while still making performance explicit.
import java.util.ArrayList;
import java.util.List;
public final class Playlist {
private final List<Song> songs = new ArrayList<>();
public void append(Song song) {
songs.add(song);
}
public Song songAt(int index) {
return songs.get(index);
}
public List<Song> snapshot() {
return List.copyOf(songs);
}
}Collection hierarchy in one mental model
Iterable is the root capability for enhanced for loops. Collection extends it and represents a group of elements. List, Set, and Queue are the main Collection subinterfaces. Deque extends Queue for operations at both ends.
Map is separate because it stores key-value associations, not standalone elements. A map can expose collection views through keySet, values, and entrySet, but the map itself is not a Collection.
This hierarchy matters in LLD because it tells you what behavior your class is promising. If a method accepts Collection, it promises only grouped elements. If it accepts List, it promises order and positional access. If it accepts NavigableMap, it promises sorted range operations.
List: ArrayList versus LinkedList
ArrayList is backed by a resizable array. It is the default List for most LLD answers because indexed get is O(1), appending is amortized O(1), iteration is cache-friendly, and memory overhead is low.
LinkedList is a doubly linked list. It provides O(1) insertion or removal only when you already have a node position through an iterator. Finding an index is O(n), each element carries extra node pointers, and CPU locality is poor. It is rarely the best List choice.
Use ArrayList for ordered collections, history lists, menu items, seats on a row, or snapshots. Use LinkedList only when you need a List plus frequent iterator-based middle removals, or when an API specifically benefits from its Deque behavior. For stack or queue behavior, prefer ArrayDeque instead.
Set: HashSet, LinkedHashSet, and TreeSet
HashSet gives average O(1) add, remove, and contains. It is the default for membership, de-duplication, reserved identifiers, blocked users, assigned seats, or visited states. It relies on correct equals and hashCode.
LinkedHashSet keeps insertion order while preserving average O(1) lookup. Use it when you need deterministic iteration, such as returning selected filters, recently discovered IDs, or unique items in input order.
TreeSet keeps elements sorted using natural order or a Comparator. Add, remove, and contains are O(log n). Use it for rankings, next available slots, range queries, and ordered uniqueness. It relies on comparison consistency: if compare says two elements are equal, the set treats them as duplicates.
Map: HashMap, LinkedHashMap, TreeMap, and ConcurrentHashMap
HashMap is the default key-value index. Use it for ID to object lookup, user to session lookup, product to inventory lookup, and cache tables when ordering does not matter. Average get, put, remove, and containsKey are O(1).
LinkedHashMap adds predictable iteration order. In insertion-order mode it returns entries in the order inserted. In access-order mode it moves recently read or updated entries to the end, making it ideal for LRU cache design.
TreeMap stores keys in sorted order and supports ordered operations such as firstKey, ceilingKey, floorKey, and subMap. Most operations are O(log n). Use it for schedules, price ranges, leaderboards, and time-indexed events.
ConcurrentHashMap supports thread-safe concurrent access without locking the entire map for common operations. Use it for shared registries and counters in concurrent LLD answers. It does not allow null keys or null values, and compound workflows still need careful atomic methods such as compute, merge, and putIfAbsent.
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
public final class SessionRegistry {
private final ConcurrentMap<String, Session> sessions = new ConcurrentHashMap<>();
public Session getOrCreate(String userId) {
return sessions.computeIfAbsent(userId, id -> new Session(id));
}
public void remove(String userId) {
sessions.remove(userId);
}
}Queue and Deque: ArrayDeque and PriorityQueue
Queue models processing order. Use it for BFS, ticket counters, message dispatch, waiting rooms, and producer-consumer handoff at the design level.
Deque supports both ends. ArrayDeque is the best in-memory stack and double-ended queue for most single-threaded LLD designs. It gives amortized O(1) add and remove at both ends and avoids the node overhead of LinkedList.
PriorityQueue always exposes the smallest element according to natural order or a Comparator. Offer and poll are O(log n), peek is O(1), and arbitrary contains or removal is O(n). Use it for task scheduling, min available resource, top priority order, delayed work, and closest item selection.
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;
public final class DispatchCenter {
private final ArrayDeque<Request> fifo = new ArrayDeque<>();
private final Queue<Request> urgent = new PriorityQueue<>((a, b) -> Integer.compare(b.priority(), a.priority()));
public void enqueue(Request request) {
if (request.priority() > 0) {
urgent.offer(request);
} else {
fifo.addLast(request);
}
}
public Request next() {
return !urgent.isEmpty() ? urgent.poll() : fifo.pollFirst();
}
}Big-O must match the operation you actually perform
A common interview mistake is quoting one Big-O for the whole collection. Always name the exact operation. ArrayList.get is O(1), but ArrayList.contains is O(n). PriorityQueue.peek is O(1), but PriorityQueue.remove(object) is O(n). HashMap.get is average O(1), but resizing, hashing quality, and key equality still matter.
Also separate logical complexity from object cost. TreeMap gives O(log n) lookup, but it buys sorted keys and range queries. LinkedHashMap has average O(1) lookup, but it pays memory for linked iteration order. The best LLD answer names both the asymptotic cost and the reason the cost is acceptable for the workload.
LinkedHashMap access-order mode powers LRU caches
LinkedHashMap can maintain insertion order or access order. Access order means every successful get or put moves that entry to the most recently used end.
For an LRU cache, create a LinkedHashMap with access-order enabled and override removeEldestEntry. Reads become cache usage signals automatically, and eviction checks stay centralized. This is a classic Iterator-pattern-adjacent design because the map owns a deterministic traversal order of entries.
import java.util.LinkedHashMap;
import java.util.Map;
public final class LruCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LruCache(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}Comparable versus Comparator
Comparable defines the natural order inside the class itself. Use it when the ordering is intrinsic and stable, such as Money by amount, Version by version number, or Task by scheduled time if that is the domain identity.
Comparator defines an external order. Use it when different screens, services, or workflows sort the same objects differently: priority first, created time first, price ascending, rating descending, or distance ascending.
For TreeSet, TreeMap, and PriorityQueue, the chosen comparison determines both ordering and equality for sorted structures. Keep comparison consistent with equals when uniqueness matters, or document why it intentionally differs.
import java.time.Instant;
import java.util.Comparator;
public final class Task implements Comparable<Task> {
private final Instant scheduledAt;
private final int priority;
public Task(Instant scheduledAt, int priority) {
this.scheduledAt = scheduledAt;
this.priority = priority;
}
public Instant scheduledAt() {
return scheduledAt;
}
public int priority() {
return priority;
}
@Override
public int compareTo(Task other) {
return scheduledAt.compareTo(other.scheduledAt);
}
public static Comparator<Task> byPriorityThenTime() {
return Comparator.comparingInt(Task::priority)
.reversed()
.thenComparing(Task::scheduledAt);
}
}Iteration and fail-fast behavior
Most non-concurrent Java collections expose fail-fast iterators. If you structurally modify the collection outside the iterator while iterating, the iterator may throw ConcurrentModificationException. This is a bug-detection feature, not a concurrency guarantee.
Use the iterator's own remove method for safe removal during iteration. For bulk filtering, use removeIf. For concurrent maps, iterators are usually weakly consistent: they do not throw fail-fast exceptions, but they may reflect some updates and miss others while traversal is in progress.
import java.util.Iterator;
import java.util.List;
public final class OrderCleaner {
public void removeExpired(List<Order> orders) {
Iterator<Order> iterator = orders.iterator();
while (iterator.hasNext()) {
if (iterator.next().isExpired()) {
iterator.remove();
}
}
}
}Immutability with List.of and copy factories
List.of, Set.of, and Map.of create unmodifiable collections and reject null elements. List.copyOf, Set.copyOf, and Map.copyOf create unmodifiable snapshots from existing collections.
Use these factories when returning internal state, storing constructor inputs, or publishing configuration. They prevent callers from changing the collection structure. Remember that unmodifiable collection structure does not make mutable element objects themselves immutable.
import java.util.List;
import java.util.Map;
public final class RolePolicy {
private final List<String> roles;
private final Map<String, Integer> quotaByRole;
public RolePolicy(List<String> roles) {
this.roles = List.copyOf(roles);
this.quotaByRole = Map.of("ADMIN", 100, "MEMBER", 10);
}
public List<String> roles() {
return roles;
}
}Diagrams
Java Collections hierarchy used in LLD
Comparisons
Collection selection guide for LLD
| Need | Best choice | Why it fits | Avoid when |
|---|---|---|---|
| Ordered sequence with index lookup | ArrayList | O(1) indexed access and efficient append | Frequent arbitrary insertions at the front or middle dominate the workload |
| Unique membership with no ordering requirement | HashSet | Average O(1) add, remove, and contains | Iteration order must be deterministic or sorted |
| Unique membership preserving input order | LinkedHashSet | Average O(1) lookup plus insertion-order iteration | Sorted order or range navigation is required |
| Unique sorted values or next value queries | TreeSet | O(log n) operations with sorted navigation | You only need membership and unordered O(1) average lookup |
| Key-value lookup by ID | HashMap | Average O(1) put, get, remove, and containsKey | Keys must be returned in insertion, access, or sorted order |
| LRU cache or deterministic map iteration | LinkedHashMap | Average O(1) map operations plus insertion-order or access-order traversal | The map is heavily shared across threads without synchronization |
| Sorted keys and range queries | TreeMap | O(log n) lookup with first, last, floor, ceiling, and range views | Only direct key lookup is required at very high throughput |
| Shared concurrent key-value registry | ConcurrentHashMap | Thread-safe concurrent access and atomic compute operations | Null keys or null values are required |
| Stack, queue, or double-ended queue | ArrayDeque | Amortized O(1) operations at both ends with low memory overhead | Priority ordering or thread-safe blocking behavior is required |
| Always process next highest or lowest priority | PriorityQueue | O(log n) offer and poll with O(1) peek | You need fast contains, arbitrary removal, or full sorted iteration |
Big-O comparison of common operations
| Collection | add or put | remove | get or peek | contains or lookup | Ordering guarantee |
|---|---|---|---|---|---|
| ArrayList | Append amortized O(1), insert middle O(n) | By index or value O(n) | By index O(1) | Contains O(n) | Insertion order by index |
| LinkedList | At ends O(1), at found iterator O(1), find position O(n) | Known iterator O(1), by value or index O(n) | By index O(n), peek ends O(1) | Contains O(n) | Insertion order |
| HashSet | Average O(1) | Average O(1) | No indexed get | Average O(1) | No stable guarantee |
| LinkedHashSet | Average O(1) | Average O(1) | No indexed get | Average O(1) | Insertion order |
| TreeSet | O(log n) | O(log n) | First, last, ceiling, floor O(log n) | O(log n) | Sorted order |
| HashMap | Average O(1) | Average O(1) | Average O(1) by key | Average O(1) containsKey | No stable guarantee |
| LinkedHashMap | Average O(1) | Average O(1) | Average O(1) by key | Average O(1) containsKey | Insertion order or access order |
| TreeMap | O(log n) | O(log n) | O(log n) by key | O(log n) containsKey | Sorted key order |
| ConcurrentHashMap | Average O(1) | Average O(1) | Average O(1) by key | Average O(1) containsKey | No global iteration snapshot guarantee |
| ArrayDeque | Ends amortized O(1) | Ends amortized O(1), arbitrary O(n) | Peek ends O(1) | Contains O(n) | Deque order |
| PriorityQueue | Offer O(log n) | Poll O(log n), arbitrary remove O(n) | Peek O(1) | Contains O(n) | Heap priority for head only |
Comparable versus Comparator
| Dimension | Comparable | Comparator | LLD guidance |
|---|---|---|---|
| Ownership | Defined inside the class | Defined outside the class | Use Comparable only when one natural order truly belongs to the domain object |
| Number of orderings | One natural order | Many possible orderings | Use Comparator for screen-specific, workflow-specific, or policy-specific ordering |
| Typical usage | Task sorted by scheduled time | Task sorted by priority, owner, or creation time | Prefer Comparator when the interviewer asks for configurable ranking |
| Risk | Hard to change without changing the model class | Can conflict with equals if careless | State the equality and ordering rule explicitly for TreeSet and TreeMap |
Best Practices
- ✓
Declare fields and parameters with interfaces such as List, Set, Map, Queue, or Deque; instantiate concrete classes where the performance decision is made.
- ✓
Use ArrayList as the default List unless there is a proven iterator-based removal or Deque requirement.
- ✓
Use HashSet for membership checks and de-duplication, but switch to LinkedHashSet when deterministic iteration matters.
- ✓
Use HashMap for ordinary lookup, LinkedHashMap for deterministic or access-order iteration, TreeMap for sorted keys, and ConcurrentHashMap for shared concurrent lookup.
- ✓
Prefer ArrayDeque over Stack and LinkedList for stack or queue behavior in single-threaded designs.
- ✓
Use PriorityQueue only when the next item by priority matters; do not expect it to iterate in fully sorted order.
- ✓
Make key objects immutable or at least keep fields used by equals and hashCode stable while the object is inside a hash-based collection.
- ✓
Return List.copyOf, Set.copyOf, Map.copyOf, or unmodifiable snapshots instead of exposing mutable internal collections.
- ✓
Use Iterator.remove or removeIf for structural removal during traversal; do not mutate a collection directly inside an enhanced for loop.
- ✓
For concurrent designs, prefer atomic map operations such as compute, merge, and putIfAbsent over separate check-then-act steps.
Common Mistakes
- ×
Choosing LinkedList for frequent indexed access because it sounds cheaper for insertion.
- ×
Using PriorityQueue and assuming iteration returns elements in priority order.
- ×
Using HashSet or HashMap with mutable keys whose hashCode changes after insertion.
- ×
Forgetting that TreeSet uniqueness is based on comparison, not only equals.
- ×
Returning a mutable internal List and allowing callers to bypass class invariants.
- ×
Using Collections.synchronizedMap but still performing multi-step check-then-act logic outside a shared lock.
- ×
Ignoring null behavior: ConcurrentHashMap rejects null keys and values, while List.of and Map.of reject null elements.
- ×
Modifying a collection inside an enhanced for loop and being surprised by fail-fast behavior.
- ×
Using HashMap when deterministic output order is part of the API contract.
- ×
Using List for membership checks where Set would communicate intent and improve lookup complexity.
Quiz
0/8 answered
1.Which collection is usually the best default for an ordered list with frequent index-based reads?
2.Which collection should you choose for unique values that must iterate in insertion order?
3.Why is LinkedHashMap useful for an LRU cache?
4.Which map is the best fit for sorted key navigation such as floorKey and ceilingKey?
5.What is the correct Big-O for PriorityQueue.peek and PriorityQueue.poll?
6.When should Comparator be preferred over Comparable?
7.What can happen if a non-concurrent collection is structurally modified during enhanced for iteration?
8.What is true about List.of?
Flashcards
Cheat Sheet
Hierarchy: Iterable enables iteration. Collection groups elements. List, Set, and Queue extend Collection. Deque extends Queue. Map is separate because it stores key-value pairs.
List: ArrayList is the default for ordered indexed data. LinkedList rarely wins; use it only for iterator-position changes or when Deque behavior is intentionally needed.
Set: HashSet for fastest average membership. LinkedHashSet for deterministic insertion order. TreeSet for sorted uniqueness and O(log n) navigation.
Map: HashMap for ordinary key lookup. LinkedHashMap for insertion-order or access-order traversal. TreeMap for sorted keys and range queries. ConcurrentHashMap for shared concurrent registries.
Queue and Deque: ArrayDeque is the preferred stack, FIFO queue, and double-ended queue for single-threaded memory structures. PriorityQueue is for next-by-priority, not full sorted traversal.
Big-O anchors: ArrayList get O(1), contains O(n). HashSet and HashMap average lookup O(1). TreeSet and TreeMap operations O(log n). ArrayDeque end operations amortized O(1). PriorityQueue peek O(1), offer and poll O(log n), contains O(n).
LRU: LinkedHashMap with access-order enabled plus removeEldestEntry gives a concise LRU cache design.
Ordering: Comparable is natural order inside the class. Comparator is external policy and is better for multiple orderings.
Iteration: Non-concurrent collections are usually fail-fast. Use Iterator.remove, removeIf, or concurrent collection semantics intentionally.
Immutability: List.of, Set.of, Map.of, and copyOf factories create unmodifiable structures and reject nulls. They do not freeze mutable element objects.
References
- DocsOracle Java Tutorials: Collections Framework
- DocsJava Platform API Specification: java.util Package
- BookEffective Java — Joshua Bloch
- BookJava Concurrency in Practice — Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes, and Doug Lea