Java ArrayList vs LinkedList: Performance and When to Use

Introduction

ArrayList and LinkedList both implement List, so a program can use either one with the same method calls - and get very different speed and memory use. This tutorial compares the two. It covers, in this order, how each class stores its elements, what each list operation costs as a result, a timing program that measures eight operations on both lists, the memory each list needs per element, why ArrayDeque is the better choice for a queue, and a short guide for choosing between them. The examples run on JDK 25.

(Note - This tutorial builds on Java Collections Framework: Overview and HierarchyClick to read tutorial: Java Collections Framework: Overview and Hierarchy, which introduces the List interface.)

How ArrayList stores its elements

An ArrayList keeps its elements in an ordinary array, plus a count of how many slots of it are used. Two numbers therefore describe it: its size, the number of elements, and its capacity, the length of the array behind it. How an ArrayList stores its elements - an array of 10 slots, of which the first 7 hold elements, so the size is 7 and the capacity is 10; get(i) reads slot i directly; when an element is added to a full array, a new array one and a half times as long is created and the elements are copied over
  • Element i is in slot i, so get(i) and set(i, e) go straight to it, however long the list is.
  • add(e) puts the element into the next free slot. When the array is full, the list creates a new array about one and a half times as long, copies all elements into it, and continues there. This happens rarely, so adding at the end is still fast on average.
  • Adding or removing anywhere else shifts every element after that position by one slot, to open or close the gap.
The array is a private field, but with the JVM option --add-opens java.base/java.util=ALL-UNNAMED a program can look at it through reflection. This one adds 50 elements and prints the capacity each time it changes:
ArrayListGrowth.java
//ArrayListGrowth.java
import java.lang.reflect.Field;
import java.util.ArrayList;

public class ArrayListGrowth {
  public static void main(String[] args) throws Exception {
    Field elementData = ArrayList.class.getDeclaredField("elementData");
    elementData.setAccessible(true);   // needs --add-opens java.base/java.util=ALL-UNNAMED

    ArrayList<Integer> list = new ArrayList<>();
    int capacity = ((Object[]) elementData.get(list)).length;
    System.out.println("empty list: size 0, capacity " + capacity);
    for (int i = 1; i <= 50; i++) {
      list.add(i);
      int now = ((Object[]) elementData.get(list)).length;
      if (now != capacity) {
        System.out.println("adding element " + i + ": capacity " + capacity + " -> " + now);
        capacity = now;
      }
    }
    System.out.println("size " + list.size() + ", capacity " + capacity);
    list.trimToSize();
    System.out.println("after trimToSize(): capacity " + ((Object[]) elementData.get(list)).length);
  }
}
 OUTPUT of the above code
empty list: size 0, capacity 0
adding element 1: capacity 0 -> 10
adding element 11: capacity 10 -> 15
adding element 16: capacity 15 -> 22
adding element 23: capacity 22 -> 33
adding element 34: capacity 33 -> 49
adding element 50: capacity 49 -> 73
size 50, capacity 73
after trimToSize(): capacity 50
A new ArrayList starts without an array; the first add() creates one of 10 slots, and each later growth adds half of the current capacity: 10, 15, 22, 33, 49, 73. trimToSize() shrinks the array to the size. When the final size is known in advance, new ArrayList<>(1000) creates the right capacity at once and avoids the copying.

How LinkedList stores its elements

A LinkedList is a doubly linked list. Each element is wrapped in a small node object that also holds a reference to the previous node and to the next one; the list itself only knows its first and its last node. How a LinkedList stores its elements - the list holds references to the first and the last node; each node holds the element and references to the previous and the next node; get(3) must start at the first node and follow the next references three times; adding a node only changes the references of its two neighbours
  • Adding or removing an element only changes the references of its neighbours; no other element moves. At the two ends this is immediate, because the list knows the first and the last node.
  • There is no index: to reach element i, the list follows the links from the nearer end, one node at a time. get(i), set(i, e), and add(i, e) or remove(i) in the middle all have to walk there first.
  • Every element costs a separate node object, and the nodes are scattered in memory.

What each operation costs

From the two ways of storing, the cost of each operation follows. O(1) means the time does not depend on the size of the list, O(n) that it grows in proportion to it.
OperationArrayListLinkedList
get(i), set(i, e)O(1)O(n) - walks to position i
add(e) at the endO(1) on average (the array sometimes grows)O(1)
add(0, e), remove(0) at the frontO(n) - shifts all elementsO(1)
add(i, e), remove(i) in the middleO(n) - shifts the elements after iO(n) - walks to i, then O(1) to link
insert or remove through a ListIterator that is already thereO(n) - shifts the elements after itO(1)
iterating over all elementsO(n), very fast - adjacent memoryO(n), slower - node to node
memory per elementone reference, plus unused capacitya node object with three references
The middle of the list is where intuition often goes wrong: a LinkedList can link a new node in O(1), but only after walking to the position, which is O(n) as well - and walking from node to node is slower than shifting an array, which the processor does in one fast memory copy. Inserting in the middle of a list - in an ArrayList, the elements after the position are shifted one slot to the right with a single fast memory copy, then the new element is written into the gap; in a LinkedList, the list first follows the next references from the first node to the position, one node at a time, and then links the new node between its two neighbours

Measuring the difference

The following program times eight operations on both lists, each on a fresh list of 100,000 elements. Every measurement is repeated seven times, and the median is printed; the code runs a few rounds first, so that the JIT compiler has compiled it before the measuring starts.
ListTimings.java
//ListTimings.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
import java.util.function.Supplier;

public class ListTimings {

  static final int SIZE = 100_000;
  static final int OPS = 10_000;
  static long sink;   // results are added here so that the JIT compiler cannot skip the work

  interface Task { void run(List<Integer> list); }

  static List<Integer> filled(Supplier<List<Integer>> factory) {
    List<Integer> list = factory.get();
    for (int i = 0; i < SIZE; i++) list.add(i);
    return list;
  }

  // runs the task on a fresh list 7 times and returns the median time in milliseconds
  static double time(Supplier<List<Integer>> factory, Task task, boolean prefill) {
    double[] ms = new double[7];
    for (int r = 0; r < ms.length; r++) {
      List<Integer> list = prefill ? filled(factory) : factory.get();
      long start = System.nanoTime();
      task.run(list);
      ms[r] = (System.nanoTime() - start) / 1e6;
      sink += list.size();
    }
    Arrays.sort(ms);
    return ms[ms.length / 2];
  }

  static void row(String name, Task task, boolean prefill) {
    double a = time(ArrayList::new, task, prefill);
    double l = time(LinkedList::new, task, prefill);
    System.out.printf("%-34s %10.2f %11.2f%n", name, a, l);
  }

  public static void main(String[] args) {
    int[] indexes = new Random(42).ints(OPS, 0, SIZE).toArray();
    Task addAtEnd = list -> { for (int i = 0; i < SIZE; i++) list.add(i); };
    Task getByIndex = list -> { for (int i : indexes) sink += list.get(i); };
    Task iterate = list -> { for (int v : list) sink += v; };
    Task addAtFront = list -> { for (int i = 0; i < OPS; i++) list.add(0, i); };
    Task removeAtFront = list -> { for (int i = 0; i < OPS; i++) list.remove(0); };
    Task addInMiddle = list -> { for (int i = 0; i < OPS; i++) list.add(list.size() / 2, i); };
    Task iteratorInsert = list -> {   // inserts -1 after every tenth element
      ListIterator<Integer> it = list.listIterator();
      while (it.hasNext()) { if (it.next() % 10 == 0) it.add(-1); }
    };
    Task removeIfHalf = list -> list.removeIf(v -> v % 2 == 0);

    for (int warmUp = 0; warmUp < 2; warmUp++) {
      time(ArrayList::new, getByIndex, true);
      time(LinkedList::new, iterate, true);
      time(ArrayList::new, addInMiddle, true);
      time(LinkedList::new, addAtFront, true);
    }

    System.out.printf("%-34s %10s %11s%n", "operation (100,000 elements)", "ArrayList", "LinkedList");
    row("add 100,000 at the end", addAtEnd, false);
    row("get(i) at 10,000 random indexes", getByIndex, true);
    row("iterate over all elements", iterate, true);
    row("add(0, e) 10,000 times", addAtFront, true);
    row("remove(0) 10,000 times", removeAtFront, true);
    row("add(size/2, e) 10,000 times", addInMiddle, true);
    row("insert with ListIterator.add()", iteratorInsert, true);
    row("removeIf() on half the elements", removeIfHalf, true);
    System.out.println("(milliseconds, median of 7 runs)");
  }
}
 OUTPUT of the above code
operation (100,000 elements)        ArrayList  LinkedList
add 100,000 at the end                   2.58        3.26
get(i) at 10,000 random indexes          0.11      331.40
iterate over all elements                1.05        3.64
add(0, e) 10,000 times                  97.51        0.18
remove(0) 10,000 times                  70.62        0.82
add(size/2, e) 10,000 times             46.77      684.03
insert with ListIterator.add()          45.93        4.64
removeIf() on half the elements          2.49        1.97
(milliseconds, median of 7 runs)
Explanation of the output The exact times depend on the computer and change a little from run to run; what matters is how far apart the two columns are.
  • Access by index is where LinkedList loses badly: 10,000 calls of get(i) took a fraction of a millisecond on the ArrayList and hundreds of milliseconds on the LinkedList, which walked on average 25,000 nodes per call. A loop such as for (int i = 0; i < list.size(); i++) list.get(i) over a LinkedList is the classic way to make a program slow; a for-each loop does not have this problem.
  • Adding at the end took about the same time on both, and iterating was faster on the ArrayList, whose elements lie next to each other in memory.
  • At the front, LinkedList wins: add(0, e) and remove(0) cost it almost nothing, while the ArrayList shifted up to 110,000 elements each time.
  • In the middle by index, ArrayList wins - more than ten times faster here, although it shifted 50,000 elements per insert. The LinkedList spent its time walking to the middle.
  • When the position is reached anyway during a pass over the list, as with ListIterator.add(), the LinkedList only relinks and was about ten times faster. removeIf() was close on both lists - in some runs the LinkedList was ahead - because ArrayList.removeIf() moves the remaining elements in a single pass, not once per removed element.

Memory per element

Each element of a LinkedList needs a node object: an object header plus three references - the element, the previous node and the next node. An ArrayList needs one reference per element, plus the unused part of its array. The next program fills each list with one million references to the same object, so that only the memory of the list itself is measured.
ListMemory.java
//ListMemory.java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.function.Supplier;

public class ListMemory {

  static final int SIZE = 1_000_000;

  static long usedMemory() {
    for (int i = 0; i < 3; i++) System.gc();
    Runtime rt = Runtime.getRuntime();
    return rt.totalMemory() - rt.freeMemory();
  }

  static void measure(String name, Supplier<List<Object>> factory) {
    Object element = new Object();   // the same element every time, so only the list itself is measured
    long before = usedMemory();
    List<Object> list = factory.get();
    for (int i = 0; i < SIZE; i++) list.add(element);
    long after = usedMemory();
    System.out.printf("%-32s %5.1f MB  %5.1f bytes per element%n", name, (after - before) / 1e6, (after - before) / (double) SIZE);
    if (list.size() != SIZE) throw new AssertionError();
  }

  public static void main(String[] args) {
    measure("ArrayList, grown by add()", ArrayList::new);
    measure("ArrayList, new ArrayList<>(SIZE)", () -> new ArrayList<>(SIZE));
    measure("LinkedList", LinkedList::new);
  }
}
 OUTPUT of the above code
ArrayList, grown by add()          5.2 MB    5.2 bytes per element
ArrayList, new ArrayList<>(SIZE)   4.2 MB    4.2 bytes per element
LinkedList                        24.0 MB   24.0 bytes per element
  • The ArrayList created with its final capacity needed about 4 bytes per element - one reference, which the JVM stores in 4 bytes on a heap of this size. Grown by add(), it needed more, because its last growth left part of the array unused.
  • The LinkedList needed about 24 bytes per element, around five times as much. On a list of millions of elements the difference is tens of megabytes, and more objects also mean more work for the garbage collector.

LinkedList as a queue - use ArrayDeque instead

LinkedList also implements Deque, and is often used as a queue or a stack because adding and removing at the ends is cheap. For that purpose the JDK has a class made for it: ArrayDeque, which stores the elements in a circular array, has the same O(1) operations at both ends without a node per element, and is described in its documentation as likely to be faster than LinkedList when used as a queue. Unlike LinkedList, it does not accept null elements.

When to use which

  • Use ArrayList by default. Most lists are filled at the end, read by index or iterated over, and that is where ArrayList is fast and compact.
  • Choose LinkedList only when the program mainly inserts or removes while iterating with a ListIterator over a long list, or at the front of a list that is not a queue - and measure, because the walking cost often cancels the gain.
  • For a queue, a stack or work at both ends, use ArrayDeque.
  • Never read a LinkedList by index in a loop; iterate with for-each or an iterator.
  • Because both implement List, declare variables as List<E>: switching from one to the other is then a change of one line.

Summary

In this tutorial we saw that an ArrayList stores its elements in an array that grows by half when it is full, and a LinkedList in nodes linked in both directions. From that, ArrayList reads any position at once but shifts elements to insert or remove, while LinkedList relinks without shifting but has to walk to a position first. A timing program measured eight operations: get(i) and inserts in the middle by index were far faster on the ArrayList, work at the front and inserts through a ListIterator were faster on the LinkedList. A memory measurement showed about 4 bytes per element for ArrayList against about 24 for LinkedList. ArrayList is the default choice, and ArrayDeque is the better queue.