ArrayList vs LinkedList in Java

The short answer

• Use ArrayList by default: fast access by index, fast iteration, less memory.
• Use ArrayDeque (not LinkedList) when you need a queue or a stack.
• Choose LinkedList only when you add and remove in the middle through a ListIterator a lot, which is rare.

Comparison table

How ArrayList works

An ArrayList keeps its elements in an array. Reading index i is a single step. When the array is full, add creates a new array about 1.5 times bigger and copies everything over; because this happens rarely, adding at the end is still O(1) on average. Inserting at index 0 shifts every element one place to the right.

If you know roughly how many elements are coming, new ArrayList<>(10_000) avoids the repeated copying.

How LinkedList works

A LinkedList stores each element in its own node that points to the previous and the next node. Adding or removing at either end only changes a few links. But to reach index 500 it has to walk node by node, and each node costs extra memory for the two links.

Same code, both lists

Because both implement List, you can write code against the interface and pick the implementation in one place.

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

public class SameInterface {
    static void work(List<String> list) {
        list.add("b");
        list.add("c");
        list.add(0, "a");        // insert at the start
        list.remove("c");
        list.set(1, "B");
        System.out.println(list.getClass().getSimpleName() + " " + list + " size=" + list.size());
    }

    public static void main(String[] args) {
        work(new ArrayList<>());
        work(new LinkedList<>());
    }
}

ArrayList [a, B] size=2
LinkedList [a, B] size=2

LinkedList as a queue, and why ArrayDeque is better

LinkedList also implements Deque, so it can act as a queue or a stack. ArrayDeque does the same job with less memory and better speed, and it is the class Java's own documentation recommends.

import java.util.ArrayDeque;
import java.util.Deque;

public class QueueAndStack {
    public static void main(String[] args) {
        Deque<String> queue = new ArrayDeque<>();
        queue.offer("first");
        queue.offer("second");
        queue.offer("third");
        System.out.println(queue.poll()); // FIFO: first in, first out

        Deque<String> stack = new ArrayDeque<>();
        stack.push("bottom");
        stack.push("middle");
        stack.push("top");
        System.out.println(stack.pop());  // LIFO: last in, first out
        System.out.println(stack.peek());
    }
}

first
top
middle

Common mistakes

• Choosing LinkedList "because inserts are O(1)". Finding the position is O(n), so inserts in the middle are not faster in practice.
• Looping over a LinkedList with for (int i = 0; i < list.size(); i++) list.get(i). Every get walks the list, making the loop O(n²). Use a for-each loop.
• Using the old Stack or Vector classes. They are synchronized and outdated; use ArrayDeque and ArrayList.
• Declaring variables as ArrayList<String> list. Declare List<String> list so the implementation can change in one place.

• Java collections interview questions
• HashMap vs TreeMap vs LinkedHashMap