ArrayList vs LinkedList

## What a List is In Java, `List` is an interface — a contract that says "an ordered collection you can access by integer position (index)." `ArrayList` and `LinkedList` are two **implementations** of that same contract. They behave identically from the outside (`add`, `get`, `remove`, `size`) but store the data completely differently inside, which is why their speed differs. ## ArrayList: backed by an array An **array** is a single block of memory holding elements one after another, like numbered boxes in a row. `ArrayList` wraps a resizable array. - **Random access — `get(i)` / `set(i)`** is **O(1)** (constant time): the computer computes the memory address directly as `base + i * elementSize` and jumps straight there. No matter how large the list, fetching element 5 or element 5,000,000 costs the same. - **Insert/remove in the middle** is **O(n)** (linear time): to insert at position `i`, every element from `i` onward must be **shifted** one slot to make room (or to close the gap on removal). With a million elements, inserting near the front moves ~a million elements. - **Append at the end** is **amortized O(1)**: usually instant, but when the array fills up, `ArrayList` allocates a bigger array (typically ~1.5x) and copies everything over. That occasional copy is spread ("amortized") over many cheap appends, so the average stays constant. - **Memory**: just the array plus a little slack capacity. No per-element overhead beyond the references themselves. - **Cache locality**: excellent. Because elements sit contiguously in memory, the CPU's cache loads neighbors together, so iterating is very fast in practice. ## LinkedList: a chain of nodes A **node** is a small object holding one value plus references (pointers) to other nodes. Java's `LinkedList` is **doubly linked**: each node points to both the **next** and the **previous** node. The list keeps references to the first and last nodes. - **Random access — `get(i)`** is **O(n)**: there is no formula for "where is element i." You must start at the head (or tail, whichever is closer) and **walk** the chain `i` steps. Element 5,000,000 requires five million hops. - **Insert/remove once you already hold the node** is **O(1)**: you just rewire a few pointers (relink the neighbors). This is its one structural strength — e.g. removing via an `Iterator` during traversal. - **Insert/remove at the ends** is **O(1)**: it has direct references to first and last, which is why it's a natural `Deque`/queue. - **Memory**: high overhead. Every element needs a separate node object, and each node carries **two extra references** (prev + next) plus object header bloat — often ~3x the memory of an `ArrayList` of the same data. - **Cache locality**: poor. Nodes are allocated at scattered heap addresses, so the CPU cache can't prefetch neighbors; even plain iteration is slower than `ArrayList` despite both being O(n). ## The crucial subtlety: insertion in the middle People often say "LinkedList is better for inserting in the middle." The pointer **relink** itself is O(1) — but **finding** the middle position is O(n) for LinkedList (you must traverse to it). For ArrayList, finding is O(1) but the **shift** is O(n). So both are O(n) for an arbitrary-position insert; ArrayList's O(n) is a fast contiguous `System.arraycopy` (memory block move), while LinkedList pays an O(n) traversal plus cache misses. That's why ArrayList usually still wins even at the task LinkedList supposedly excels at — unless you already hold the position (e.g. an iterator). ## Big-O summary | Operation | ArrayList | LinkedList | |---|---|---| | `get(i)` / `set(i)` | O(1) | O(n) | | `add` at end | amortized O(1) | O(1) | | `add`/`remove` at front | O(n) | O(1) | | `add`/`remove` middle (by index) | O(n) (shift) | O(n) (traverse) + O(1) relink | | remove via iterator at cursor | O(n) (shift) | O(1) | | memory per element | low | high (2 pointers/node) | | cache locality | good | poor | ## Why ArrayList is the default For the overwhelming majority of real workloads — build a list, iterate it, look things up by index — ArrayList is faster and leaner. Modern CPUs reward contiguous memory heavily (cache), so even LinkedList's theoretical edges rarely materialize. The standard advice: **default to ArrayList; reach for LinkedList only when you genuinely need a queue/deque with heavy add/remove at both ends, or O(1) removal while iterating.** Even then, `ArrayDeque` is usually a better deque than `LinkedList`.