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 only for end/queue ops
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
~40 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) once you hold the node. In practice ArrayList wins almost always: arrays have far better cache locality, no per-element node objects, and less memory overhead. LinkedList only pays off for frequent insert/remove at the front of a large list, or when used as a Deque/queue. For interview purposes: 'default to ArrayList; reach for LinkedList only for queue-like end operations.'
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 the end-only O(1) for LinkedList.
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 can discuss when the linked structure's stable element identity / splicing actually matters.
## 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. Elements sit in contiguous memory. - **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 (typically 1.5x) 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. *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. Arrays store data contiguously, so the CPU cache loads neighbouring elements together — iteration and access are extremely fast. A linked list scatters node objects across 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 dramatically faster in reality. ## 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), 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` only when profiling shows front-end 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)?The O(1) only applies once you already hold the node. Reaching the node at a given index requires walking the chain from an end, which is O(n). The traversal dominates.
saying these in an interview costs you the question
- 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)