Linked List — The Data Structures Atlas

Categoría: Linear

El problema

Un array dinámico ofrece acceso indexado O(1), pero insertar en el medio cuesta O(n): cada elemento después del punto de inserción tiene que desplazarse una posición. Cuando la operación que una aplicación realmente hace con más frecuencia es "inserta aquí, al lado de algo para lo que ya tengo una referencia" — y no "indexa en la posición N" — el costo de desplazamiento de un array es puro overhead.

La solución

Almacena cada elemento en su propio nodo, manteniendo un puntero tanto al nodo anterior como al siguiente. Insertar un nuevo nodo junto a uno existente es entonces solo un puñado de reasignaciones de punteros — nada más en la lista tiene que moverse, porque la posición de ningún otro elemento está definida en relación a un índice. El costo de eso: no hay forma de saltar directamente a la "posición N", así que el acceso indexado tiene que recorrer la lista desde la cabeza, un enlace a la vez.

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

Operación	Costo	Por qué
`addFirst` / `addLast`	O(1)	solo reconecta el puntero de head/tail
`insertAfter(node, v)` / `remove(node)`	O(1)	reconecta a los vecinos de un nodo que ya tienes
`get(index)`	O(n)	sin acceso aleatorio — hay que recorrer desde la cabeza

Ejemplo clásico

classic/LinkedList es una lista doblemente enlazada construida sobre objetos Node<T> hechos a mano — sin java.util.LinkedList. addFirst, addLast, insertAfter y remove(Node) son todos O(1); get(index) es la única vía de escape O(n), mantenida solo para que el benchmark de abajo tenga algo con qué contrastar. LinkedListTest cubre cada combinación de inserción/desconexión (head, tail, medio, y el caso de un solo elemento, donde un nodo es simultáneamente head y tail).

Ejemplo aplicado: etapas del flujo de siniestros de seguro

applied/ClaimWorkflow modela el pipeline de procesamiento de un siniestro de seguro (en una gran aseguradora) como una cadena de nodos ClaimStage: recepción, verificación de documentos, evaluación, pago. Un siniestro de alto valor puede necesitar una etapa extra de "revisión manual" insertada justo después de la verificación de documentos — con una lista respaldada por array eso desplaza cada etapa después del punto de inserción; aquí es una sola inserción, sin importar cuántas etapas vengan después. ClaimWorkflowTest cubre la inserción a mitad del pipeline, el append después de la última etapa, y el caso de falla por nombre de etapa desconocido.

Benchmark

./gradlew :linear:linked-list:jmh

Ejecución real (JMH 1.37, JDK 26.0.2, 2 iteraciones de warmup + 3 de medición, 1 fork) — la imagen especular del benchmark de dynamic-array:

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

La inserción en un anchor conocido se mantiene estable alrededor de 116–120ns, sin importar si la lista tiene 100 o 100,000 elementos — O(1), confirmado. El acceso indexado, en cambio, crece casi proporcionalmente al tamaño (~100x más lento en size=10,000 que en size=100, ~10x más lento de nuevo en size=100,000 que en size=10,000) — el costo O(n) de recorrer desde la cabeza, hecho visible.

Cuándo no usarlo

¿Necesitas acceso indexado, búsqueda binaria o iteración masiva favorable a la caché? Un Dynamic Array gana en los tres frentes — consulta el benchmark de ese módulo para ver los números especulares.
insertAfter/remove solo son O(1) si ya tienes la referencia al Node. Encontrar cuál nodo usar como referencia para insertar (por valor o por búsqueda) sigue siendo O(n) aquí — el findNode del ejemplo aplicado es honesto sobre ese costo, solo que esa no es la operación de la que trata este módulo.
¿Patrón de acceso aleatorio con índices impredecibles, sin referencias de nodo estables para reutilizar? El overhead de puntero por nodo y el pointer-chasing (poco favorable a la caché, a diferencia del diseño contiguo de un array) hacen que esto encaje peor de lo que parece sobre el papel.

Cobertura de pruebas

100% de cobertura de instrucciones, 100% de cobertura de ramas (JaCoCo). Reprodúcelo tú mismo:

./gradlew :linear:linked-list:jacocoTestReport

Informe en linear/linked-list/build/reports/jacoco/test/html/index.html.

Pruebas unitarias

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);
    }
}

Ver informe completo de cobertura JaCoCo →