Skip to content
Java collections 6 min read

ArrayList vs LinkedList

Choosing between ArrayList and LinkedList is one of the most common decisions you’ll make when working with Java collections. Both implement the List interface, so they share the same API — but their internal structures are completely different, and those differences have real performance consequences.

The Core Difference

  • ArrayList stores elements in a contiguous Object[] array. Random access is instant, but inserting in the middle requires shifting elements.
  • LinkedList stores elements as a chain of doubly-linked Node objects. Insertion and deletion at any position are fast once you have a reference, but random access requires walking the chain.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class BasicComparison {
    public static void main(String[] args) {
        List<String> arrayList   = new ArrayList<>();
        List<String> linkedList  = new LinkedList<>();

        // Both expose identical List API
        arrayList.add("Java");
        linkedList.add("Java");

        System.out.println(arrayList.get(0));   // Java
        System.out.println(linkedList.get(0));  // Java
    }
}

Output:

Java
Java

Note: Because both implement List, you can switch between them by changing only the constructor — your calling code stays the same.

Internal Structure

ArrayList Internals

ArrayList maintains a backing Object[] elementData array with a default initial capacity of 10. When the array fills up, Java allocates a new array at 1.5× the old size (newCapacity = oldCapacity + (oldCapacity >> 1)) and copies all elements over. This is the “grow” operation — it is O(n) but happens infrequently (amortized O(1) per add).

// Simplified mental model of what ArrayList.add() looks like:
// if (size == elementData.length) grow();
// elementData[size++] = element;

Elements sit side-by-side in memory, so the CPU cache loves them — iterating an ArrayList is extremely cache-friendly.

LinkedList Internals

LinkedList is implemented as a doubly-linked list. Each element is wrapped in a private Node<E> object:

// Simplified Node structure (from JDK source)
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

LinkedList keeps references to both the first and last nodes, making operations at either end O(1). However, accessing element i in the middle requires traversing from whichever end is closer — O(n/2) = O(n).

Note: LinkedList also implements Deque, so it can act as a queue or stack with addFirst(), addLast(), removeFirst(), and removeLast().

Performance Comparison

OperationArrayListLinkedListWhy
get(i) — random accessO(1)O(n)Array index vs node traversal
add(e) — append to endO(1) amortizedO(1)Array append vs last-node link
add(i, e) — insert in middleO(n)O(n)*Shift vs traverse then re-link
remove(i) — remove by indexO(n)O(n)*Shift vs traverse then unlink
contains(e) — linear searchO(n)O(n)Both scan sequentially
Memory per element~4–8 bytes~24–40 bytesObject reference vs Node object
Cache friendlinessExcellentPoorContiguous memory vs scattered nodes

*LinkedList insert/remove is O(1) once you hold the iterator/node. Getting there is still O(n).

Tip: The O(n) middle-insertion looks the same on paper, but ArrayList is often faster in practice for small-to-medium lists because array shifting is a highly optimised memory-copy (System.arraycopy) that benefits from CPU cache, while LinkedList chases pointers scattered across the heap.

Code Examples

Random Access (ArrayList wins)

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

public class RandomAccessDemo {
    public static void main(String[] args) {
        List<Integer> al = new ArrayList<>();
        List<Integer> ll = new LinkedList<>();

        for (int i = 0; i < 100_000; i++) {
            al.add(i);
            ll.add(i);
        }

        long start = System.nanoTime();
        for (int i = 0; i < 100_000; i++) al.get(i);
        long alTime = System.nanoTime() - start;

        start = System.nanoTime();
        for (int i = 0; i < 100_000; i++) ll.get(i);
        long llTime = System.nanoTime() - start;

        System.out.println("ArrayList  get: " + alTime  / 1_000_000 + " ms");
        System.out.println("LinkedList get: " + llTime  / 1_000_000 + " ms");
    }
}

Output (approximate):

ArrayList  get: 1 ms
LinkedList get: 4500 ms

Insert at the Front (LinkedList wins)

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

public class FrontInsertDemo {
    public static void main(String[] args) {
        List<Integer> al = new ArrayList<>();
        List<Integer> ll = new LinkedList<>();

        long start = System.nanoTime();
        for (int i = 0; i < 50_000; i++) al.add(0, i);  // insert at index 0
        long alTime = System.nanoTime() - start;

        start = System.nanoTime();
        for (int i = 0; i < 50_000; i++) ll.add(0, i);  // insert at index 0
        long llTime = System.nanoTime() - start;

        System.out.println("ArrayList  front-insert: " + alTime / 1_000_000 + " ms");
        System.out.println("LinkedList front-insert: " + llTime  / 1_000_000 + " ms");
    }
}

Output (approximate):

ArrayList  front-insert: 280 ms
LinkedList front-insert: 12 ms

Using LinkedList as a Queue

import java.util.LinkedList;
import java.util.Queue;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("first");
        queue.offer("second");
        queue.offer("third");

        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}

Output:

first
second
third

Tip: If you need a queue or deque, ArrayDeque is generally faster than LinkedList for that use case too. Reach for LinkedList as a Deque only when you already need it as a List.

Memory Overhead

Memory matters at scale. For a list of Integer objects:

  • ArrayList: stores object references — roughly 4–8 bytes per element reference, plus the backing array object overhead.
  • LinkedList: each element is wrapped in a Node holding three references (item, next, prev) — roughly 24–40 bytes per node depending on JVM pointer compression.

At 1 million elements, LinkedList can consume several times more memory than ArrayList.

Iterating Both Lists

Both types iterate efficiently when you use a for-each loop or an explicit Iterator, because LinkedList’s iterator moves from node to node without any index-based traversal overhead.

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

public class IterationDemo {
    public static void main(String[] args) {
        List<String> list = new LinkedList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        // Always prefer for-each or iterator over index-based loop for LinkedList
        for (String s : list) {
            System.out.print(s + " ");
        }
    }
}

Output:

A B C

Warning: Never use an index-based for (int i = 0; i < list.size(); i++) loop on a LinkedList — each get(i) call traverses from the head, turning O(n) iteration into O(n²) torture.

Under the Hood

ArrayList Growth Strategy

When an ArrayList grows, the JVM calls Arrays.copyOf(), which delegates to System.arraycopy() — a native method that uses memcpy-style bulk memory operations. This is why even the O(n) resize is fast in absolute terms: it is a single contiguous block copy, not a loop over individual objects.

The JIT compiler can also vectorise tight ArrayList loops using SIMD instructions. LinkedList pointer chasing is much harder to vectorise.

LinkedList Node Allocation

Every add() on a LinkedList allocates a new Node object on the heap. More allocations means more pressure on the garbage collector, more GC pauses, and more fragmented heap memory — all of which hurt throughput in high-volume scenarios.

Sublist and Iterator Invalidation

Both ArrayList and LinkedList use a modCount field to detect structural modifications during iteration. If you modify the list while iterating (outside of the iterator’s own remove() method), a ConcurrentModificationException is thrown immediately — a fail-fast behaviour that catches bugs early.

Quick Decision Guide

You need…Use
Fast random access by indexArrayList
Frequent append to endEither (both O(1))
Frequent insert/delete at front or known positionLinkedList
Queue / Deque semanticsLinkedList or ArrayDeque
Minimum memory footprintArrayList
Iteration-heavy, rarely modifiedArrayList
Thread-safe listNeither — use CopyOnWriteArrayList or Collections.synchronizedList()

Tip: When in doubt, start with ArrayList. It is faster for the majority of real-world workloads, uses less memory, and is friendlier to the JVM’s optimiser. Switch to LinkedList only when profiling proves it helps.

Last updated June 13, 2026
Was this helpful?