Java Collections Time Complexity for Interviews

Where these figures come from

Every statement below comes from the class documentation in the Java SE 25 Javadoc, the current long-term support release, read on November 5, 2026. Each section links to its class. Java states these in sentences rather than tables, so the wording and its conditions matter, and this page keeps them.

ArrayList

From ArrayList. The add operation "runs in amortized constant time, that is, adding n elements requires O(n) time."

LinkedList

LinkedList states no Big O at all. It says: "All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index." So there is no table here. In an interview, that second sentence is what you can cite: get(i) walks the list, it does not jump.

The Javadoc also gives a reason to avoid it for queues: ArrayDeque "is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue." ArrayList's page adds that its constant factor "is low compared to that for the LinkedList implementation."

HashMap

From HashMap. The condition matters: "constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets."

The same page explains what happens under pressure. When the map passes its load factor, it is rehashed to about twice the buckets, and the default load factor of .75 "offers a good tradeoff between time and space costs." It also warns that "using many keys with the same hashCode() is a sure way to slow down performance of any hash table," and that when keys are Comparable, the class may use their order to help break ties. It gives no Big O for that case, so neither does this page.

HashSet

From HashSet, with the same condition as HashMap.

TreeMap

From TreeMap. Unlike HashMap, this one has no condition: "guaranteed log(n) time cost."

PriorityQueue

From PriorityQueue, which is the clearest of the seven. Note that remove() and remove(Object) are very different.

ArrayDeque

From ArrayDeque. This is the class to use for both stacks and queues, for the reason quoted above.

The choices in code

Each line here is one of the choices above: ArrayDeque for a queue, a bounded PriorityQueue for top k, and HashMap with merge for counts.

import java.util.*;

class CollectionChoices {
    // Fewest steps in an unweighted graph: ArrayDeque as the queue.
    static int fewestSteps(Map<Integer, List<Integer>> graph, int start, int goal) {
        Deque<int[]> queue = new ArrayDeque<>();
        Set<Integer> seen = new HashSet<>(List.of(start));
        queue.add(new int[] {start, 0});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            if (cur[0] == goal) return cur[1];
            for (int next : graph.getOrDefault(cur[0], List.of())) {
                if (seen.add(next)) queue.add(new int[] {next, cur[1] + 1});
            }
        }
        return -1;
    }

    // The k largest values: a min-heap holding only k items, O(n log k).
    static List<Integer> topK(int[] values, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int v : values) {
            heap.offer(v);
            if (heap.size() > k) heap.poll();   // evict the smallest
        }
        return new ArrayList<>(heap);
    }

    // Counting with a HashMap, then reading in key order with a TreeMap.
    static SortedMap<String, Integer> sortedCounts(List<String> words) {
        Map<String, Integer> counts = new HashMap<>();
        for (String w : words) counts.merge(w, 1, Integer::sum);
        return new TreeMap<>(counts);           // n*log(n) to build
    }
}

How to say it out loud

Saying "assuming the hash disperses well" is the Java version of saying "on average," and it is the condition an interviewer is listening for. You can practice it in a coding mock interview, and the Big O cheat sheet covers the structures in general.

What the docs do not state

These have no figure in the class documentation, so they have no row here:

• LinkedList: no Big O for any operation, including addFirst and removeFirst.
• HashMap: no figure for remove or containsKey, since "basic operations" names only get and put, and no worst case.
• TreeMap: no figure for firstKey, floorKey, ceilingKey and the other navigation methods.
• ArrayList: the sentence on add does not separate add(E) from add(int, E), so neither does the table.