Choosing Java Collections by Operation Costs

Hello. In the last lesson, you compared correct algorithms by time, auxiliary space, mutation rules, and implementation risk. This lesson makes that comparison concrete at the Java API level: a solution’s complexity depends not only on its loops, but on the cost of the collection operations inside those loops.

For interview problems, the goal is not to memorize every class in java.util. It is to identify the operations your solution performs most often—lookup, indexed access, insertion at an end, maintaining order, retrieving a minimum—and choose a collection whose guarantees fit. This is especially useful in interviews at companies such as Google or Walmart, where explaining why a data structure fits is often as important as writing the code.

---

Choose semantics first, then operation costs

Start with a simple question:

What relationship must the stored values have?

This narrows the choice before any complexity analysis.

Need	Primary abstraction	Typical Java choice
Ordered sequence; duplicates allowed	List	ArrayList
Unique values; fast membership checks	Set	HashSet
Associate a key with a value	Map	HashMap
Process first-in, first-out or last-in, first-out	Deque	ArrayDeque
Repeatedly retrieve smallest or largest remaining item	PriorityQueue	PriorityQueue
Maintain values or keys in sorted order	Sorted map/set	TreeMap, TreeSet

For example, if duplicates must be rejected, an ArrayList is already the wrong semantic fit, even if it is convenient to write. If you need to find whether an item has appeared before, use a set. If you need its previous index or frequency as well, use a map.

Only after choosing the right abstraction should you compare implementations such as HashSet versus TreeSet, or ArrayList versus LinkedList.

A useful interview habit is to declare a variable by its interface and instantiate it with the implementation you selected:

List<String> results = new ArrayList<>();
Set<Integer> seen = new HashSet<>();
Map<Character, Integer> counts = new HashMap<>();
Deque<TreeNode> work = new ArrayDeque<>();

The left side communicates the required behavior. The right side communicates the performance decision. It also makes a later substitution easier if requirements change.

---

The high-value operation-cost reference

Interview analysis normally uses these standard costs. For hash-based structures, say expected $O(1)$, because performance relies on a reasonably distributed hash function and normal resizing behavior.

Collection	Fast operations	Costly operations	Ordering guarantee	Interview default
ArrayList<E>	get(i), set(i): $O(1)$; append: amortized $O(1)$	Insert/remove near front or middle: $O(n)$; contains: $O(n)$	Insertion order, duplicates allowed	General-purpose list
LinkedList<E>	Add/remove at either end: $O(1)$	get(i), indexed insert/remove: $O(n)$	Insertion order, duplicates allowed	Usually avoid as a regular list
ArrayDeque<E>	Add, remove, inspect at either end: amortized $O(1)$	Arbitrary indexed access is unavailable	Deque order	Stack or queue
HashSet<E>	add, remove, contains: expected $O(1)$	Ordered/range queries unavailable	No iteration order	Membership and deduplication
HashMap<K,V>	get, put, containsKey: expected $O(1)$	Ordered/range queries unavailable	No key iteration order	Counts, indices, lookup tables
LinkedHashSet<E> / LinkedHashMap<K,V>	Hash-style operations: expected $O(1)$	Slightly more bookkeeping than hash-only variants	Insertion order	When output order matters
TreeSet<E> / TreeMap<K,V>	add, remove, lookup: $O(\log n)$	Slower than hashing for ordinary lookup	Sorted order	Sorted traversal and range/neighbor queries
PriorityQueue<E>	peek: $O(1)$; offer, poll: $O(\log n)$	Arbitrary contains/removal are $O(n)$	Only the head is guaranteed highest priority	Repeated min/max selection

Two cautions make this table more useful:

1. Do not confuse API similarity with cost similarity. Both ArrayList and LinkedList provide get(i), but one reaches index $i$ directly and the other may traverse many nodes.
2. Analyze the whole operation. Inserting into a linked list after you already have a node reference is cheap. But list.add(index, value) must first locate that index, so its overall cost is still $O(n)$.

---

Lists: why ArrayList is normally the default

A List preserves positional order and permits duplicates. It is appropriate when the algorithm needs a sequence: collected results, interval lists, a list of adjacent items, or a dynamically built answer.

ArrayList: fast indexed access and iteration

ArrayList stores references in a resizable array. Given an index, Java can calculate where the element belongs in the backing array, making get(i) $O(1)$.

List<Integer> scores = new ArrayList<>();

scores.add(9);           // amortized O(1)
scores.add(4);           // amortized O(1)
int first = scores.get(0); // O(1)

Appending is amortized $O(1)$. Most additions simply occupy the next array slot. Occasionally the internal array fills, requiring allocation of a larger array and copying existing references, which is $O(n)$ for that individual append. Spread over many appends, the average per append remains constant.

But inserting or deleting in the middle requires shifting the elements after that position:

scores.add(1, 7);  // O(n): shift elements right
scores.remove(0); // O(n): shift elements left

That makes ArrayList the right default when your algorithm mostly:

• iterates through values,
• reads or updates positions by index,
• appends output values,
• stores data compactly.

It is also commonly the best practical list choice even when there are occasional middle insertions. Its elements are stored contiguously, which helps iteration and cache locality.

LinkedList: do not choose it merely because inserts sound cheap

A Java LinkedList is a chain of nodes, each holding an element and references to neighboring nodes. It knows its first and last nodes, so operations at either end are efficient. But to access the middle, Java must follow references node by node.

This is a classic hidden-cost trap:

List<Integer> values = new LinkedList<>();

for (int i = 0; i < values.size(); i++) {
    process(values.get(i));
}

The loop runs $n$ times. Each get(i) can take up to $O(n)$, so the total can become:

$$O(n^2)$$

If you are handed a LinkedList and must traverse it, use an enhanced for loop or an iterator:

for (int value : values) {
    process(value);
}

That traversal is $O(n)$, though it still typically has less favorable memory behavior than iterating over an ArrayList.

There is a narrow distinction worth stating accurately in an interview:

• At a known node or iterator position, linking or unlinking a LinkedList node is $O(1)$.
• At a numeric index, locating that position costs $O(n)$.
• In normal Java code, LinkedList is rarely the best answer for a general list problem.

---

Stacks and queues: use ArrayDeque

A stack needs last-in, first-out behavior. A queue needs first-in, first-out behavior. Both are endpoint-oriented, so choose the Deque interface and usually instantiate ArrayDeque.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(20);
int top = stack.pop();       // 20

Deque<String> queue = new ArrayDeque<>();
queue.offer("first");
queue.offer("second");
String next = queue.poll();  // "first"

For ArrayDeque, these endpoint operations are amortized $O(1)$:

• Queue: offer, poll, peek
• Stack: push, pop, peek
• Either end: addFirst, addLast, removeFirst, removeLast

Avoid using ArrayList as a queue if you repeatedly remove from index 0. Every removal shifts the remaining elements, creating $O(n)$ work per operation. Likewise, avoid the legacy Stack class in interview code; Deque expresses the intended behavior and ArrayDeque is the conventional choice.

This matters immediately for future tree and graph problems: breadth-first search needs a queue, while depth-first iterative traversal and next-greater-element problems need a stack.

---

Fast lookup: HashSet and HashMap

Hash-based collections are central to coding interviews because they replace repeated scans with expected constant-time lookups.

Use HashSet when only membership matters

A HashSet stores unique elements. It is ideal for questions such as:

• “Have I seen this value before?”
• “Does the input contain a duplicate?”
• “Which values are common to two collections?”
• “How do I eliminate duplicates?”

Set<Integer> seen = new HashSet<>();

for (int value : nums) {
    if (!seen.add(value)) {
        return true; // add returns false when value already exists
    }
}
return false;

The important operation is seen.add(value), expected $O(1)$. A list-based alternative that calls contains for every item can become $O(n^2)$, because ArrayList.contains scans linearly.

Use a HashSet when order does not matter. Do not promise a particular iteration order:

for (int value : seen) {
    // Order is unspecified.
}

Use HashMap when membership needs associated information

A HashMap associates each unique key with some value: a count, original index, boolean state, list of grouped values, or another object.

Map<Character, Integer> frequency = new HashMap<>();

for (char ch : text.toCharArray()) {
    frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
}

Each lookup and update is expected $O(1)$, making the complete frequency count expected $O(n)$.

The distinction is simple:

• “Does this value exist?”: HashSet<E>
• “What information do I associate with this key?”: HashMap<K, V>

For the earlier Two Sum example, the map is necessary because the output requires an index, not merely proof that a complement exists.

---

Order is a requirement, not a free feature

Hash collections optimize ordinary lookup, but they deliberately do not keep elements sorted or insertion-ordered. If the prompt requires a specific iteration order, make that requirement explicit.

Preserve first-seen order with linked hash collections

Use LinkedHashSet when elements must remain unique and be iterated in insertion order. Use LinkedHashMap for key-value data in insertion order.

Set<String> uniqueInEncounterOrder = new LinkedHashSet<>();

for (String word : words) {
    uniqueInEncounterOrder.add(word);
}

The collection still gives hash-style expected constant-time operations, while doing additional bookkeeping to preserve the order. This is often useful when an interviewer asks you to remove duplicates while retaining the first occurrence order.

Maintain sorted order with TreeSet and TreeMap

Use TreeSet or TreeMap when you must repeatedly work with values or keys in sorted order. They are tree-based, so common operations cost $O(\log n)$, rather than expected $O(1)$.

TreeMap<Integer, String> labelByScore = new TreeMap<>();

labelByScore.put(80, "good");
labelByScore.put(95, "excellent");

Integer threshold = labelByScore.ceilingKey(90); // 95

The cost is justified when the algorithm needs operations such as:

• iterate in sorted order;
• find the next greater or next smaller key;
• find the nearest boundary with floorKey, ceilingKey, lowerKey, or higherKey;
• maintain a dynamically changing sorted set.

Do not choose a TreeMap just because “sorted output might be nice.” If you only need fast lookup during the algorithm and can sort once at the end, a HashMap plus a final sort may be clearer and faster overall. The exact choice depends on whether ordering is needed throughout the computation or only in the final result.

---

PriorityQueue: choose it when the next best item matters

A PriorityQueue is not a FIFO queue. It is a heap: it efficiently exposes the smallest element by default, or the largest if you provide a reverse comparator.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

minHeap.offer(8);  // O(log n)
minHeap.offer(3);  // O(log n)
minHeap.offer(5);  // O(log n)

int smallest = minHeap.poll(); // 3, O(log n)

The key costs are:

$$\text{peek()}=O(1)$$ $$\text{offer()}=O(\log n),\text{poll()}=O(\log n)$$

This collection fits problems that repeatedly ask:

• “What is the smallest remaining item?”
• “What is the largest of the values I have retained?”
• “Keep the best $k$ candidates while processing a stream.”
• “Which task should run next under a priority rule?”

A priority queue does not keep every element fully sorted for iteration. Only its head is guaranteed to be the next-priority item. If the requirement is “return everything in sorted order,” you must repeatedly poll items, costing $O(n\log n)$ overall, or use a different strategy.

---

A repeatable selection routine

When an interviewer asks you to choose a collection, reason aloud in this order.

1. State the data relationship.
   “I need unique values,” “I need key-to-count associations,” or “I need to process values in FIFO order.”

2. Name the dominant operation.
   Is the algorithm dominated by membership checks, indexed reads, endpoint removals, sorted-neighbor queries, or min/max extraction?

3. Match it to the operation cost.
   For example: “A HashSet makes the repeated membership test expected $O(1)$, so the full scan is expected $O(n)$.”

4. Identify ordering and mutation constraints.
   Do duplicates matter? Must output retain insertion order? Is sorted order required during the algorithm?

5. Mention the relevant trade-off.
   Hash collections spend extra memory; trees pay $O(\log n)$ to remain ordered; ArrayList pays shifting costs for middle changes; ArrayDeque does not provide random access.

Here are concise interview-ready decisions:

Problem requirement	Choice and justification
Detect whether any duplicate exists	HashSet: expected $O(1)$ membership/insertion makes one pass expected $O(n)$
Count each character or number	HashMap: each key stores its frequency with expected $O(1)$ updates
Build results and access by index	ArrayList: $O(1)$ indexed access and amortized $O(1)$ append
Process nodes in first-discovered order	ArrayDeque as Deque: amortized $O(1)$ queue operations
Undo most recent work	ArrayDeque as Deque: amortized $O(1)$ stack operations
Deduplicate but preserve encounter order	LinkedHashSet: expected $O(1)$ set operations plus insertion-ordered iteration
Repeatedly find smallest current value	PriorityQueue: $O(1)$ peek and $O(\log n)$ insertion/removal
Query next key at or above a threshold	TreeMap: sorted keys support neighbor queries in $O(\log n)$

One final practical point: if an interview input is a fixed primitive array such as int[], keep it as an array unless the algorithm genuinely needs a collection’s additional behavior. Converting it to List<Integer> introduces boxing and allocation, and it does not improve simple indexed traversal.

---

Key takeaways

Select a collection by combining semantic needs with dominant operation costs:

• Use ArrayList as the default mutable list for indexed access, iteration, and appending.
• Avoid LinkedList for general indexed-list work; its positional access can quietly make an algorithm quadratic.
• Use ArrayDeque for interview stacks and queues.
• Use HashSet for unique membership and HashMap for fast key-associated lookup, both with expected $O(1)$ core operations.
• Use linked hash variants only when insertion order is an explicit requirement.
• Use TreeSet and TreeMap when sorted order or neighbor/range queries justify $O(\log n)$ operations.
• Use PriorityQueue when the next minimum or maximum matters, not when you need general queue order or fully sorted iteration.

Next, you will practice turning an interview plan into correct Java code from pseudocode—without relying on an IDE to supply method names, types, or structural fixes.