Detailed explanation
ArrayList and LinkedList are Java implementations of the List interface, so both maintain element order, allow duplicates, and support indexed operations. Their main difference is storage: ArrayList uses a resizable backing array, while LinkedList uses a doubly linked chain of nodes. Each LinkedList node stores an element and references to the previous and next nodes. Choosing between them depends on access patterns, update positions, and memory overhead, not simply whether your code performs more reads or writes.
ArrayList provides O(1) indexed access because it can directly locate an array slot. Adding an element at the end is amortized O(1): most additions fill an available slot, but an occasional resize allocates a larger array and copies existing references, taking O(n). Inserting or removing an element in the middle takes O(n) because later elements must shift. Its compact storage of references usually gives good cache locality during traversal. For object elements, the references are contiguous, not necessarily the objects themselves.
LinkedList provides O(1) insertion and removal at either end because it maintains references to the first and last nodes. However, get(index), add(index, value), and remove(index) generally require traversal, making them O(n) in the worst case. Java traverses from whichever end is closer. An important interview distinction is that modifying links is O(1), but finding the position is not. With a ListIterator already positioned appropriately, insertion or removal can update nearby links without a fresh traversal. LinkedList also typically consumes more memory because every element requires a separate node with extra references.
Prefer ArrayList as the default list, especially for indexed reads and general traversal. LinkedList can suit iterator-based local edits or operations at both ends, although ArrayDeque is usually a better starting choice for a queue or stack when null elements are unnecessary. Neither list is inherently thread-safe. In the supplied example, al.get(0) illustrates constant-time lookup only after an element has been added; on the newly created empty list, it throws IndexOutOfBoundsException. Interviewers look for these qualifications rather than memorised complexity labels.
Key points to remember
- ArrayList uses a dynamic array; LinkedList uses doubly linked nodes.
- Indexed access is O(1) for ArrayList and O(n) for LinkedList.
- ArrayList append is amortized O(1); a resizing append takes O(n).
- LinkedList end operations are O(1), but indexed middle updates generally require O(n) traversal.
- Default to ArrayList for general list use; consider memory overhead and actual access patterns.
Common mistakes candidates make
- Claiming every LinkedList insertion or deletion is O(1), ignoring the cost of locating the position.
- Calling ArrayList append always O(1), without distinguishing amortized cost from resizing cost.
- Running get(0) on a newly created empty list and expecting a value instead of IndexOutOfBoundsException.
Likely follow-up questions
When are middle insertions and deletions O(1) in LinkedList?
They are O(1) when a ListIterator is already appropriately positioned, so no search is needed before changing links. Reaching that position initially may still take O(n).
Why can an indexed loop be slow on LinkedList?
A loop that repeatedly calls get(i) performs a new traversal for each index, resulting in O(n²) total time. Use an iterator or enhanced for-loop for O(n) traversal.
Should LinkedList be the default choice for a queue?
Usually, start with ArrayDeque, which supports efficient operations at both ends without allocating a node per element. Unlike LinkedList, ArrayDeque does not permit null elements.
Interview tip: Compare storage first, explain access and update costs, then recommend ArrayList by default while qualifying LinkedList’s O(1) updates.