Choosing Java Data Structures by Operation Costs

Hello again. In the previous lesson, you used input constraints to set a performance budget: for $n\le 10^5$, a quadratic design is usually ruled out before you code it. This lesson supplies the next link in that reasoning chain: once you know the operation budget, choose a Java structure whose expensive operations are not on your algorithm’s critical path.

For an interview solution, do not begin with “Which collection class do I remember?” Begin with: What information must I retrieve, update, or remove repeatedly—and must it be indexed, unique, ordered, or prioritized? By the end of this lesson, you should be able to justify choices such as HashMap, ArrayDeque, PriorityQueue, or ArrayList in one precise sentence.

---

Choose from operations, not names

A data structure is useful because it makes some operations cheap by making other operations more expensive or by using extra memory.

Consider three ways to answer “Have I already seen value $x$?” while scanning $n$ integers:

// List: contains may scan the whole list
List<Integer> seen = new ArrayList<>();

for (int x : nums) {
    if (seen.contains(x)) {
        // found a duplicate
    }
    seen.add(x);
}

ArrayList.contains(x) is $O(n)$. If it happens inside a loop over $n$ values, the total becomes $O(n^2)$. At $n=10^5$, that conflicts with the performance target from the previous lesson.

The question is fundamentally membership, not positional storage. A set expresses that requirement directly:

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

for (int x : nums) {
    if (!seen.add(x)) {
        // x was already present
    }
}

For HashSet, add, remove, and membership testing are expected $O(1)$, giving expected $O(n)$ total time. The structure did not merely make the code shorter; it removed the repeated linear search.

Use this four-part decision process before coding:

1. Name the repeated operation.
   Examples: random access by index, membership test, lookup by key, remove the smallest item, or add and remove at an endpoint.

2. Count how often it occurs.
   An $O(n)$ operation once may be fine. An $O(n)$ operation in each of $n$ iterations usually is not.

3. Identify semantic requirements.
   Do you need duplicates? insertion order? sorted order? only the current minimum? This is as important as Big-O.

4. Select the simplest Java structure that makes the repeated operation cheap.
   Prefer standard interfaces such as List, Set, Map, Deque, and Queue in declarations; choose the concrete implementation for its costs.

This compact cheat sheet will be a useful visual reference during the course. Treat its complexity labels as first approximations; we will add the important qualifications below, especially “expected,” “amortized,” and “only at the ends.”

Watch the selected portions of “Java Collections Explained (with examples)” by Visual Computer Science for a fast survey of the trade-offs among the collections used most often in interview code.

---

The interview operation map

The following table is the core reference for this lesson. Complexities refer to the typical operations relevant to DSA interviews.

Algorithm needs	Prefer in Java	Key operations	Typical cost	Important limitation
Fixed-size, indexed primitive data	int[], char[], etc.	read/write by index	$O(1)$	Fixed length
Dynamic sequence with indexed access	ArrayList<E>	get(i), set(i), append	$O(1)$, $O(1)$ amortized	Insert/remove in middle is $O(n)$
Unique membership, no ordering needed	HashSet<E>	add, contains, remove	expected $O(1)$	No sorted or insertion-order guarantee
Key-to-value lookup or counting	HashMap<K, V>	get, put, containsKey, remove	expected $O(1)$	Iteration order is unspecified
FIFO queue, LIFO stack, both ends	ArrayDeque<E>	offer, poll, push, pop	$O(1)$ amortized	No random access by index
Repeatedly retrieve min/max priority item	PriorityQueue<E>	offer, poll	$O(\log n)$	Only the head is directly accessible
Ordered keys plus predecessor/successor queries	TreeMap<K,V>, TreeSet<E>	lookup, insert, floor, ceiling	$O(\log n)$	Slower than hashing when order is unnecessary
General linked sequence	usually avoid LinkedList<E>	endpoint operations	$O(1)$	Index access and indexed traversal are costly

The high-value habit is to distinguish accessing a position from accessing an endpoint, and finding an arbitrary item from finding the globally smallest item.

For example, a PriorityQueue does not maintain a fully sorted array you can inspect at arbitrary indices. It guarantees that peek() returns the highest-priority element—by default, the smallest—and that poll() removes it efficiently. If all you repeatedly need is “the next smallest active item,” that is exactly the guarantee you want.

By contrast, if you must ask, “What is the largest key no greater than $x$?” a hash map cannot help: hashing intentionally discards ordering. A TreeMap maintains order and provides methods such as floorKey(x) and ceilingKey(x) in $O(\log n)$.

---

Arrays and lists: positional access versus edits

Use an array when the size is known or bounded and you need fast positional access. In interview code, primitive arrays are particularly valuable:

int[] frequency = new int[26];
frequency[ch - 'a']++;

This has $O(1)$ access, uses compact primitive storage, and avoids hashing. It is ideal when keys come from a small known range: lowercase letters, digits, or values in a bounded interval.

Use ArrayList<E> when you need a dynamically growing sequence and positional access:

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

values.add(10);       // amortized O(1)
int middle = values.get(0); // O(1)

“Amortized $O(1)$” deserves a precise interpretation. Most appends write into unused space in the backing array. Occasionally the backing array fills, so Java allocates a larger one and copies existing elements, taking $O(n)$ for that individual append. Across many appends, those rare copies average out to $O(1)$ per append.

The costly list operations are insertions and removals away from the end:

values.add(0, 99);  // O(n): shift elements right
values.remove(0);  // O(n): shift elements left

That shift is not automatically a problem. If it happens once, use the clear, simple list operation. If it happens repeatedly in a large loop, redesign.

Read the selected portions of Dev.java’s “Choosing the Right Implementation Between ArrayList and LinkedList.” The article is useful because it separates theoretical operation costs from the practical cost of traversing linked nodes.

Why LinkedList is rarely the answer in Java interview code

A linked list can relink nodes in $O(1)$ time only after you already have the relevant node or its predecessor. But Java’s LinkedList.get(i), add(i, x), and remove(i) first have to traverse nodes to reach index $i$, which is $O(n)$.

This distinction matters:

• In a custom linked-list algorithm, if you hold a ListNode prev, inserting after prev is $O(1)$.
• In java.util.LinkedList, “insert at the middle index” is still $O(n)$, because locating that middle node costs $O(n)$.
• Iterating with for (int i = 0; i < list.size(); i++) list.get(i) is $O(n^2)$ on a LinkedList.

For an ordinary resizable indexed sequence, default to ArrayList. For endpoint-only work, use ArrayDeque, not LinkedList.

---

Hashing: choose it for fast lookup, membership, and counts

A HashMap<K, V> stores a relationship from a key to a value. A HashSet<E> stores only membership. Internally, a set is conceptually similar to a map whose values are irrelevant.

Use a hash map when your scan repeatedly needs a fact associated with a prior value:

• value $\mapsto$ frequency
• value $\mapsto$ first index
• prefix sum $\mapsto$ number of occurrences
• identifier $\mapsto$ record or state

For frequency counting:

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

for (int x : nums) {
    frequency.put(x, frequency.getOrDefault(x, 0) + 1);
}

Each getOrDefault and put is expected $O(1)$, so the complete pass is expected $O(n)$.

For the classic “find two values adding to target” pattern, the map stores information that lets the current value query the past in constant expected time:

Map<Integer, Integer> indexByValue = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
    int needed = target - nums[i];

    if (indexByValue.containsKey(needed)) {
        return new int[] {indexByValue.get(needed), i};
    }

    indexByValue.put(nums[i], i);
}

A concise interview justification is:

“For each number, I need to test whether its complement occurred earlier. A hash map gives expected constant-time lookup and stores the earlier value’s index, so the full scan is expected linear time.”

That statement identifies the operation, the required information, and the total complexity.

“Expected” matters. Hash tables rely on keys dispersing well across buckets; pathological collisions can hurt performance. For ordinary Integer, String, and well-designed custom keys, HashMap and HashSet are the standard interview choice. Also remember these common traps:

• containsKey(key) is expected $O(1)$; containsValue(value) is $O(n)$.
• Iterating a HashMap does not promise sorted or insertion order.
• A mutable object should not be changed in a way that changes its equality or hash code while it is a map key or set element.
• If you need only “seen or not seen,” use HashSet, not a map with dummy values.

The Java documentation’s note on capacity is a useful qualification: although lookups are expected constant time, iteration depends on both stored entries and the table’s capacity.

---

Endpoint processing: use ArrayDeque for stacks and queues

A stack restricts work to one end: last in, first out. A queue restricts it to opposite ends: first in, first out. If that is your algorithm’s access pattern, model it directly with Deque<E> and implement it with ArrayDeque<E>.

Deque<Integer> stack = new ArrayDeque<>();

stack.push(10);      // add at top
int top = stack.peek();
int removed = stack.pop();

Deque<Integer> queue = new ArrayDeque<>();

queue.offer(10);     // add at back
int front = queue.peek();
int removed = queue.poll();

These endpoint operations are amortized $O(1)$. ArrayDeque is a strong default for interview stacks and queues because it is array-backed and avoids the per-node overhead and pointer traversal of LinkedList.

Use the method names consistently:

Role	Add	Inspect without removing	Remove
Stack	push(x)	peek()	pop()
Queue	offer(x)	peek()	poll()

Avoid the legacy Stack class in new interview code. Also note that ArrayDeque does not permit null, which is usually helpful because poll() returning null clearly means the deque was empty.

This choice will recur constantly: breadth-first search uses a queue; matching brackets and next-greater-element problems use a stack; sliding-window maxima later use a deque from both ends.

---

Priority and ordering: do not pay for more order than you need

A PriorityQueue<E> is a heap. It is the right tool when your algorithm repeatedly needs the single best next candidate according to a priority rule.

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

minHeap.offer(7);
minHeap.offer(2);
minHeap.offer(5);

int smallest = minHeap.poll(); // 2

Its core costs are:

• peek(): $O(1)$
• offer(x): $O(\log n)$
• poll(): $O(\log n)$

To make a max-heap of integers:

PriorityQueue<Integer> maxHeap =
        new PriorityQueue<>(Comparator.reverseOrder());

The decision rule is simple:

• Need every insertion followed by access to the minimum or maximum? Use PriorityQueue.
• Need a structure fully sorted for iteration, or need nearest ordered keys such as floor and ceiling? Use TreeMap or TreeSet.
• Need only exact key lookup or membership, not order? Use HashMap or HashSet.

For example, imagine processing jobs by earliest finish time. Sorting all jobs once may be best if all jobs are known upfront. But if jobs arrive incrementally and you repeatedly need the next earliest job, a heap matches the operational need.

Do not use PriorityQueue merely because a problem mentions “largest” or “smallest.” If you need the maximum of a static array once, a linear scan is $O(n)$ and simpler than building a heap. A data structure pays off when its inexpensive operation is repeated.

---

Turn a problem statement into a data-structure sentence

Before you implement, force yourself to complete this template:

“During each iteration, I need to ___; I need ___ ordering or uniqueness; therefore I will use ___, whose ___ operation costs ___; the total is ___.”

Here are examples worth memorizing as reasoning patterns—not as fixed solutions.

Problem shape	Required repeated operation	Appropriate choice
Detect duplicates while scanning	Test membership of current value	HashSet
Count occurrences	Retrieve and update count by value	HashMap
Maintain visited nodes in a traversal	Test and mark visited	HashSet plus ArrayDeque for BFS
Process tasks in arrival order	Add at back, remove at front	ArrayDeque
Repeatedly select least costly available task	Add candidates and remove minimum	PriorityQueue
Store a growing answer and later access by index	Append and indexed reads	ArrayList
Find nearest stored key below or above a value	Ordered predecessor/successor query	TreeMap or TreeSet
Count lowercase English letters	Access a small bounded key range	int[26]

One subtle but important comparison: an int[26] is better than a HashMap<Character, Integer> for lowercase-letter frequency counting because the key domain is fixed and tiny. A map becomes necessary when the keys are sparse, large, unknown in advance, or not naturally convertible to compact indices.

For the next few array and string problems you solve, write the one-sentence justification in a comment before the data-structure declaration. This makes pattern recognition deliberate rather than automatic:

// Need expected O(1) lookup of prior values to avoid pair enumeration.
Map<Integer, Integer> indexByValue = new HashMap<>();

---

Key takeaways

Data-structure selection is an operation-cost decision:

• Use arrays and ArrayList for indexed access; choose primitive arrays when the size or value range is known.
• Use HashSet for expected $O(1)$ membership and HashMap for expected $O(1)$ key-to-value lookup or counting.
• Use ArrayDeque for stacks, queues, and work at both endpoints.
• Use PriorityQueue when repeatedly extracting the current minimum or maximum is the central operation.
• Use TreeMap or TreeSet only when key order, predecessor, successor, or ordered traversal is genuinely required.
• Default to ArrayList over LinkedList for general list work. In Java, a linked list does not make indexed insertion cheap because reaching the target index is itself linear.

Next, you will examine a different hidden cost: recursion. You will estimate recursion depth and auxiliary call-stack usage, then decide when an iterative Java implementation is safer.