Linked List — The Data Structures Atlas

Category: Linear

The problem

A dynamic array gives O(1) indexed access, but inserting into the middle costs O(n): every element after the insertion point has to shift over by one. When the operation an application actually does most is "insert here, next to something I already have a reference to" — not "index into position N" — an array's shifting cost is pure overhead.

The solution

Store each element in its own node, holding a pointer to both the previous and the next node. Splicing a new node in next to an existing one is then just a handful of pointer reassignments — nothing else in the list has to move, because nothing else's position is defined relative to an index. The cost of that: there's no way to jump to "position N" directly, so indexed access has to walk from the head one link at a time.

flowchart LR
    H["head"] <--> A["A"] <--> B["B"] <--> C["C"] <--> T["tail"]

Operation	Cost	Why
`addFirst` / `addLast`	O(1)	just relinks the head/tail pointer
`insertAfter(node, v)` / `remove(node)`	O(1)	relinks the neighbors of a node you already hold
`get(index)`	O(n)	no random access — has to walk from the head

Classic example

classic/LinkedList is a doubly linked list built on hand-rolled Node<T> objects — no java.util.LinkedList. addFirst, addLast, insertAfter, and remove(Node) are all O(1); get(index) is the one O(n) escape hatch, kept only so the benchmark below has something to contrast against. LinkedListTest covers every splice/unlink combination (head, tail, middle, and the single-element case where a node is simultaneously head and tail).

Applied example: insurance claim workflow stages

applied/ClaimWorkflow models an insurance claim's processing pipeline (at a large insurer) as a chain of ClaimStage nodes: intake, document verification, assessment, payout. A high-value claim might need an extra "manual review" stage inserted right after document verification — with an array-backed list that shifts every stage after the insertion point; here it's one splice, regardless of how many stages come after it. ClaimWorkflowTest covers inserting mid-pipeline, appending after the last stage, and the unknown-stage-name failure case.

Benchmark

./gradlew :linear:linked-list:jmh

Real run (JMH 1.37, JDK 26.0.2, 2 warmup + 3 measurement iterations, 1 fork) — the mirror image of the dynamic-array benchmark:

Benchmark	size=100	size=10,000	size=100,000
`insertAfterKnownAnchor`	116.5 ns	119.6 ns	116.1 ns
`getMiddleElement` (indexed read)	42.5 ns	8,203.3 ns	78,680.1 ns

Insertion at a known anchor stays flat around 116–120ns regardless of whether the list holds 100 or 100,000 elements — O(1), confirmed. Indexed access instead grows roughly in step with size (~100x slower at size=10,000 than at size=100, ~10x slower again at size=100,000 than at size=10,000) — the O(n) walk-from-the-head cost, made visible.

When not to use it

Need indexed access, binary search, or cache-friendly bulk iteration? A Dynamic Array wins on all three — see that module's benchmark for the mirror-image numbers.
insertAfter/remove are only O(1) if you already hold the Node reference. Finding which node to splice next to (by value or by search) is still O(n) here — the applied example's findNode is honest about that cost, it just isn't the operation this module is about.
Random access pattern with unpredictable indices, no stable node references to reuse? The per-node pointer overhead and pointer-chasing (cache-unfriendly, unlike an array's contiguous layout) make this a worse fit than it looks on paper.

Test coverage

100% instruction coverage, 100% branch coverage (JaCoCo). Reproduce it yourself:

./gradlew :linear:linked-list:jacocoTestReport

Report at linear/linked-list/build/reports/jacoco/test/html/index.html.

Unit tests

src/test/java/com/datastructures/linear/linkedlist/classic/LinkedListTest.java

package com.datastructures.linear.linkedlist.classic;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class LinkedListTest {

    @Test
    void startsEmpty() {
        LinkedList<String> list = new LinkedList<>();

        assertThat(list.isEmpty()).isTrue();
        assertThat(list.size()).isZero();
    }

    @Test
    void addFirstOnAnEmptyListBecomesTheOnlyElement() {
        LinkedList<String> list = new LinkedList<>();

        list.addFirst("a");

        assertThat(list.get(0)).isEqualTo("a");
        assertThat(list.size()).isEqualTo(1);
        assertThat(list.isEmpty()).isFalse();
    }

    @Test
    void addFirstOnANonEmptyListPrependsIt() {
        LinkedList<String> list = new LinkedList<>();
        list.addFirst("b");

        list.addFirst("a");

        assertThat(toList(list)).containsExactly("a", "b");
    }

    @Test
    void addLastOnAnEmptyListBecomesTheOnlyElement() {
        LinkedList<String> list = new LinkedList<>();

        list.addLast("a");

        assertThat(list.get(0)).isEqualTo("a");
        assertThat(list.size()).isEqualTo(1);
    }

    @Test
    void addLastOnANonEmptyListAppendsIt() {
        LinkedList<String> list = new LinkedList<>();
        list.addLast("a");

        list.addLast("b");

        assertThat(toList(list)).containsExactly("a", "b");
    }

    @Test
    void insertAfterTheTailBehavesLikeAddLast() {
        LinkedList<String> list = new LinkedList<>();
        LinkedList.Node<String> first = list.addLast("a");

        list.insertAfter(first, "b");

        assertThat(toList(list)).containsExactly("a", "b");
    }

    @Test
    void insertAfterAMiddleNodeSplicesInWithoutShifting() {
        LinkedList<String> list = new LinkedList<>();
        LinkedList.Node<String> a = list.addLast("a");
        list.addLast("c");

        list.insertAfter(a, "b");

        assertThat(toList(list)).containsExactly("a", "b", "c");
        assertThat(list.size()).isEqualTo(3);
    }

    @Test
    void removeFirstOnAnEmptyListThrows() {
        LinkedList<String> list = new LinkedList<>();

        assertThatThrownBy(list::removeFirst).isInstanceOf(NoSuchElementException.class);
    }

    @Test
    void removeLastOnAnEmptyListThrows() {
        LinkedList<String> list = new LinkedList<>();

        assertThatThrownBy(list::removeLast).isInstanceOf(NoSuchElementException.class);
    }

    @Test
    void removeFirstReturnsAndUnlinksTheHead() {
        LinkedList<String> list = new LinkedList<>();
        list.addLast("a");
        list.addLast("b");

        String removed = list.removeFirst();

        assertThat(removed).isEqualTo("a");
        assertThat(toList(list)).containsExactly("b");
    }

    @Test
    void removeLastReturnsAndUnlinksTheTail() {
        LinkedList<String> list = new LinkedList<>();
        list.addLast("a");
        list.addLast("b");

        String removed = list.removeLast();

        assertThat(removed).isEqualTo("b");
        assertThat(toList(list)).containsExactly("a");
    }

    @Test
    void removingTheOnlyElementLeavesAnEmptyList() {
        LinkedList<String> list = new LinkedList<>();
        LinkedList.Node<String> only = list.addLast("a");

        list.remove(only);

        assertThat(list.isEmpty()).isTrue();
        assertThat(list.size()).isZero();
    }

    @Test
    void removingAMiddleNodeSplicesItsNeighborsTogether() {
        LinkedList<String> list = new LinkedList<>();
        list.addLast("a");
        LinkedList.Node<String> b = list.addLast("b");
        list.addLast("c");

        list.remove(b);

        assertThat(toList(list)).containsExactly("a", "c");
    }

    @Test
    void getReturnsTheValueAtTheGivenIndex() {
        LinkedList<Integer> list = new LinkedList<>();
        list.addLast(10);
        list.addLast(20);
        list.addLast(30);

        assertThat(list.get(1)).isEqualTo(20);
    }

    @Test
    void getRejectsOutOfBoundsIndexes() {
        LinkedList<Integer> list = new LinkedList<>();
        list.addLast(10);

        assertThatThrownBy(() -> list.get(-1)).isInstanceOf(IndexOutOfBoundsException.class);
        assertThatThrownBy(() -> list.get(1)).isInstanceOf(IndexOutOfBoundsException.class);
    }

    @Test
    void iteratesHeadToTailAndExhaustsCorrectly() {
        LinkedList<Integer> list = new LinkedList<>();
        list.addLast(1);
        list.addLast(2);

        Iterator<Integer> iterator = list.iterator();
        List<Integer> collected = new ArrayList<>();
        while (iterator.hasNext()) {
            collected.add(iterator.next());
        }

        assertThat(collected).containsExactly(1, 2);
        assertThatThrownBy(iterator::next).isInstanceOf(NoSuchElementException.class);
    }

    @Test
    void headNodeAndTailNodeExposeTheEndsForTraversal() {
        LinkedList<String> list = new LinkedList<>();
        list.addLast("a");
        list.addLast("b");
        list.addLast("c");

        assertThat(list.headNode().value()).isEqualTo("a");
        assertThat(list.tailNode().value()).isEqualTo("c");
        assertThat(list.headNode().next().value()).isEqualTo("b");
        assertThat(list.tailNode().prev().value()).isEqualTo("b");
        assertThat(list.headNode().prev()).isNull();
        assertThat(list.tailNode().next()).isNull();
    }

    private static <T> List<T> toList(LinkedList<T> list) {
        List<T> result = new ArrayList<>();
        for (T value : list) {
            result.add(value);
        }
        return result;
    }
}

src/test/java/com/datastructures/linear/linkedlist/applied/ClaimWorkflowTest.java

package com.datastructures.linear.linkedlist.applied;

import org.junit.jupiter.api.Test;

import java.util.NoSuchElementException;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class ClaimWorkflowTest {

    @Test
    void startsWithTheDefaultFourStageSequence() {
        ClaimWorkflow workflow = new ClaimWorkflow();

        assertThat(workflow.stageNames())
                .containsExactly("intake", "document-verification", "assessment", "payout");
    }

    @Test
    void insertingAStageAfterAnExistingOneSplicesItInWithoutDisturbingTheRest() {
        ClaimWorkflow workflow = new ClaimWorkflow();

        workflow.insertStageAfter("document-verification", "manual-review");

        assertThat(workflow.stageNames())
                .containsExactly("intake", "document-verification", "manual-review", "assessment", "payout");
    }

    @Test
    void insertingAfterTheLastStageAppendsIt() {
        ClaimWorkflow workflow = new ClaimWorkflow();

        workflow.insertStageAfter("payout", "post-payout-audit");

        assertThat(workflow.stageNames())
                .containsExactly("intake", "document-verification", "assessment", "payout", "post-payout-audit");
    }

    @Test
    void insertingAfterAnUnknownStageThrows() {
        ClaimWorkflow workflow = new ClaimWorkflow();

        assertThatThrownBy(() -> workflow.insertStageAfter("nonexistent", "x"))
                .isInstanceOf(NoSuchElementException.class);
    }
}

View full JaCoCo coverage report →