Given a real-world scenario, how do you decide between ArrayList and LinkedList — and why is ArrayList almost always the right default?

## The decision framework Choosing a `List` implementation is about matching your **dominant operations** to the structure's strengths. Both implement the same `List` interface, so switching later is usually a one-line change. ### Step 1: Default to ArrayList The vast majority of list usage is: add items (usually at the end), iterate over them, and occasionally fetch by index. `ArrayList` is excellent at all three — O(1) index access, amortized O(1) append, and cache-friendly iteration with low memory. So **start there** and only deviate with a concrete reason. ### Step 2: Identify your dominant operation - **Random access by index** (`list.get(i)` in a hot loop): ArrayList, definitively — it's O(1) vs LinkedList's O(n). - **Plain iteration**: ArrayList — better cache locality means it's faster even at the same Big-O. - **Append at end**: both are fine; ArrayList is amortized O(1). - **Frequent add/remove at the front**: ArrayList front-ops are O(n) (shifting). This is the classic case people cite for LinkedList — but the right answer is usually **ArrayDeque** (array-backed, O(1) at both ends, great locality). - **Remove/insert while iterating** (you hold an `Iterator` at the spot): LinkedList's relink is O(1) here, vs ArrayList's O(n) shift. This is LinkedList's one genuine niche. - **Queue/stack/deque** (add/remove at ends): use **ArrayDeque**, not LinkedList. ### Step 3: Account for memory and cache LinkedList costs ~3x memory (each element is a node with two pointers + object header) and scatters nodes across the heap, so even iteration suffers cache misses. ArrayList is compact and contiguous. This is why LinkedList's theoretical advantages rarely show up in benchmarks — and why ArrayList is the practical default. ### Step 4: Debunk the myth The statement "LinkedList is better for insertions" is misleading. Inserting at an **arbitrary index** requires first **finding** that index — O(1) for ArrayList, O(n) traversal for LinkedList. So both are O(n) for index-based insertion, and ArrayList's contiguous shift usually beats LinkedList's traversal-plus-cache-misses. LinkedList only wins when you skip the search (ends, or an iterator cursor). ## Worked examples - **A list of search results rendered in a UI**: build once, iterate, index occasionally → **ArrayList**. - **A work queue: producers add, consumers poll from the front**: → **ArrayDeque** (not LinkedList). - **Filtering a list in place, removing matched elements during a single pass via Iterator.remove()**: → **LinkedList** has an edge here (O(1) removals), though for small/medium lists ArrayList is often still fine; measure. - **Lookup table accessed by index thousands of times**: → **ArrayList**. ## The honest rule of thumb 1. **Default: ArrayList.** 2. **Need a queue/stack/deque (ends only): ArrayDeque.** 3. **Need O(1) removal while iterating a large list: consider LinkedList, after measuring.** 4. Never choose LinkedList just because of the 'better insertion' myth — and don't micro-optimize without profiling realistic data.