beginner~4h

List Internals: ArrayList, LinkedList, and Their Relatives

How ArrayList actually grows its backing array, why that growth is amortized O(1) rather than O(n), and when LinkedList, Vector, Stack, or CopyOnWriteArrayList genuinely earn their keep instead.

Learning objectives

Explain ArrayList's backing-array growth strategy and why resizing is amortized O(1) rather than O(n) per insertion
State the real time complexity of get, add, add-at-index, and remove for both ArrayList and LinkedList
Explain why LinkedList rarely wins the trade-off against ArrayList in practice despite O(1) head insertion
Describe how Vector and Stack differ from ArrayList and why they're considered legacy
Explain how CopyOnWriteArrayList achieves thread safety and why it fits read-heavy, write-rare workloads specifically

Imagine you run a small parking lot with exactly 10 marked spaces, laid out in a single contiguous row. Cars park in order, and because the spaces are contiguous and numbered, finding "the car in space 7" is instant — you just walk to spot 7. That's the entire appeal of a contiguous array: direct, O(1) access by index, because the address of slot i is just the base address plus i times the slot size, a single arithmetic calculation with no searching involved.

The trouble starts when the 11th car shows up and there's no more pavement. You have two bad options and one good one. Bad option one: refuse the car — but a resizable list can't just refuse to grow. Bad option two: repaint new lines one space at a time every time a new car arrives, which means repainting (re-copying) the entire lot on almost every single arrival, an expensive operation repeated constantly. The good option, and the one ArrayList actually uses, is to buy the much bigger empty lot next door whenever you run out, move every car once in a single pass, and then have plenty of room for a long stretch of future arrivals before you need to move again.

This is exactly ArrayList's growth strategy: when the backing array is full, it allocates a new array roughly 1.5 times the old capacity (the exact factor is an internal implementation detail that has shifted slightly across JDK versions, but 1.5x is the long-standing rule of thumb), copies every existing element into it with Arrays.copyOf, and only then inserts the new element. That single copy is an O(n) operation — but it happens rarely, and each time it happens, the list has bought itself enough headroom that it won't need to do it again for a long while. Spread that occasional O(n) copy cost over the many O(1) insertions that happen between resizes, and the average cost per insertion comes out to O(1). This is called amortized constant time, and it is one of the most important ideas in this entire topic: a single operation can occasionally be expensive, while the structure as a whole is still cheap on average.

LinkedList takes an entirely different approach: instead of one contiguous block, every element lives in its own node carrying a reference to the next node and the previous node, scattered wherever the JVM's heap allocator happens to put them. There's no "array" to resize, ever — growing a LinkedList means allocating one new node and splicing in two pointer updates, genuinely O(1) with no amortization needed, no matter how large the list gets. The cost shows up elsewhere, as the next section works out in detail.

ArrayList is backed by an Object[] field named elementData. A default-constructed ArrayList doesn't allocate a 10-element array immediately — it starts with a shared empty array and only allocates a real backing array of capacity 10 on the first add() call, a small optimization that avoids wasting memory on lists that turn out to be empty. From there, every time size() would exceed the backing array's length, grow() computes a new capacity of roughly oldCapacity + (oldCapacity >> 1) — old capacity plus half of it, i.e. 1.5x — allocates a new array of that size, and copies every element across with Arrays.copyOf, an O(n) operation in the array's current size.

Here is the complexity table that matters in practice:

Operation	ArrayList	LinkedList
`get(index)`	O(1) — direct address arithmetic	O(n) — must walk from head or tail
`add(element)` (append at end)	O(1) amortized	O(1)
`add(index, element)` (middle)	O(n) — must shift every element after index	O(n) — must walk to the index first, splice is O(1)
`remove(index)`	O(n) — must shift every element after index left	O(n) — walk to index, then O(1) splice
`addFirst` / `removeFirst`	O(n) — shifts the entire array	O(1) — just relink the head
Memory per element	Tight — one array slot	Loose — object header + two pointers + payload per node

The "LinkedList wins at the head" row is the one most people remember from a textbook, and it's the one that misleads people in practice: real-world list usage is overwhelmingly dominated by random-access reads (get(i)) and appends at the end, both of which ArrayList wins decisively, and both of which are vastly more common in typical code than repeated head insertion. LinkedList's O(n) get() is a serious cost precisely because random access is so common — iterating a LinkedList by index in a loop (for (int i = 0; i < list.size(); i++) list.get(i)) is a classic, easy-to-write, accidentally-quadratic bug, since each get(i) call walks from the nearer end all over again.

There's also a memory-density argument that compounds the problem: each LinkedList node is a separate heap object carrying a full object header plus two reference fields, scattered across memory in whatever order the allocator happened to place them — which is hostile to CPU cache behavior. ArrayList's contiguous backing array, by contrast, is exactly the access pattern CPU prefetchers are built to exploit. In practice, ArrayList outperforms LinkedList on nearly every realistic workload, including many workloads that look on paper like they should favor LinkedList. This is why ArrayList is the default list choice in nearly all production Java code, and LinkedList shows up mainly as a teaching tool for understanding node-based structures or as the backing structure inside Deque implementations where its genuine strength — O(1) insertion and removal at both ends — is exactly what's needed.

💻 Code example

package collections.lists;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Demonstrates ArrayList's amortized growth (observing capacity jumps
 * indirectly via timing) and the real cost difference between indexed
 * access on ArrayList vs. LinkedList.
 */
public class ListGrowthAndAccessCost {

    public static void main(String[] args) {
        // --- Amortized growth: most adds are cheap, occasional resizes are not ---
        List<Integer> growing = new ArrayList<>();
        long start = System.nanoTime();
        for (int i = 0; i < 1_000_000; i++) {
            growing.add(i); // O(1) amortized: a handful of O(n) copies hidden inside
        }
        long elapsedMs = (System.nanoTime() - start) / 1_000_000;
        System.out.println("1,000,000 ArrayList appends took ~" + elapsedMs + "ms");

        // --- Random access cost: O(1) for ArrayList, O(n) for LinkedList ---
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 50_000; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        long t1 = System.nanoTime();
        for (int i = 0; i < arrayList.size(); i++) {
            arrayList.get(i); // direct index arithmetic every time
        }
        long arrayListMs = (System.nanoTime() - t1) / 1_000_000;

        long t2 = System.nanoTime();
        for (int i = 0; i < linkedList.size(); i++) {
            linkedList.get(i); // walks from head or tail every single call
        }
        long linkedListMs = (System.nanoTime() - t2) / 1_000_000;

        System.out.println("Indexed walk over 50,000 elements:");
        System.out.println("  ArrayList:  ~" + arrayListMs + "ms");
        System.out.println("  LinkedList: ~" + linkedListMs + "ms (dramatically slower)");

        // The correct way to walk a LinkedList is via its iterator, not by index:
        long t3 = System.nanoTime();
        for (Integer value : linkedList) {
            // uses the internal node pointer directly, O(1) per step, O(n) total
        }
        long linkedIterMs = (System.nanoTime() - t3) / 1_000_000;
        System.out.println("  LinkedList via iterator: ~" + linkedIterMs + "ms (back to O(n) total)");
    }
}

Three other List implementations round out the family, and each exists for a reason that's easy to misjudge.

Vector is functionally almost identical to ArrayList — contiguous backing array, index-based access — with one crucial difference: every method is synchronized. That sounds like a free safety upgrade until you notice what it actually buys you: thread-safety for individual operations, but not thread-correctness for compound operations. A check-then-act sequence like "if the vector doesn't contain this element, add it" is still a race condition on a Vector, because the check and the act are two separate synchronized calls with a window between them where another thread can interleave. Meanwhile, every single-threaded program using a Vector pays a real locking cost on every add() and get() for a safety guarantee it never needed. This combination — a locking cost with a correctness guarantee too weak to rely on for anything beyond single-operation atomicity — is exactly why Vector is considered legacy: ArrayList plus explicit synchronization (or a proper concurrent collection) when you actually need thread safety is the modern answer.

Stack extends Vector directly, inheriting all of Vector's baggage, and adds push, pop, and peek. The inheritance choice is widely considered a historical mistake: because Stack is a Vector, every list-style method (get(index), add(index, element), remove(index)) is still publicly available, which means nothing stops code from reaching into the "stack" and inserting an element in the middle, silently breaking the LIFO discipline the class name promises. Modern code that needs a stack should use Deque<E> (typically backed by ArrayDeque) and call push/pop/peek on that instead — it gives the same LIFO operations with none of Vector's inherited surface area or synchronization cost.

CopyOnWriteArrayList is the one implementation in this family actually worth reaching for in concurrent code, but only for a specific access pattern: reads vastly outnumber writes. Every mutating operation — add, remove, set — makes a brand-new copy of the entire backing array, mutates the copy, and atomically swaps the reference, leaving any iterator already in progress on the old array completely undisturbed. The payoff is that reads need no locking at all: an iterator just walks the array snapshot it grabbed when it started, immune to ConcurrentModificationException by construction, since the array it's reading never changes underneath it. The cost is that every single write is O(n), because it copies the entire list regardless of how small the actual change is. This makes CopyOnWriteArrayList an excellent fit for things like a list of event listeners — registered rarely, iterated constantly, by many threads, with no tolerance for locking the read path — and a poor fit for anything with frequent writes, where the repeated full-array copies turn into real, measurable overhead.

💻 Code example

package collections.lists;

import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

/**
 * Shows CopyOnWriteArrayList's key guarantee: an iterator started before a
 * concurrent write keeps seeing the old snapshot, with zero
 * ConcurrentModificationException risk -- unlike a plain ArrayList.
 */
public class CopyOnWriteDemo {

    public static void main(String[] args) throws InterruptedException {
        List<String> listeners = new CopyOnWriteArrayList<>();
        listeners.add("audit-logger");
        listeners.add("metrics-recorder");

        Thread notifier = new Thread(() -> {
            // Iterating is safe even if another thread mutates the list
            // mid-iteration -- it walks the array snapshot taken at
            // iterator-creation time, not the live backing array.
            for (String listener : listeners) {
                System.out.println("Notifying: " + listener);
                try {
                    Thread.sleep(50); // simulate slow notification work
                } catch (InterruptedException ignored) {}
            }
        });

        notifier.start();
        Thread.sleep(10); // let the iteration begin first

        // A write arriving mid-iteration: this does NOT throw
        // ConcurrentModificationException, and the in-progress iterator
        // simply never sees "audit-trail-v2" -- it already has its own copy.
        listeners.add("audit-trail-v2");
        System.out.println("Registered a new listener mid-notification");

        notifier.join();
        System.out.println("Final listener count (seen by new iteration): " + listeners.size());
    }
}

Q: Why is ArrayList's add() called "amortized O(1)" rather than plain O(1)?

A: Most calls to add() just write into free space, genuinely O(1). Occasionally, when the backing array is full, add() triggers a resize: allocate a new array at roughly 1.5x capacity and copy every element, an O(n) operation. Spread that occasional O(n) cost over the many cheap insertions between resizes, and the average cost per call comes out to O(1) — that average is what "amortized" means.

Q: Why does ArrayList usually outperform LinkedList even for workloads that look like they should favor LinkedList?

A: Real workloads are dominated by random-access reads and end-appends, both O(1) for ArrayList and either O(n) (random access) or just O(1) but cache-hostile (appends) for LinkedList. LinkedList's scattered, per-node heap allocations also fight CPU cache prefetching, while ArrayList's contiguous array is exactly what prefetchers are optimized for.

Q: What's wrong with Vector and Stack as "safe" or "LIFO" choices?

A: Vector synchronizes every individual method, which pays a locking cost on every call in the common single-threaded case while still not guaranteeing correctness for compound operations like check-then-act. Stack extends Vector, inheriting all of its baggage plus every list-style method (get(index), add(index, ...)), which means nothing enforces the LIFO discipline the class name implies.

Q: When does CopyOnWriteArrayList actually make sense?

A: When reads vastly outnumber writes — e.g., a list of event listeners registered rarely but iterated constantly. Every write copies the entire backing array (O(n) per write), but reads need zero locking and are immune to ConcurrentModificationException by construction, since an in-progress iterator is walking an immutable snapshot that a concurrent write can never touch.

Want a visual for this concept?

Generate a diagram tailored to “List Internals: ArrayList, LinkedList, and Their Relatives” — the AI picks whichever visual (flowchart, comparison, sequence, etc.) best fits.

Practice quiz

Next Step

Continue to Set Implementations: Uniqueness Without the Repetition →← Back to all Java Collections Framework chapters