What are the time complexities of common operations on ArrayList versus LinkedList, and when would you pick one over the other?
answer
- ArrayList = array: index O(1), middle insert/remove O(n)
- LinkedList = nodes: access O(n), end ops O(1)
- Amortized O(1) append because of rare resize copy
- Cache locality makes ArrayList win in practice
- Default ArrayList; LinkedList for end or iterator edits
basics
~20 sArrayList 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 sArrayList 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
Knows ArrayList get is O(1) and LinkedList get is O(n); can state 'default to ArrayList'.
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.
Brings in cache locality / constant factors to argue ArrayList wins in practice even when Big-O ties, and names ArrayDeque as the better queue.
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
- ArrayList (Java SE 27 & JDK 27)docs.oracle.com
- LinkedList (Java SE 27 & JDK 27)docs.oracle.com
- ArrayDeque (Java SE 27 & JDK 27)docs.oracle.com