LinkedList Class in Java

The loop for (int i = 0; i < list.size(); i++) { list.get(i); } looks harmless, but on a LinkedList of 100,000 elements it makes about 2.5 billion pointer hops: every get(i) call walks to the requested node again from the beginning or the end of the list. The same pass with a for-each loop takes 100,000 steps. The reason lies in how this class is built.

LinkedList (java.util.LinkedList) is the doubly linked list implementation in Java: every element is stored in a separate node that holds references to the previous and the next node. The class is part of the Java Collections Framework and implements two interfaces at once, List and Deque, so it works as a list, a queue, a double-ended queue and a stack. Adding and removing at the ends takes O(1), access by index takes O(n). LinkedList accepts any values, including null, and is not thread-safe.

LinkedList implementation in Java: Node objects

There is no array inside a LinkedList: every element lives in a Node object that stores the element itself (item) and references to the next (next) and the previous (prev) node. The list itself remembers only the first node (first), the last node (last) and the number of elements (size).

Here is a fragment of the LinkedList source code in a modern JDK (Java 7 and later, including Java 8, 17 and 21):

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;

    private static 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;
        }
    }
    // ...
}

Node is a good example of a static nested class: a node needs no reference to the list object, so it is declared static. The first node has prev == null, the last one has next == null.

A LinkedList of four elements A, B, C and D looks like this (the arrows are the next and prev references):

How get(index) works in LinkedList

The get(index) method cannot jump straight to the right cell the way an array does: it follows the references from node to node. To shorten the walk, the JDK starts from the nearer end — from first if the index is in the first half, and from last if it is in the second:

Node<E> node(int index) {
    if (index < (size >> 1)) {          // index in the first half
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {                            // second half: walk from the end
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

That is why get(0) and get(size() - 1) return immediately, while an element in the middle takes the longest — up to n/2 steps. In Big O notation that is still O(n). set(index, e), add(index, e) and remove(index) go through the same node() method.

ArrayList vs LinkedList: the difference

ArrayList stores elements in an array and gives O(1) access by index, while LinkedList stores them in linked nodes: index access is O(n), but inserting or removing at an already found position does not shift the other elements. ArrayList is faster for most tasks; LinkedList is chosen for frequent operations at both ends or insertions through an iterator.

Removing element B from the middle of a linked list comes down to rewriting two references: A.next now points to C, and C.prev points to A. The other nodes are not touched:

But to remove B with remove(1) or remove("B"), the list has to find it first, and that is a walk along the chain in O(n). You get O(1) only when the node is already at hand: at the ends of the list or at the current position of an iterator.

Even where LinkedList has the better Big O, ArrayList is often faster on real data: array elements sit next to each other in memory and fit the CPU cache well, and System.arraycopy() shifts thousands of references very quickly. LinkedList nodes are scattered across the heap, and every hop along next is a potential cache miss. If what you need is a queue or a stack, ArrayDeque is usually the better choice — the three classes are compared in ArrayDeque vs LinkedList vs Stack.

LinkedList constructors

LinkedList has two constructors: a no-argument one that creates an empty list, and one that takes a collection and copies its elements into the new list in the order of its iterator. There is no constructor with an initial capacity: there is no array inside, so nothing needs to be reserved in advance.

As with other collections, the variable is declared with an interface type: List<String> list = new LinkedList<>(); if you need list methods, or Deque<String> deque = new LinkedList<>(); if you need a queue.

LinkedList methods: example and time complexity

LinkedList methods come from two interfaces: List provides index-based operations (add(i, e), get(i), set(i, e), remove(i)), and Deque provides operations at the ends (addFirst(), addLast(), removeFirst(), removeLast(), peek(), poll()). Methods at the ends run in O(1), methods with an index in O(n).

In the example below the variable is declared with the class LinkedList rather than an interface. You would not do this in ordinary code, but here it is deliberate: through the LinkedList type both the List and the Deque methods are available at once.

import java.util.LinkedList;

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

        list.add("F");
        list.add("B");
        list.add("D");
        list.add("E");
        list.add("C");
        list.addLast("Z");
        list.addFirst("A");
        list.add(1, "A2");
        System.out.println("Contents: " + list);

        list.remove("F");
        list.remove(2);
        list.removeFirst();
        list.removeLast();
        System.out.println("After removal: " + list);

        String val = list.get(2);
        list.set(2, val + "+");
        System.out.println("After update: " + list);
    }
}

Output:

Contents: [A, A2, F, B, D, E, C, Z]
After removal: [A2, D, E, C]
After update: [A2, D, E+, C]

Step by step:

• add() appends F, B, D, E, C to the end of the list in that order; addLast("Z") also appends, addFirst("A") inserts at the beginning, and add(1, "A2") inserts A2 at position 1 (indexes start at zero).
• remove("F") removes the object F, leaving [A, A2, B, D, E, C, Z]; remove(2) removes the element at index 2, which is B. Then removeFirst() removes A and removeLast() removes Z.
• get(2) returns E, and set(2, "E+") replaces it without changing the size of the list.

Time complexity of the main methods and how they behave on an empty list:

getFirst(), removeFirst() and their relatives have always been available on LinkedList (from Deque); since Java 21 they are also declared in List through SequencedCollection (details). Methods shared by all lists are covered in List and ArrayList methods.

LinkedList as a queue and a stack

LinkedList implements Deque, so the same object can work as a FIFO queue (offer() to the tail, poll() from the head) and as a LIFO stack (push() and pop() at the head). It still remains a list: indexes are available at any moment, and toString() shows the elements from head to tail.

What does this code print?

import java.util.LinkedList;

public class LinkedListDequeExample {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);        // to the end
        list.push(2);       // to the front, like a stack
        list.offer(3);      // to the end, like a queue
        list.addFirst(4);   // to the front
        System.out.println(list);

        System.out.println(list.pop());
        System.out.println(list.poll());
        System.out.println(list.peekLast());
        System.out.println(list);
    }
}

Output:

[4, 2, 1, 3]
4
2
3
[1, 3]

This is easy to get wrong: push() adds to the front, while add() and offer() add to the end. Both pop() and poll() take the element from the head, so 4 came out first, then 2. peekLast() only looks at the tail without removing it. The full list of queue methods and the difference between the offer/add and poll/remove pairs are in Queue and Deque Interfaces in Java.

Iterating a LinkedList and inserting in the middle

Iterate a LinkedList with a for-each loop, the forEach() method or an explicit iterator — each of them passes through the list in O(n). A for loop with get(i) does not suit a LinkedList: every call searches for the node again, and the pass becomes O(n²).

That is where the number from the start of the lesson comes from. For a list of n elements, get(i) takes about min(i, n − i) steps, and summed over all indexes that is about n²/4: for 100,000 elements, about 2.5 billion pointer hops. An iterator simply remembers the current node and moves to next on each step.

An iterator is also the way to get true O(1) insertion and removal: a ListIterator stands on a node it has already found, and its add() and remove() methods change only the neighbouring references.

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

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

        ListIterator<String> it = list.listIterator();
        while (it.hasNext()) {
            String s = it.next();
            if (s.equals("B")) {
                it.add("B2");     // insert after B in O(1)
            } else if (s.equals("C")) {
                it.remove();      // remove C in O(1)
            }
        }
        System.out.println(list);
    }
}

Output:

[A, B, B2, D]

B2 was inserted right after B and C was removed — all in one pass, without searching for the position again. If you call list.add() or list.remove() inside the loop instead of it.add() and it.remove(), the next it.next() throws ConcurrentModificationException. Besides add() and remove(), a ListIterator can move backwards with previous(), replace the current element with set() and report its position with nextIndex().