LinkedList in Java: How It Works, When to Use It, and When Not To

I used to think LinkedList was the “advanced” data structure, the one serious Java devs reached for instead of ArrayList. Then I profiled a piece of code where I’d swapped ArrayList for LinkedList to “optimize” insertions, and it was actually slower. Turns out, I’d made every wrong assumption about when LinkedList wins.

That experience is why this post exists. LinkedList is a powerful data structure, but it’s misunderstood. It’s not a drop-in replacement for ArrayList. It excels in specific scenarios and loses badly in others. Let me break down which is which.

What Is a LinkedList?

A LinkedList is a data structure where each element (called a node) stores its value and a reference (pointer) to the next node. Unlike an array, elements are not stored in contiguous memory. Each node can live anywhere in memory, and they are connected through these references.

Singly Linked List:

[10 | *] [20 | *] [30 | *] [40 | null]

Doubly Linked List:

null [10 | * | *] [20 | * | *] [30 | * | *] [40 | * | null]

The key difference from an ArrayList: LinkedList does not use an underlying array. This changes everything about how it performs insertions, deletions, and lookups.

How Java Implements LinkedList

Java provides java.util.LinkedList, which implements both the List and Deque interfaces. It is a doubly linked list: each node has a reference to both the next and the previous node.

Here is a simplified version of what happens inside:

// Simplified internal structure
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

When you create a LinkedList, you get an empty list with a first and last pointer:

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
// list.first null
// list.last  null
// list.size  0

When to Use LinkedList

LinkedList is often misunderstood. It is not a universal replacement for ArrayList. It excels in specific scenarios.

Use LinkedList when:

• You need frequent insertions and deletions at the beginning or middle of the list. Inserting at the head of an ArrayList requires shifting every element. LinkedList just updates pointers. That is O(1) vs O(n).
• You are building a queue or stack. LinkedList implements Deque, so you get addFirst(), addLast(), removeFirst(), removeLast() all in O(1).
• You do not need random access. If you rarely use get(index) and mostly iterate or modify from the ends, LinkedList is a strong choice.
• Memory allocation is fragmented. LinkedList nodes can live anywhere in memory, so it works well when contiguous allocation is expensive or unavailable.

Do not use LinkedList when:

• You need frequent random access by index. get(i) in LinkedList is O(n) because it must traverse from the head or tail. ArrayList gives you O(1).
• You are doing a lot of searches. Searching a LinkedList requires linear traversal every time.
• You want cache-friendly performance. ArrayList elements sit in contiguous memory, which plays nicely with CPU caches. LinkedList nodes are scattered, causing more cache misses.

The cache point is the one most people overlook. Even when LinkedList has better Big-O for an operation, the constant factors from cache misses can make ArrayList faster in practice. I’ve seen this firsthand, profiling doesn’t lie.

Core Operations with Code

Creating and Populating

import java.util.LinkedList;

LinkedList<Integer> numbers = new LinkedList<>();

// Add elements
numbers.add(10);         // append to end
numbers.addFirst(5);     // insert at head
numbers.addLast(20);     // insert at tail
numbers.add(2, 15);      // insert at index 2

// Result: [5, 10, 15, 20]

Accessing Elements

int first = numbers.getFirst();   // 5
int last = numbers.getLast();     // 20
int atOne = numbers.get(1);       // 10 (traverses from head)

Important: get(index) is O(n). Each call traverses the list from the nearest end. Do not use it in loops on large lists.

Inserting and Removing

// Insert
numbers.addFirst(1);       // O(1)
numbers.addLast(25);       // O(1)
numbers.add(2, 12);        // O(n) - must traverse to index

// Remove
numbers.removeFirst();     // O(1)
numbers.removeLast();      // O(1)
numbers.remove(2);         // O(n) - must traverse to index
numbers.remove(Integer.valueOf(15));  // O(n) - must find the value first

Iterating

There are three main ways to iterate a LinkedList. Each has different performance characteristics.

LinkedList<String> names = new LinkedList<>();
names.add("Alice");
names.add("Bob");
names.add("Charlie");

1. Enhanced for loop (recommended for most cases)

for (String name : names) {
    System.out.println(name);
}

This uses the Iterator internally. It is clean and safe.

2. Iterator with explicit control

import java.util.Iterator;

Iterator<String> it = names.iterator();
while (it.hasNext()) {
    String name = it.next();
    if (name.equals("Bob")) {
        it.remove();  // safe removal during iteration
    }
}

This is the correct way to remove elements while iterating. Do not use names.remove() inside an enhanced for loop, it throws ConcurrentModificationException. I’ve hit this one in production and it’s a painful way to learn.

3. Index-based loop (avoid this)

for (int i = 0; i < names.size(); i++) {
    System.out.println(names.get(i));  // O(n) per call - O(n^2) total
}

This is O(n^2) because get(i) traverses the list from scratch each time. Never do this on a LinkedList.

Searching

boolean hasBob = names.contains("Bob");       // O(n) linear scan
int index = names.indexOf("Charlie");          // O(n) linear scan

Both are O(n). There is no way to search a LinkedList faster than linear time.

LinkedList as a Deque

One of LinkedList’s biggest strengths is its Deque interface. It works as both a queue and a stack.

As a Queue (FIFO):

LinkedList<String> queue = new LinkedList<>();

queue.offer("first");    // add to tail
queue.offer("second");
queue.offer("third");

String head = queue.poll();   // remove from head "first"
String next = queue.peek();   // look at head without removing "second"

As a Stack (LIFO):

LinkedList<String> stack = new LinkedList<>();

stack.push("bottom");    // add to head
stack.push("middle");
stack.push("top");

String top = stack.pop();     // remove from head "top"
String next = stack.peek();   // look at head without removing "middle"

In practice, Java developers often prefer ArrayDeque over LinkedList for queue and stack operations because ArrayDeque is faster due to better cache locality. But LinkedList works perfectly fine if you already have one.

Performance Comparison

* amortized means occasionally it is O(n) when the internal array needs to resize.

Common Patterns

Reversing a LinkedList

public static <E> void reverse(LinkedList<E> list) {
    int size = list.size();
    for (int i = 0; i < size / 2; i++) {
        E temp = list.get(i);
        list.set(i, list.get(size - 1 - i));
        list.set(size - 1 - i, temp);
    }
}

Or using an iterator for O(n) without random access:

public static <E> void reverse(LinkedList<E> list) {
    java.util.ListIterator<E> left = list.listIterator();
    java.util.ListIterator<E> right = list.listIterator(list.size());

    while (left.nextIndex() < right.previousIndex()) {
        E leftVal = left.next();
        E rightVal = right.previous();

        left.set(rightVal);
        right.set(leftVal);
    }
}

Removing Duplicates

public static <E> void removeDuplicates(LinkedList<E> list) {
    java.util.HashSet<E> seen = new java.util.HashSet<>();
    java.util.Iterator<E> it = list.iterator();

    while (it.hasNext()) {
        E element = it.next();
        if (!seen.add(element)) {
            it.remove();
        }
    }
}

Merging Two Sorted LinkedLists

public static LinkedList<Integer> mergeSorted(
    LinkedList<Integer> a, LinkedList<Integer> b
) {
    LinkedList<Integer> result = new LinkedList<>();
    java.util.ListIterator<Integer> itA = a.listIterator();
    java.util.ListIterator<Integer> itB = b.listIterator();

    Integer valA = itA.hasNext() ? itA.next() : null;
    Integer valB = itB.hasNext() ? itB.next() : null;

    while (valA != null || valB != null) {
        if (valA == null) {
            result.addLast(valB);
            valB = itB.hasNext() ? itB.next() : null;
        } else if (valB == null) {
            result.addLast(valA);
            valA = itA.hasNext() ? itA.next() : null;
        } else if (valA <= valB) {
            result.addLast(valA);
            valA = itA.hasNext() ? itA.next() : null;
        } else {
            result.addLast(valB);
            valB = itB.hasNext() ? itB.next() : null;
        }
    }

    return result;
}

Common Mistakes

Mistake 1: Using get() in a Loop

// Bad - O(n^2)
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// Good - O(n)
for (String s : list) {
    System.out.println(s);
}

Mistake 2: Removing During Enhanced For Loop

// Bad - throws ConcurrentModificationException
for (String s : list) {
    if (s.equals("remove me")) {
        list.remove(s);  // don't do this
    }
}

// Good - use iterator
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("remove me")) {
        it.remove();  // safe
    }
}

Mistake 3: Assuming LinkedList Is Always Faster

LinkedList is not faster than ArrayList. It is only faster for insertions and deletions at known positions near the ends. For most other operations, ArrayList wins. Profile your code before switching.

Building LinkedList from Scratch

Understanding how LinkedList works means building one from scratch. This section shows you how to implement a fully functional linked list using only basic Java primitives, no imports from java.util needed.

Singly Linked List from Scratch

A singly linked list has nodes that only point forward. Each node holds a value and a reference to the next node.

public class SinglyLinkedList<T> {

    private static class Node<E> {
        E data;
        Node<E> next;

        Node(E data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node<T> head;
    private int size;

    public SinglyLinkedList() {
        this.head = null;
        this.size = 0;
    }

    public void addFirst(T value) {
        Node<T> newNode = new Node<>(value);
        newNode.next = head;
        head = newNode;
        size++;
    }

    public void addLast(T value) {
        Node<T> newNode = new Node<>(value);
        if (head == null) {
            head = newNode;
        } else {
            Node<T> current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }

    public T removeFirst() {
        if (head == null) {
            throw new java.util.NoSuchElementException("List is empty");
        }
        T value = head.data;
        head = head.next;
        size--;
        return value;
    }

    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<T> current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

    public boolean contains(T value) {
        Node<T> current = head;
        while (current != null) {
            if (current.data.equals(value)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    public T remove(T value) {
        if (head == null) {
            return null;
        }
        if (head.data.equals(value)) {
            return removeFirst();
        }
        Node<T> current = head;
        while (current.next != null) {
            if (current.next.data.equals(value)) {
                T removed = current.next.data;
                current.next = current.next.next;
                size--;
                return removed;
            }
            current = current.next;
        }
        return null;
    }

    public void printList() {
        Node<T> current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

Usage:

public class Main {
    public static void main(String[] args) {
        SinglyLinkedList<Integer> list = new SinglyLinkedList<>();

        list.addFirst(10);
        list.addFirst(5);
        list.addLast(20);
        list.addLast(25);

        list.printList();   // 5 -> 10 -> 20 -> 25 -> null

        System.out.println(list.get(2));       // 20
        System.out.println(list.size());        // 4

        list.removeFirst();                     // removes 5
        list.remove(20);                        // removes 20

        list.printList();   // 10 -> 25 -> null
    }
}

Doubly Linked List from Scratch

A doubly linked list lets you traverse in both directions. Each node has references to both the next and previous nodes.

public class DoublyLinkedList<T> {

    private static class Node<E> {
        E data;
        Node<E> next;
        Node<E> prev;

        Node(E data) {
            this.data = data;
            this.next = null;
            this.prev = null;
        }
    }

    private Node<T> head;
    private Node<T> tail;
    private int size;

    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    public void addFirst(T value) {
        Node<T> newNode = new Node<>(value);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }

    public void addLast(T value) {
        Node<T> newNode = new Node<>(value);
        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }

    public T removeFirst() {
        if (head == null) {
            throw new java.util.NoSuchElementException("List is empty");
        }
        T value = head.data;
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
        size--;
        return value;
    }

    public T removeLast() {
        if (tail == null) {
            throw new java.util.NoSuchElementException("List is empty");
        }
        T value = tail.data;
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
        size--;
        return value;
    }

    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<T> current;
        if (index < size / 2) {
            current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
        } else {
            current = tail;
            for (int i = size - 1; i > index; i--) {
                current = current.prev;
            }
        }
        return current.data;
    }

    public T remove(T value) {
        if (head == null) {
            return null;
        }
        Node<T> current = head;
        while (current != null) {
            if (current.data.equals(value)) {
                if (current == head) {
                    return removeFirst();
                } else if (current == tail) {
                    return removeLast();
                } else {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                    size--;
                    return current.data;
                }
            }
            current = current.next;
        }
        return null;
    }

    public void printForward() {
        Node<T> current = head;
        System.out.print("null <-> ");
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public void printBackward() {
        Node<T> current = tail;
        System.out.print("null <-> ");
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.prev;
        }
        System.out.println("null");
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

Usage:

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList<String> list = new DoublyLinkedList<>();

        list.addLast("A");
        list.addLast("B");
        list.addLast("C");
        list.addFirst("Z");

        list.printForward();    // null <-> Z <-> A <-> B <-> C <-> null
        list.printBackward();   // null <-> C <-> B <-> A <-> Z <-> null

        System.out.println(list.get(0));    // Z
        System.out.println(list.get(3));    // C

        list.removeFirst();                  // removes Z
        list.removeLast();                   // removes C

        list.printForward();    // null <-> A <-> B <-> null
    }
}

Why Build It from Scratch?

Building your own linked list teaches you things the Collection Framework hides:

• Pointer management. You see exactly how nodes connect and disconnect. Every edge case (empty list, single element, head removal: tail removal: middle removal) becomes real.
• Memory allocation. Each new Node(...) allocates memory on the heap. You start to understand the cost of object creation and garbage collection.
• Time complexity. You feel the O(n) cost of get(index) when you write the traversal loop yourself.
• Debugging skills. Null pointer exceptions in linked lists are common and teach you to think about every pointer assignment.

I built my first linked list for a data structures assignment and it took three tries to get the edge cases right. But after that, every pointer-based data structure made more sense.

Key Differences: Custom vs Collection Framework

What I Took Away

LinkedList is a data structure with a narrow but real sweet spot: frequent insertions and deletions at the ends, queue/stack behavior via Deque, and situations where you can’t guarantee contiguous memory allocation. Outside that sweet spot, ArrayList wins on almost every metric.

The honest advice: default to ArrayList unless you have a specific reason to reach for LinkedList. Profile before switching. The performance difference depends entirely on your access patterns, not on which data structure looks more sophisticated.

Pro Tip: In modern Java development, ArrayDeque is generally preferred over LinkedList for queue and stack operations. It uses a circular array internally and provides better cache performance. Use LinkedList only when you specifically need the O(1) insert and delete at arbitrary positions in the middle of a list, or when your use case requires both List and Deque behavior.