LinkedList en Java — Node, first y next para la lista enlazada del examen (sin ArrayList y sin perder la cola)

Cuando abrí el enunciado del Examen 3 de prácticas, la primera línea en negrita decía: no se pueden usar arrays ni colecciones de Java. Ni ArrayList, ni LinkedList, ni Stack. Me dieron Node, ContainerBase con un first y una clase vacía que tenía que heredar de ella. En Python ya había hecho listas enlazadas, pero en Java cada null es un NullPointerException esperando, y == con textos no hace lo que parece. Este artículo es lo que me habría gustado leer antes de ese examen.

Esto es LinkedList en Java como se pide en FP2: una lista enlazada programada a mano, con nodos que se apuntan unos a otros. Usamos el mismo molde que el examen (Node con value y next, ContainerBase con first y toString(), y tu clase con extends) y el ejemplo de siempre: la cola de reservas de un libro de la biblioteca de la facultad (la norma de que el PDI se cuela es inventada). Todos los programas se han compilado y ejecutado con Java 21, y las salidas son reales.

Si vienes de LinkedList en Python, la idea es idéntica; cambian la sintaxis y dos trampas propias de Java. Y si vienes del último tema, Colecciones en Java, aquí vas a programar por dentro algo parecido a lo que java.util.LinkedList te da hecho.

Qué es una lista enlazada y por qué el examen no deja usar ArrayList

Un ArrayList guarda sus elementos en un array por dentro: casillas seguidas. Por eso get(3) es instantáneo, pero add(0, x) tiene que mover todos los elementos un sitio a la derecha. Una lista enlazada hace lo contrario: cada elemento vive en su propio objeto, un nodo, en cualquier sitio de la memoria, y cada nodo sabe quién va después de él. La lista solo guarda el primero.

Operación	ArrayList	Lista enlazada (solo first)
Leer la posición i	O(1): salto directo	O(n): i saltos desde la cabeza
Insertar al principio	O(n): mueve todo	O(1): cambian dos referencias
Insertar al final	O(1) casi siempre	O(n): hay que llegar al último (O(1) con last)
Borrar si ya estás en el nodo anterior	O(n)	O(1)
Buscar un valor	O(n)	O(n)

¿Por qué el examen prohíbe las colecciones? Porque lo que se evalúa es que sepas manejar referencias a mano: enlazar, desenlazar, recorrer y no dejar nodos sueltos. Es la base de los árboles y los grafos que vendrán en otras asignaturas.

El nodo: value y next

Un nodo guarda dos cosas: el dato (value) y la referencia al siguiente nodo (next), que vale null en el último. Esta es la clase Node que dan en el examen, con un String como dato:

public class Node {
    public String value;     // el dato: quién ha reservado
    public Node next;        // el siguiente nodo (null si es el último)

    public Node(String value) {
        this.value = value;
    }
}

Creamos tres nodos y los encadenamos a mano:

public class Nodos {
    public static void main(String[] args) {
        Node laura = new Node("Laura");
        Node pablo = new Node("Pablo");
        Node marta = new Node("Marta");
        laura.next = pablo;                              // Laura apunta a Pablo
        pablo.next = marta;                              // Pablo apunta a Marta; marta.next sigue a null

        System.out.println(laura.value);                 // el dato del primer nodo
        System.out.println(laura.next.value);            // un salto
        System.out.println(laura.next.next.value);       // dos saltos
        System.out.println(laura.next.next.next);        // tres saltos: null
        System.out.println(laura.next == pablo);         // ¿el MISMO objeto?

        for (Node n = laura; n != null; n = n.next) {    // el recorrido de siempre
            System.out.print(n.value + " -> ");
        }
        System.out.println("null");

        System.out.println(laura.next.next.next.value);  // un salto de más
    }
}

Salida:

Laura
Pablo
Marta
null
true
Laura -> Pablo -> Marta -> null
Exception in thread "main" java.lang.NullPointerException: Cannot read field "value" because "laura.next.next.next" is null
        at Nodos.main(Nodos.java:20)

• laura.next.value da Pablo: desde Laura se sigue una flecha.
• laura.next.next.next da null: Marta es la última y su next nunca se cambió.
• laura.next == pablo da true: no es una copia, es el mismo objeto. Aquí == es justo lo que queremos (comparar referencias).
• El for es el recorrido de toda la vida en Java: empezar en la cabeza, avanzar con n = n.next y parar cuando n es null. Lo vas a escribir en casi todos los métodos.
• La última línea pide .value de null y Java lanza NullPointerException. Desde Java 14 el mensaje dice exactamente qué era null: "laura.next.next.next" is null.

La clase base del examen: ContainerBase y first

En el examen, la lista no empieza de cero: te dan una clase base que guarda la cabeza y sabe dibujarse. Esta es la nuestra, igual que la del simulacro práctico:

public class ContainerBase {
    protected Node first;    // la cabeza: el primer nodo (null si está vacía)

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("➡");
        int steps = 0;       // tope por si hay un ciclo
        for (Node n = first; n != null && steps < 1000; n = n.next, steps++) {
            sb.append(n.value).append("->");
        }
        return sb.append("null").toString();
    }
}

Tres cosas que mirar:

• first es protected: lo pueden usar las clases que heredan de ContainerBase. Tu clase lo manejará directamente.
• toString() ya está hecho y dibuja la lista como ➡Laura->Pablo->null. Gracias a él, System.out.println(cola) enseña la cadena entera.
• El tope de 1000 pasos es un seguro: si por un fallo tuyo la lista acaba formando un ciclo, toString() no se queda colgado para siempre.

Tu clase hereda de ella con extends y añade los métodos que pida el enunciado. La nuestra se llama ColaReservas.

Insertar al principio: el orden de dos líneas

public void insertarDelante(String socio) {
    Node nuevo = new Node(socio);
    nuevo.next = first;                   // 1. el nuevo apunta a la cabeza actual...
    first = nuevo;                        // 2. ...y pasa a ser la cabeza
    size++;
}

El orden no se negocia: primero nuevo.next = first (el nodo nuevo apunta a la cabeza actual) y después first = nuevo. Al revés, first ya es el nodo nuevo cuando haces nuevo.next = first, así que el nodo se apunta a sí mismo y el resto de la cola se queda sin nadie que la apunte. Es lo que enseña la fila «Mal» del dibujo: toString() imprimiría «Ana» mil veces, hasta su tope.

Fíjate también en size++: guardamos el tamaño en un atributo propio (private int size) para que getSize() no tenga que recorrer. A cambio, cada método que añade o quita nodos tiene que actualizarlo.

Insertar al final y recorrer

public void insertarDetras(String socio) {
    Node nuevo = new Node(socio);
    if (first == null) {                  // lista vacía: el nuevo es la cabeza
        first = nuevo;
    } else {
        Node actual = first;
        while (actual.next != null) {     // paramos EN el último, no después
            actual = actual.next;
        }
        actual.next = nuevo;
    }
    size++;
}

• La lista vacía es un caso aparte: si first es null, no hay último al que engancharse y el nuevo pasa a ser la cabeza. Sin ese if, first.next lanzaría NullPointerException.
• while (actual.next != null) se para en el último nodo. Para recorrerlos todos se usa n != null; para pararse en el último y engancharle algo, actual.next != null. Confundirlas es el error del cuestionario.

Esta es la traza al insertar a Iván detrás de Ana -> Laura -> Pablo -> Marta:

Vuelta	actual	actual.next	¿Sigue el while?
Antes	Ana	Laura	Sí
1	Laura	Pablo	Sí
2	Pablo	Marta	Sí
3	Marta	null	No: Marta es la última
Después	Marta	Iván	(se engancha el nuevo)

Cuatro nodos visitados para añadir uno: por eso insertar al final es O(n) si solo guardas first. En la práctica añadimos un last para que sea instantáneo.

Buscar es el mismo recorrido con una comparación:

public boolean contiene(String socio) {
    for (Node n = first; n != null; n = n.next) {
        if (n.value.equals(socio)) {      // equals: compara el texto, no la dirección
            return true;
        }
    }
    return false;
}

Eliminar: la pareja anterior/actual

Para borrar un nodo, el anterior tiene que saltárselo: anterior.next = actual.next. El nodo borrado se queda sin nadie que lo apunte y el recolector de basura de Java lo libera. Como desde un nodo no se puede ir hacia atrás, se recorre con dos referencias que avanzan juntas. La cabeza no tiene anterior: es un caso aparte.

public boolean eliminar(String socio) {
    if (first == null) {
        return false;
    }
    if (first.value.equals(socio)) {      // caso 1: es la cabeza
        first = first.next;
        size--;
        return true;
    }
    Node anterior = first;                // casos 2 y 3: buscamos su ANTERIOR
    Node actual = first.next;
    while (actual != null) {
        if (actual.value.equals(socio)) {
            anterior.next = actual.next;  // el anterior se salta a actual
            size--;
            return true;
        }
        anterior = actual;                // avanzan los dos, siempre en pareja
        actual = actual.next;
    }
    return false;                         // no estaba
}

Traza de eliminar("Pablo") sobre Laura -> Pablo -> Marta -> Iván, y de eliminar("Iván"):

Llamada	anterior	actual	¿actual.value.equals(socio)?	Qué pasa
eliminar("Pablo")	Laura	Pablo	Sí	Laura.next = Marta, size--, true
eliminar("Iván"), vuelta 1	Laura	Marta	No	avanzan los dos
eliminar("Iván"), vuelta 2	Marta	Iván	Sí	Marta.next = null, size--, true

El método devuelve true o false en lugar de lanzar una excepción, como suelen pedir los enunciados del examen («devuelve false si no estaba»). El caso 3 (borrar el último) es el mismo código que el caso 2: actual.next vale null y el anterior pasa a ser el último.

La clase completa en acción

La clase ColaReservas entera:

/** Cola de reservas de un libro: una lista enlazada que hereda de ContainerBase. */
public class ColaReservas extends ContainerBase {
    private int size;                         // la llevamos al día para no recorrer

    public void insertarDelante(String socio) {
        Node nuevo = new Node(socio);
        nuevo.next = first;                   // 1. el nuevo apunta a la cabeza actual...
        first = nuevo;                        // 2. ...y pasa a ser la cabeza
        size++;
    }

    public void insertarDetras(String socio) {
        Node nuevo = new Node(socio);
        if (first == null) {                  // lista vacía: el nuevo es la cabeza
            first = nuevo;
        } else {
            Node actual = first;
            while (actual.next != null) {     // paramos EN el último, no después
                actual = actual.next;
            }
            actual.next = nuevo;
        }
        size++;
    }

    public boolean contiene(String socio) {
        for (Node n = first; n != null; n = n.next) {
            if (n.value.equals(socio)) {      // equals: compara el texto, no la dirección
                return true;
            }
        }
        return false;
    }

    public boolean eliminar(String socio) {
        if (first == null) {
            return false;
        }
        if (first.value.equals(socio)) {      // caso 1: es la cabeza
            first = first.next;
            size--;
            return true;
        }
        Node anterior = first;                // casos 2 y 3: buscamos su ANTERIOR
        Node actual = first.next;
        while (actual != null) {
            if (actual.value.equals(socio)) {
                anterior.next = actual.next;  // el anterior se salta a actual
                size--;
                return true;
            }
            anterior = actual;                // avanzan los dos, siempre en pareja
            actual = actual.next;
        }
        return false;                         // no estaba
    }

    public int getSize() {
        return size;
    }
}

Y una prueba que pasa por los tres casos de borrado y por un socio que no está:

public class PruebaCola {
    public static void main(String[] args) {
        ColaReservas cola = new ColaReservas();
        System.out.println("Vacía: " + cola + " | size = " + cola.getSize());
        cola.insertarDetras("Laura");                    // reservas normales: al final
        cola.insertarDetras("Pablo");
        cola.insertarDetras("Marta");
        System.out.println("Reservas: " + cola);
        cola.insertarDelante("Ana");                     // Ana es PDI: pasa delante (norma inventada)
        System.out.println("Ana delante: " + cola);
        cola.insertarDetras("Iván");
        System.out.println("Iván detrás: " + cola + " | size = " + cola.getSize());
        System.out.println("¿Pablo? " + cola.contiene("Pablo") + " | ¿Nora? " + cola.contiene("Nora"));
        System.out.println("Quito a Ana (cabeza): " + cola.eliminar("Ana") + " " + cola);
        System.out.println("Quito a Pablo (medio): " + cola.eliminar("Pablo") + " " + cola);
        System.out.println("Quito a Iván (último): " + cola.eliminar("Iván") + " " + cola);
        System.out.println("Quito a Nora (no está): " + cola.eliminar("Nora") + " | size = " + cola.getSize());
    }
}

Salida:

Vacía: ➡null | size = 0
Reservas: ➡Laura->Pablo->Marta->null
Ana delante: ➡Ana->Laura->Pablo->Marta->null
Iván detrás: ➡Ana->Laura->Pablo->Marta->Iván->null | size = 5
¿Pablo? true | ¿Nora? false
Quito a Ana (cabeza): true ➡Laura->Pablo->Marta->Iván->null
Quito a Pablo (medio): true ➡Laura->Marta->Iván->null
Quito a Iván (último): true ➡Laura->Marta->null
Quito a Nora (no está): false | size = 2

Compruébalo con los dibujos: Ana entra delante sin recorrer nada; Iván detrás, recorriendo cuatro nodos; salen Ana (cabeza), Pablo (medio) e Iván (último), y size termina en 5 − 3 = 2 sin recorrer. Con Nora, que nunca reservó, eliminar devuelve false.

Del Python que ya sabes al Java del examen

Si hiciste el tema de Python, todo esto te sonará. La traducción es casi palabra por palabra:

Python (FP2)	Java (FP2)
self.__primero	first (protected en ContainerBase)
nodo.siguiente	n.next
None	null
while actual is not None:	while (actual != null) o for (Node n = first; n != null; n = n.next)
actual.valor == socio	actual.value.equals(socio)
raise ValueError(...)	Lo habitual en el examen: devolver false, null o -1
__len__ con __longitud	getSize() con private int size
__str__	toString() (ya hecho en ContainerBase)

La diferencia más importante no está en la tabla: en Java todo tiene tipo. Node guarda un String, así que no puedes meter un número en esta cola sin cambiar la clase.

¿Y si los datos no son String?

En el examen te dan un Node hecho para el dato del enunciado: un Box con etiqueta y kilos, un préstamo, un número. La estructura no cambia: solo el tipo de value. En la práctica verás un Node con int value para los días de préstamo.

La versión general sería un nodo genérico, Node<T>, como los de las colecciones que viste en el tema anterior:

public class Node<T> {
    public T value;
    public Node<T> next;
}

Así, Node<String> y Node<Integer> comparten código. En el examen de FP2 se usan nodos con un tipo concreto, que es lo que practicamos aquí; si un enunciado usa <T>, todo lo que ves en este artículo vale igual.

La trampa de Java: == frente a equals

En Python, == entre dos textos compara su contenido. En Java, == entre dos objetos pregunta si son el mismo objeto. Con String eso es una trampa, porque dos textos iguales pueden ser objetos distintos. Esta es la misma cola, pero comparando con ==:

public class PruebaIgual {
    public static void main(String[] args) {
        String escrito = "Pablo";
        String leido = new String("Pablo");      // el mismo texto en OTRO objeto (como lo que llega de un archivo)
        System.out.println(escrito == leido);         // ¿mismo objeto?
        System.out.println(escrito.equals(leido));    // ¿mismo texto?

        ColaMal cola = new ColaMal();
        cola.insertarDetras("Laura");
        cola.insertarDetras(leido);
        System.out.println(cola + " | ¿Pablo? " + cola.contiene("Pablo"));
        System.out.println("Quito a Pablo: " + cola.eliminar("Pablo") + " " + cola);
    }
}

Salida:

false
true
➡Laura->Pablo->null | ¿Pablo? false
Quito a Pablo: false ➡Laura->Pablo->null

El Pablo que entró en la cola se creó con new String (como pasaría si llegara de un archivo o de Scanner), y el "Pablo" que buscamos es otro objeto. == dice que no son el mismo, así que contiene responde false y eliminar no encuentra a nadie, aunque se vea «Pablo» en la cola. Con equals, como en ColaReservas, funciona siempre.

Si first fuera private

¿Por qué protected y no private, que es lo que nos enseñaron para los atributos? Mira qué pasa si en ContainerBase lo cambiamos a private y compilamos la misma ColaReservas:

ColaReservas.java:7: error: first has private access in ContainerBase
        nuevo.next = first;                   // 1. el nuevo apunta a la cabeza actual...
                     ^

…y así hasta 12 errors, uno por cada uso de first. private solo deja usar el atributo dentro de su propia clase, y ColaReservas es otra clase, aunque herede de ella. Con protected, las subclases pueden usarlo. Es el equivalente en Java del problema que en Python daban los atributos con dos guiones bajos.

Errores típicos con listas enlazadas en Java

Míralo paso a paso en Python Tutor

Python Tutor ejecuta Java y dibuja cada objeto con sus flechas: elige Java en el desplegable. Tiene que ser una sola clase pública, así que el nodo va dentro como clase anidada (static class Node). Este programa mete a Ana entre Laura y Pablo:

public class Tutor {
    static class Node {
        String value;
        Node next;

        Node(String value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Node laura = new Node("Laura");
        Node pablo = new Node("Pablo");
        Node marta = new Node("Marta");
        laura.next = pablo;
        pablo.next = marta;
        Node first = laura;

        Node ana = new Node("Ana");    // Ana se cuela entre Laura y Pablo
        ana.next = laura.next;         // 1. enlazar con el resto
        laura.next = ana;              // 2. engancharla

        for (Node n = first; n != null; n = n.next) {
            System.out.println(n.value);
        }
    }
}

Salida:

Laura
Ana
Pablo
Marta

Qué observar paso a paso:

1. Tras los tres new Node, verás tres objetos sueltos con next a null.
2. Con laura.next = pablo y pablo.next = marta aparecen las flechas. Ningún objeto se mueve.
3. En ana.next = laura.next, Ana ya apunta a Pablo y Laura todavía también: dos flechas al mismo nodo.
4. En laura.next = ana cambia una sola flecha. Pablo y Marta no se enteran.
5. Durante el for, mira cómo la variable n salta de objeto en objeto hasta valer null.

Resumen rápido

Operación	Código clave	Coste
Insertar delante	nuevo.next = first; first = nuevo;	O(1)
Insertar detrás	Caso vacía; si no, while (actual.next != null) y actual.next = nuevo	O(n)
Recorrer	for (Node n = first; n != null; n = n.next)	O(n)
Buscar	Recorrer con equals	O(n)
Eliminar	Cabeza aparte; resto con anterior.next = actual.next	O(n)
Tamaño	private int size al día	O(1)

Tres ideas para quedarte:

1. Primero se enlaza, después se mueve. Un orden equivocado deja nodos sin nadie que los apunte.
2. null es el final y también la trampa. Piensa siempre en la lista vacía y en el último nodo.
3. Textos con equals, nodos con ==.

En la práctica de LinkedList en Java programamos tres clases como las del examen: una cola con first y last, una lista ordenada de préstamos con «eliminar todos» y una cola que se da la vuelta sin crear nodos.

Siguiente paso: prácticaLinkedList en Java práctica — la cola de reservas con first y last, los préstamos ordenados y la cola al revés (como en el Examen 3)

¿Te ha servido este artículo? Así puedes apoyar SergioLearns →