ArrayList stores its elements in a plain Java array. When you add an element, it goes into the next slot of that array. When the array runs out of capacity, ArrayList allocates a new array roughly 1.5× the size, copies all existing elements, and discards the old array. This resize is an O(n) operation, but because it happens exponentially less often as the list grows, the amortised cost of each add() call at the end of the list is O(1).
The key performance advantage of an array is cache locality. Array elements are stored in contiguous memory. When the CPU loads one element, the memory controller fetches a whole cache line (typically 64 bytes) of adjacent elements along with it. Iterating an ArrayList is therefore very fast because most elements are already in the L1/L2 cache by the time they are needed. Random access by index is O(1) — a simple offset calculation from the array's base address.
You can pre-size an ArrayList with new ArrayList<>(initialCapacity) when you know roughly how many elements to expect, which avoids mid-growth resizes and improves throughput.
import java.util.ArrayList;
ArrayList<String> list = new ArrayList<>(100); // pre-allocate for 100 elements
list.add("Alice"); // O(1) amortised — appends to end
list.add("Bob");
list.add(0, "Zara"); // O(n) — shifts Alice, Bob one position right
System.out.println(list.get(1)); // O(1) — direct array access → "Alice"
System.out.println(list.size()); // 3
list.remove(0); // O(n) — shifts remaining elements left
System.out.println(list); // [Alice, Bob]
LinkedList stores each element in a separate node object. Each node holds the element value, a reference to the next node, and a reference to the previous node — making it a doubly-linked list. The LinkedList itself holds references only to the first (head) and last (tail) nodes.
Adding to the front or back of a LinkedList is a true O(1) operation — no shifting, no resizing, just link a new node. Removing from the front or back is also O(1) given the head/tail pointers. This is why LinkedList also implements Deque and is sometimes used as a queue or stack.
The weakness is random access and cache misses. Calling get(50) on a LinkedList requires starting at the head (or tail, if 50 is in the second half) and following node references one by one. Each node is a separate heap object at an arbitrary memory address, so every step likely causes a CPU cache miss. For a list of 10 000 elements, this turns a single get() call into hundreds of cache misses — orders of magnitude slower than the equivalent ArrayList.get().
import java.util.LinkedList;
LinkedList<String> list = new LinkedList<>();
list.addFirst("Alice"); // O(1) — update head pointer
list.addLast("Bob"); // O(1) — update tail pointer
list.addFirst("Zara"); // O(1) — update head pointer
System.out.println(list.getFirst()); // O(1) — "Zara"
System.out.println(list.getLast()); // O(1) — "Bob"
System.out.println(list.get(1)); // O(n) — walks to position 1 → "Alice"
list.removeFirst(); // O(1) — detach head node
list.removeLast(); // O(1) — detach tail node
System.out.println(list); // [Alice]
The table below shows the algorithmic complexity of common operations for both implementations. Note that Big-O alone does not tell the full story — constant factors and cache effects matter enormously in practice, which is why ArrayList often outperforms LinkedList even for operations where theory favours linked lists.
| Operation | ArrayList | LinkedList |
|---|
| get(index) | O(1) | O(n) |
| add(element) — end | O(1) amortised | O(1) |
| add(0, element) — front | O(n) | O(1) |
| add(i, element) — middle | O(n) | O(n) ¹ |
| remove(index) — middle | O(n) | O(n) ¹ |
| removeFirst() / removeLast() | O(n) / O(1) | O(1) / O(1) |
| Sequential iteration | Fast (cache hits) | Slow (cache misses) |
| Memory per element | ~4–8 bytes (reference) | ~48 bytes (node object) |
¹ Finding the position takes O(n), but unlinking the node itself is O(1) once found. The total cost is still O(n).
Even for operations where LinkedList has better algorithmic complexity — like insertions at the front — ArrayList often performs better in benchmarks on modern hardware. The reason is the CPU cache. Modern CPUs are 10–100× faster than main memory. When iteration walks an ArrayList, consecutive elements sit next to each other in memory and load together into a 64-byte cache line. When iterating a LinkedList, each node is a separate object scattered across the heap, and every next pointer dereference is likely to miss the cache and stall the CPU waiting for main memory.
Memory overhead is also significant. Each LinkedList node is a separate heap object with an object header (~16 bytes) plus two reference fields for prev and next (~8 bytes each on a 64-bit JVM). For a list of integers, each entry in a LinkedList requires roughly 6× more memory than in an ArrayList. This larger memory footprint makes cache thrashing worse.
The practical guidance from Java performance experts (including the JDK team) is: default to ArrayList. Reach for LinkedList only for a narrow set of use cases, described in the next section.
// Prefer ArrayList for general-purpose use
List<String> list = new ArrayList<>();
// If you need frequent front-insertions or use it as a deque,
// use ArrayDeque instead of LinkedList
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("first");
deque.addLast("last");
deque.pollFirst(); // O(1) — faster than LinkedList due to cache locality
ArrayDeque is backed by a circular resizable array. It provides O(1) insertions and removals at both ends — the same as LinkedList — but with far better cache performance. For queue and deque use cases, prefer ArrayDeque over LinkedList.
LinkedList has a legitimate advantage in one specific scenario: when you hold a ListIterator at a known position and need to perform many consecutive insertions or removals at that cursor position. Because the iterator already has a direct reference to the node, each structural modification is O(1) — no traversal needed. If you are building a text editor that inserts characters at the cursor position millions of times, this matters.
A second legitimate use is as a queue or deque when the list is also being modified by multiple threads using its built-in Deque operations — though in that case LinkedBlockingDeque from java.util.concurrent is usually the better choice.
| Use case | Best choice |
|---|
| General-purpose list | ArrayList |
| Read-heavy, random access | ArrayList |
| Append to end frequently | ArrayList |
| Queue / deque (add/remove at ends) | ArrayDeque |
| Many insertions at iterator cursor | LinkedList with ListIterator |
| Thread-safe queue | LinkedBlockingDeque |