ArrayList vs LinkedList: When to Use Which

"ArrayList or LinkedList?" is the single most repeated comparison question in Java interviews — and the textbook answer ("LinkedList for insertions, ArrayList for access") is wrong often enough that giving it uncritically can hurt you. Here is the honest comparison, including the part about CPU caches most tutorials skip.

Verdict at a glance

Bottom line: ArrayList is the right default. LinkedList earns its place only in head/tail-heavy or iterator-removal-heavy workloads.

How each one stores data

ArrayList keeps elements in one contiguous Object[] that grows by ~1.5x when full. Index access is a direct array lookup; inserting in the middle shifts everything after the insertion point. The full mechanics are covered in ArrayList internal working.

LinkedList is a doubly-linked chain of node objects. Each node holds the element plus prev and next references. Nothing ever shifts — inserting means rewiring two links — but nothing is directly addressable either: reaching index i means walking the chain from the head or the tail, whichever is closer.

Both implement the List interface, so they are drop-in replacements for each other at the API level. The behavior under load is where they part ways.

Dimension 1: random access

arrayList.get(500_000) is one bounds check and one array read — O(1) regardless of size. linkedList.get(500_000) on a million-element list walks 500,000 nodes — O(n). ArrayList even implements the RandomAccess marker interface so library code (like Collections.binarySearch) can pick index-based algorithms only when they are cheap.

If your code ever calls get(i) in a loop over a LinkedList, you have accidentally written an O(n²) algorithm. This is one of the most common performance bugs in beginner Java code.

Common mistake: A common mistake beginners make is iterating a LinkedList with for (int i = 0; i < list.size(); i++) list.get(i). Each get re-walks the chain, turning a linear scan into quadratic time. Always use for-each or an iterator on a LinkedList.

Dimension 2: inserts and removals

This is where the textbook oversimplifies. Split it into three cases:

• At the tail: both are effectively O(1). No meaningful difference.
• At the head: LinkedList relinks in O(1); ArrayList shifts every element, O(n). Clear LinkedList win — this is its home turf.
• In the middle by index: ArrayList is O(n) for the shift; LinkedList is O(n) for the traversal plus O(1) for the relink. Same Big-O — and the ArrayList shift is a single System.arraycopy, which modern CPUs execute far faster than chasing n/2 scattered node pointers.

The one middle-of-list case LinkedList genuinely wins: you are already standing at the position with an iterator and call iterator.remove() or listIterator.add(). No traversal needed, O(1) relink, no shifting.

Dimension 3: memory and CPU cache

Per element, ArrayList stores one reference in a compact array (plus up to ~50% spare capacity). LinkedList allocates a whole node object per element: object header, value reference, prev, next. On a typical 64-bit JVM with compressed oops, that is roughly 40 bytes of overhead per element versus about 4–8 bytes for ArrayList.

The bigger effect is invisible in Big-O: cache locality. ArrayList elements sit next to each other, so the CPU prefetches them in cache lines and iteration flies. LinkedList nodes are scattered across the heap; every next is a potential cache miss costing hundreds of cycles. This is why ArrayList wins many benchmarks that complexity analysis says it should lose, and it is also extra pressure on the garbage collector, which has millions of node objects to track.

See it yourself: a runnable comparison

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

public class ListShowdown {
    public static void main(String[] args) {
        int n = 100_000;

        // Round 1: insert at HEAD — LinkedList's best case
        System.out.println("Head inserts:");
        System.out.println("  ArrayList : " + timeHeadInserts(new ArrayList<>(), n));
        System.out.println("  LinkedList: " + timeHeadInserts(new LinkedList<>(), n));

        // Round 2: random access — ArrayList's best case
        List<Integer> al = new ArrayList<>();
        List<Integer> ll = new LinkedList<>();
        for (int i = 0; i < n; i++) { al.add(i); ll.add(i); }

        System.out.println("Sum via get(i):");
        System.out.println("  ArrayList : " + timeGetLoop(al));
        System.out.println("  LinkedList: " + timeGetLoop(ll));
    }

    static String timeHeadInserts(List<Integer> list, int n) {
        long t = System.nanoTime();
        for (int i = 0; i < n; i++) list.add(0, i);
        return (System.nanoTime() - t) / 1_000_000 + " ms";
    }

    static String timeGetLoop(List<Integer> list) {
        long t = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < list.size(); i++) sum += list.get(i);
        return (System.nanoTime() - t) / 1_000_000 + " ms (sum=" + sum + ")";
    }
}

Run it: head inserts favor LinkedList heavily, while the get(i) loop makes LinkedList crawl. Both results follow directly from the storage layouts above. (For rigorous numbers you would use JMH, but the ordering here is robust enough to see the point.)

Using LinkedList as a Deque

LinkedList's second identity: it implements Deque, giving O(1) stack and queue operations at both ends.

import java.util.LinkedList;
import java.util.Deque;

public class DequeDemo {
    public static void main(String[] args) {
        Deque<String> browserHistory = new LinkedList<>();

        browserHistory.push("home");        // stack: push to head
        browserHistory.push("courses");
        browserHistory.push("java");

        System.out.println(browserHistory.pop());   // java  (LIFO)
        System.out.println(browserHistory.peek());  // courses

        browserHistory.addLast("contact");  // queue-style at tail
        System.out.println(browserHistory); // [courses, home, contact]
    }
}

Pro tip: If you only need stack or queue behavior — no index access, no List interface — reach for ArrayDeque instead. It backs onto a circular array, so it gets the O(1) end operations and the cache locality, and it outperforms LinkedList in almost every deque benchmark.

Choose ArrayList if / Choose LinkedList if

Choose ArrayList if:

• You read by index anywhere in your code — even occasionally.
• The workload is build-once, iterate-many (DTO lists, query results, config).
• Memory footprint or GC pressure matters.
• You are unsure. The default should win ties.

Choose LinkedList if:

• You constantly add/remove at the head (and also need the List interface).
• You remove many elements mid-iteration through an iterator.
• You need both List semantics and Deque operations in one object.

For freshers: how to answer this in an interview

Lead with the honest version, not the textbook version: "ArrayList for random access and iteration, LinkedList for head/tail insertion — but in practice ArrayList wins most benchmarks because of cache locality, so I default to ArrayList and reach for ArrayDeque before LinkedList for queues." Then be ready for the follow-ups: why get(i) is O(n) on LinkedList, why middle inserts are O(n) on both, and what RandomAccess signals.

Interview note: Interviewers often follow up with "so when did you last actually use LinkedList?" A grounded answer — iterator-heavy removal, or needing List + Deque together — lands far better than pretending it is a daily tool.

More drills on exactly this pattern are in our Java collections interview questions, and the wider context of where Lists sit among Sets, Maps and Queues is in the Collections Framework map. To practice these trade-offs on real projects with feedback, see the Java Full Stack course.