Walk through the time complexity of get, add-at-end, and remove-from-middle for LinkedList, and explain why middle insertion is not really O(1) in practice.
answer
- get(i) = O(n), walks from nearer end (~n/2)
- Ends = O(1) via first/last pointers
- Relink is O(1) but FINDING the node is O(n)
- Real O(1) insert only via ListIterator
- ArrayList still shifts even when iterating
basics
~20 sget(i) is O(n) because you walk the chain. Adding/removing at the ends is O(1). Removing a known node is O(1), but finding that middle position first costs O(n), so a middle insert is really O(n) overall.
solid answer
~40 sLinkedList's costs depend on whether you already have the node. Accessing by index, get(i), is O(n): the list walks from first or last (whichever is closer), so it is at worst n/2 hops. add(e) appending at the tail, addFirst, addLast, removeFirst, and removeLast are all O(1) because the first/last pointers are right there and you just relink a couple of references. The subtle part is middle insertion: relinking the node is O(1), but you first have to *reach* the position, which is an O(n) traversal. So add(index, e) or remove(index) is O(n) overall — the linked-list 'O(1) insert' advantage only materializes when you already hold the node, typically via a ListIterator. That iterator-driven path is where LinkedList genuinely beats ArrayList, since ArrayList must shift elements on every middle insert.
go deeper
Knows ends are cheap and indexing is slow, even if fuzzy on why middle insert is O(n).
Cleanly separates the O(1) relink from the O(n) search, and cites the ListIterator path as the genuine win.
Quantifies the n/2 traversal, contrasts removeIf vs iterator.remove on both classes, and reasons about the actual cost of an editing-while-iterating loop.
Drives the decision empirically — profiles allocation/cache effects, and notes that even the iterator advantage rarely beats ArrayList in real workloads, guiding the team accordingly.
## Setup: what we are measuring We care about how the cost of an operation grows as the list size *n* grows, expressed in Big-O notation (O(1) = constant, O(n) = linear). LinkedList is a doubly-linked list: separate **node** objects each holding a value plus `prev` and `next` references, with the list keeping `first`, `last`, and `size`. ## get(int index): O(n) There is no array, so there is no formula to jump to position *i*. The list must start at one end and follow references. LinkedList optimizes slightly: it checks whether *i* is in the first or second half and walks from `first` or `last` accordingly, so the worst case is about n/2 hops. n/2 is still O(n) — constant factors drop out of Big-O. The same O(n) applies to `indexOf`, `contains`, and `set(i, e)` (which must first locate index *i*). ## add(e) / addLast / addFirst / removeFirst / removeLast: O(1) The list holds direct `first` and `last` pointers. Appending to the tail means: create a node, point the old `last.next` to it, point the new node's `prev` to the old last, update `last`. That is a fixed number of pointer assignments regardless of size — **O(1)**. Removing from either end is symmetric. This O(1)-at-both-ends behavior is exactly why LinkedList can serve as a Deque/Queue. ## remove / add in the middle: the trap The *relinking itself* is O(1): to delete a node you set `node.prev.next = node.next` and `node.next.prev = node.prev` — a constant number of assignments, **no shifting of other elements**. This is the textbook reason people say 'linked lists insert in O(1).' But `list.add(index, e)` or `list.remove(index)` must first **find** the node at that index, and finding it is the O(n) traversal from above. So the *whole* operation is O(n) + O(1) = **O(n)**. The cheap relink is dominated by the expensive search. ### When the O(1) insert is real The advantage shows up only when you *already* have a reference to the location — practically, when iterating with a `ListIterator`. While iterating you can call `iterator.remove()` or `iterator.add(e)` and pay only O(1), because the iterator already sits on the right node; no fresh traversal is needed. Doing the same middle insert in an ArrayList while iterating still costs O(n) per operation because the array must shift every later element. **This iterator-driven, edit-while-traversing pattern is the one scenario where LinkedList legitimately outperforms ArrayList.** ## Summary table | Operation | LinkedList | ArrayList | |---|---|---| | get(i) | O(n) | O(1) | | add at end | O(1) amortized | O(1) amortized | | addFirst / removeFirst | O(1) | O(n) (shift) | | add/remove by index (middle) | O(n) (find) | O(n) (shift) | | add/remove via ListIterator at cursor | O(1) | O(n) (shift) | ## Key terms - **Relink:** reassigning a node's neighbor references to splice it in or out. - **ListIterator:** a cursor that walks a list and can insert/remove at its current position in O(1) on a LinkedList. - **Amortized O(1):** average cost per append once the occasional resize/grow is spread out. ## Takeaway LinkedList's headline 'O(1) insertion' is only the *relink* cost. By index it is O(n) because of the search; the win is real only when you hold the position via an iterator. For random-index work, ArrayList is better.
- You need to remove every element matching a predicate from a 100k-element list while iterating. Why might LinkedList beat ArrayList here?With a ListIterator, LinkedList removes the current element in O(1) (just relink), so the whole pass is O(n). ArrayList's iterator.remove shifts all following elements each time, making it O(n^2) in the worst case (every removal near the front). In practice ArrayList's removeIf does a single compacting pass that is O(n), so prefer removeIf if you stay on ArrayList.
- Does LinkedList's get(i) ever do better than n hops?Yes. It checks if the index is in the first or second half and traverses from first or last accordingly, so it never does more than about n/2 hops. That is still O(n) asymptotically but halves the constant factor.
saying these in an interview costs you the question
- Claiming add(index, e) is O(1) on a LinkedList — the search makes it O(n)
- Forgetting that ArrayList also shifts when removing via iterator
- Saying iterating a LinkedList and removing is O(n^2) — with ListIterator it is O(n)
- Treating 'O(1) insert' as true for any position rather than a held node