ArrayList versus LinkedList

Data Structures

`ArrayList<E>` — Resizable Array

Internally, an ArrayList stores elements in a contiguous array. When the array fills up, a new, larger array is allocated and all existing elements are copied across. The growth policy typically doubles the capacity, giving amortised $O(1)$ insertion at the end.

Access to any element by index is direct array indexing — $O(1)$ .

Insertion or removal from the middle requires shifting all elements after the insertion/deletion point — $O(n)$ .

Cache performance is excellent because elements are packed contiguously in memory.

`LinkedList<E>` — Doubly-Linked Nodes

Internally, a LinkedList stores elements in node objects, each containing an element reference, a prev pointer, and a next pointer. The list also maintains references to the head and tail nodes, plus a size counter.

Access to a specific index is sequential — get(i) must walk from whichever end is closer, following next (or prev) pointers $i$ times. This is $O(n)$ .

Insertion or removal at a known position — specifically, once you have a reference to the target node (e.g., via an Iterator or ListIterator) — is $O(1)$ : you just rewire the prev/next pointers.

Cache performance is poor because nodes are scattered across the heap with no spatial locality.

Complexity Comparison

Operation	`ArrayList`	`LinkedList`
`get(i)`	$O(1)$	$O(n)$
`set(i, element)`	$O(1)$	$O(n)$ (must find the node first)
`add(element)` at end	$O(1)$ amortised	$O(1)$
`add(i, element)`	$O(n)$ (shift elements)	$O(n)$ (find the node first, then $O(1)$ to insert)
`add(i, element)` via `ListIterator`	$O(n)$ (still must shift)	$O(1)$ — the iterator already points at the node
`remove(i)`	$O(n)$	$O(n)$ (find node) or $O(1)$ via `Iterator.remove()`
`contains(element)`	$O(n)$	$O(n)$
Memory per element	Reference only (packed array)	Reference + 2 pointers + node object overhead
Cache locality	Excellent (contiguous)	Poor (scattered nodes)

The key insight: LinkedList’s advertised $O(1)$ insertion/removal requires already having a reference to the node. If you are working from an index, you pay $O(n)$ to find it. If you are traversing with an iterator and want to insert or remove at the current position, the iterator has the node reference and the operation is truly $O(1)$ .

Cache Locality

Modern CPUs depend heavily on caches. Accessing adjacent memory locations (as ArrayList does) is vastly faster than chasing pointers through scattered heap memory (as LinkedList does). A sequential scan of an ArrayList can be 10–50× faster than the same logical scan of a LinkedList, even though both are theoretically $O(n)$ .

This means ArrayList often outperforms LinkedList even for workloads that theoretically favour LinkedList — like insertion in the middle at small-to-medium sizes — because the constant factor of array copying is smaller than the pointer-chasing overhead.

`LinkedList` as a Deque

LinkedList implements both List and Deque, so it can be used as a double-ended queue:

Deque<String> deque = new LinkedList<>();
deque.addFirst("alpha");
deque.addLast("omega");
String first = deque.removeFirst();
String last = deque.removeLast();

For pure queue/deque use, however, ArrayDeque is generally preferred over LinkedList — it avoids node allocation overhead and benefits from cache locality.

When to Choose Which

Choose ArrayList when:

Random access by index is common
Elements are mostly appended at the end
Iteration is the predominant operation
You want predictable, low memory overhead

Choose LinkedList when:

You need frequent insertion/removal at arbitrary positions found during iteration (e.g., implementing an LRU cache manually, or a music playlist where items are inserted mid-list while traversing)
You are implementing a data structure where ListIterator.add()/remove() at the cursor is the natural pattern
You need to poll from both ends and also need positional access (though ArrayDeque + a separate index might be cleaner)

Rule of thumb: default to ArrayList. The case for LinkedList is narrower than many assume, largely because $O(n)$ array shifting with cache-friendly memory often beats $O(n)$ pointer-chasing to find the insertion point.

Tripos Advice

Be prepared to justify your choice based on the operations the scenario requires:

Random reads favour ArrayList
Frequent mid-list insertions during traversal with a list iterator favour LinkedList
FIFO queues work with either (ArrayDeque is actually preferred to both for this)
Be explicit about the role of cache locality and constant factors — they are legitimate design considerations