skip to content

Performance & Selection

The complexity profiles of each collection, the capacity and load-factor knobs, and how to pick the right structure for a workload. Interviewers phrase it as a scenario: which collection would you use, and why.

part ofJavaread it →
on this pageshow

explore

questions

15

What are the time complexities of common operations on ArrayList versus LinkedList, and when would you pick one over the other?

level: juniorimportance: must knowfreq 85%

answer

  1. ArrayList = array: index O(1), middle insert/remove O(n)
  2. LinkedList = nodes: access O(n), end ops O(1)
  3. Amortized O(1) append because of rare resize copy
  4. Cache locality makes ArrayList win in practice
  5. Default ArrayList; LinkedList for end or iterator edits

basics

~20 s

ArrayList gives fast index access (O(1)) but slow inserts/removes in the middle (O(n)). LinkedList is slow to reach an element by index (O(n)) but fast at adding/removing at the ends (O(1)). Use ArrayList by default.

solid answer

~50 s

ArrayList is backed by a resizable array: get/set by index are O(1), but inserting or removing anywhere except the end shifts elements, so it is O(n) (amortized O(1) at the end, with occasional resize copies). LinkedList is a doubly-linked list: get(i) must walk from an end, so it is O(n), but adding/removing at the head or tail is O(1), because the list keeps references to both ends. In practice ArrayList usually wins: its constant factor is low, its reference array has better cache locality than a chain of nodes, and it needs no per-element node objects. LinkedList pays off mainly for frequent insert/remove at the front of a large list, for edits through a ListIterator already in position, or when used as a Deque/queue. For interview purposes: 'default to ArrayList; reach for LinkedList mainly for end operations or edits through a positioned iterator.'

go deeper

for a junior

Knows ArrayList get is O(1) and LinkedList get is O(n); can state 'default to ArrayList'.

for a middle

Explains the amortized resize for append, why middle insert is O(n) for ArrayList, and LinkedList's O(1) at the ends and at a positioned iterator.

for a senior

Brings in cache locality / constant factors to argue ArrayList wins in practice even when Big-O ties, and names ArrayDeque as the better queue.

for a principal

Frames the choice around real workload profiling and memory overhead, and knows java.util.LinkedList never exposes its nodes, so textbook O(1) splicing is not on offer.

## What these collections are Both `ArrayList` and `LinkedList` implement Java's `List` interface — an ordered collection you can index by position. They differ entirely in their **internal data structure**, and that structure determines the cost (the **Big-O**) of each operation. **Big-O** is a way to describe how the cost of an operation grows as the collection size `n` grows. `O(1)` means *constant time* (the same regardless of size). `O(n)` means *linear* (cost grows in proportion to size). `O(log n)` means it grows very slowly (doubling `n` adds only one more step). ## ArrayList — a resizable array Internally an `ArrayList` holds a plain Java array (`Object[]`) plus a `size` counter. The array's **references** sit in contiguous memory; the objects they point to live elsewhere on the heap. - **get(i) / set(i, v): O(1)** — the array address plus an offset gives the element directly, no searching. - **add(v) at the end: amortized O(1)** — usually it just writes into the next slot. When the array is full it allocates a bigger array (1.5x in OpenJDK; the Javadoc specifies only amortized constant time) and copies everything over — that single copy is O(n), but because it happens rarely, the *average* (amortized) cost stays O(1). - **add(i, v) / remove(i) in the middle: O(n)** — every element after position `i` must shift one slot to make room or close the gap. - **contains(v) / indexOf(v): O(n)** — a linear scan, because the list is not sorted/indexed by value. - **Since Java 21:** `getFirst`, `getLast` and `removeLast` are O(1) and `addLast` is amortized O(1), but `addFirst` and `removeFirst` are O(n), because they shift every element. *Amortized* means averaged over many operations: most adds are cheap, the rare resize is expensive, but spread out the cost per add is constant. ## LinkedList — a doubly-linked list Internally a `LinkedList` is a chain of node objects; each node holds the value plus pointers to the previous and next node. Java's `LinkedList` keeps references to both the first and last node. - **get(i) / set(i): O(n)** — there is no random access; to reach index `i` it must walk node-by-node from the nearest end. (It optimizes by starting from whichever end is closer, but that is still O(n).) - **addFirst / addLast / removeFirst / removeLast: O(1)** — just re-wire a couple of pointers at a known end. - **add/remove in the middle *given an iterator already positioned there*: O(1)** — but *finding* that position is O(n), so `add(i, v)` by index is overall O(n). - **contains(v): O(n)** — linear scan. ## Why ArrayList usually wins in practice Big-O hides constant factors. An array stores its references contiguously, so the CPU cache loads neighbouring slots together. A linked list adds a node object per element, which may sit anywhere on the heap, so each hop is a potential cache miss, and every element carries the memory overhead of a node object with two pointers. The result: even where both are 'O(n)', ArrayList iteration is typically much faster in practice. ## When LinkedList earns its place When you repeatedly add or remove at the **front** of a large list (an ArrayList front-insert is O(n) because everything shifts), when you insert or remove through a `ListIterator` already in position (an ArrayList shifts the tail each time), or when you use it purely as a **queue/deque** (`Queue`/`Deque` interfaces, via `offer`/`poll`/`push`/`pop`) where you only touch the ends. Even then, `ArrayDeque` is usually the better queue/stack choice. ## The rule of thumb Default to `ArrayList`. Reach for `LinkedList` when profiling shows front-end or positioned-iterator insert/remove dominance, or you genuinely need a doubly-linked deque.

  • Why is appending to an ArrayList called 'amortized' O(1) rather than just O(1)?
    Most appends write into a free slot in O(1), but when the backing array fills, a new larger array is allocated and all elements copied (O(n)). Averaged across many appends, that rare copy adds only constant cost per append, hence amortized O(1).
  • If LinkedList add/remove is O(1) at a node, why is add(int index, E e) O(n)?
    LinkedList never hands out its nodes, so away from the ends the O(1) needs a ListIterator already in position. add(int, E) with an index inside the list must first reach the node by walking from the nearer end, which is O(n), and that traversal dominates.

  • Claiming LinkedList is faster for inserts in general (the traversal to the position is O(n))
  • Saying ArrayList insert is O(1) everywhere (only the end is amortized O(1); middle is O(n))
  • Ignoring cache locality and concluding LinkedList beats ArrayList from Big-O alone
  • Thinking get(i) on LinkedList is O(1)

List.getFirst, addFirst and other sequenced methods
Java 21

Assumes JDK 27. The costs are the same at JDK 25; getFirst, addFirst and the other sequenced methods on List arrived in Java 21. The 1.5x growth factor is OpenJDK's implementation, not part of the ArrayList specification.

context

open as a page

What questions do you ask yourself to decide between a List, a Set, and a Map for a given task?

level: juniorimportance: must knowfreq 80%

basics

~20 s

Use a List when you need ordered items and duplicates are fine. Use a Set when you need unique items only. Use a Map when you look things up by a key. Pick based on whether you have keys, need uniqueness, or care about order.

open as a page

What is the average and worst-case time complexity of HashMap get and put, and what makes the average case constant?

level: middleimportance: must knowfreq 80%

basics

~20 s

HashMap get and put are O(1) on average because hashes spread keys across buckets. Collisions degrade them to O(n), or O(log n) in a tree bin (since Java 8) when keys have distinct hashes or are Comparable.

open as a page

When would you choose ArrayList over LinkedList, and when (if ever) the reverse?

level: middleimportance: must knowfreq 78%

basics

~20 s

Use ArrayList almost always: it's a resizable array, fast for indexing and iteration, and cache-friendly. LinkedList mainly helps if you add/remove a lot at the very front or use it as a queue/deque — and even then ArrayDeque is usually better.

open as a page

How do you choose among HashMap, LinkedHashMap, and TreeMap (and the equivalent Set variants)?

level: middleimportance: must knowfreq 70%

basics

~20 s

HashMap is the default: fast, no ordering. LinkedHashMap keeps insertion order (or access order, for LRU caches). TreeMap keeps keys sorted and lets you do range queries, but it's a bit slower. Same idea for HashSet / LinkedHashSet / TreeSet.

open as a page

Why and how would you set the initial capacity of an ArrayList or HashMap when you know how many elements you will add?

level: juniorimportance: should knowfreq 55%

basics

~20 s

ArrayList and HashMap grow by allocating a bigger array and moving everything over. With a known size, presize once: new ArrayList<>(1000) takes the count directly, while a HashMap needs HashMap.newHashMap(1000) (Java 19+) or capacity count / 0.75 + 1.

open as a page

What are the time complexities of TreeMap operations, and why does it differ from HashMap?

level: middleimportance: should knowfreq 62%

basics

~10 s

TreeMap keeps keys sorted using a balanced tree, so get, put, remove, and containsKey are O(log n) — slower than HashMap's average O(1). In return you get ordered keys and fast range queries.

open as a page

How does ArrayList grow its backing array, and how does that differ from HashMap's growth and from other list types?

level: middleimportance: should knowfreq 38%

basics

~20 s

When an ArrayList fills up, it makes a new array about 1.5x bigger and copies the elements over with no load factor involved. HashMap instead doubles its array and re-buckets every entry. LinkedList never resizes because it has no backing array.

open as a page

What is the load factor in a HashMap, and what is the trade-off when you increase or decrease it?

level: middleimportance: should knowfreq 48%

basics

~20 s

The load factor is how full the bucket array is allowed to get (default 0.75) before the map grows. A higher load factor uses less memory but causes more collisions (slower lookups); a lower one speeds lookups but wastes memory.

open as a page

Given a workload, how do you use Big-O complexity to choose between ArrayList, LinkedList, HashMap, and TreeMap?

level: seniorimportance: should knowfreq 58%

basics

~20 s

Match the structure to the operations you do most. Index access or iteration → ArrayList. Key lookups, order not needed → HashMap. Sorted keys or range queries → TreeMap. End-only queue ops → ArrayDeque (rarely LinkedList).

open as a page

What actually happens when a HashMap resizes, and why is repeated resizing expensive?

level: seniorimportance: should knowfreq 42%

basics

~20 s

A HashMap that gets too full allocates a bucket array of double the size and moves every entry into it, recomputing its bucket. That's O(n) work plus a big allocation, so repeating it wastes time and creates garbage.

open as a page

When you need a thread-safe collection, what are your options and how do you choose among them?

level: seniorimportance: should knowfreq 58%

basics

~20 s

For a shared map, use ConcurrentHashMap, not a synchronized HashMap. For a shared queue, use one of the concurrent queues like ConcurrentLinkedQueue or a blocking queue. Avoid the old Vector/Hashtable. Match the tool to whether you need blocking, ordering, or just safe shared access.

open as a page

Beyond Big-O, what cost factors do you weigh when picking a collection implementation at scale?

level: principalimportance: should knowfreq 40%

basics

~20 s

Big-O is just the start. Also weigh memory overhead per element, cache friendliness, resizing/rehashing costs, what you expose in your API (the interface, not the class), immutability, null handling, and how the choice behaves under concurrency and garbage collection.

open as a page

When presizing collections from an existing collection or stream, what subtle capacity pitfalls should you watch for?

level: seniorimportance: nice to knowfreq 30%

basics

~20 s

The classic trap is new HashMap<>(n) with a raw count: n rounds up to a power of two, and for about half of all n the map resizes before n entries fit. Two-argument Collectors.toMap never presizes. HashMap(Map) is safe.

open as a page

What is the difference between amortized, average, and worst-case complexity, using Java collections as examples?

level: principalimportance: nice to knowfreq 40%

basics

~20 s

Amortized cost averages an expensive-but-rare operation over many cheap ones (ArrayList append). Average-case is the expected cost over typical inputs (HashMap get). Worst-case is the most expensive single operation that can happen (a HashMap lookup when colliding keys have no order).

open as a page