LinkedList en Java práctica: cola, lista ordenada e invertir

Práctica Intermedio FP217 min de lectura

Repasando para el Examen 3 programé una cola con first y last que funcionaba de maravilla… hasta que la vacié. verPrimero() decía null, getSize() decía 0 y verUltimo() seguía diciendo Pablo, que ya se había ido hacía rato. Me había olvidado de una línea en el caso de la cola que se queda vacía. Ese caso, el de los extremos, es justo el que miran las pruebas del examen, y lo vas a ver con salida real en el programa 1 y en los ejercicios.

En la teoría de LinkedList en Java vimos el nodo, ContainerBase, insertar, recorrer, eliminar y la trampa de == con los textos. Ahora escribimos tres clases de nivel medio con el molde del examen (Node + ContainerBase + tu clase con extends), con el ejemplo de la biblioteca de la facultad: una cola de reservas que encola y atiende sin recorrer, una lista ordenada de días de préstamo con «eliminar todos» y una cola que se da la vuelta sin crear un solo nodo. Los datos se parecen a los de verdad: valores repetidos, colas vacías y de una persona. Las normas de la biblioteca son inventadas.

Antes de empezar

Conviene tener claro:

El molde: Node con value y next públicos, ContainerBase con protected Node first y un toString() que dibuja ➡A->B->null, y tu clase con extends ContainerBase.
El recorrido: for (Node n = first; n != null; n = n.next).
La regla de oro: primero enlazar, después mover.
Que los textos se comparan con equals y que en el examen no se pueden usar arrays ni colecciones para guardar los datos.

Si alguno te suena dudoso, repasa la teoría antes de seguir.

Pon cada programa en su carpeta con sus cuatro archivos (Node.java, ContainerBase.java, tu clase y la clase de prueba con main) y compílalos juntos con javac *.java. Es lo mismo que hace el entorno del examen.

Programa 1: la cola de reservas con first y last

En la biblioteca, las reservas se atienden en orden de llegada: se encola por detrás y se atiende por delante. Con solo first, encolar obliga a recorrer toda la cola. Queremos las dos operaciones instantáneas, más verPrimero(), verUltimo() y getSize(). Lo que lo complica: la cola vacía y la cola de una sola persona, donde first y last son el mismo nodo.

La idea

Guardamos dos referencias: first (heredada) para atender y last (nuestra, private) para encolar. Encolar engancha el nuevo detrás de last y lo convierte en el nuevo last. Atender mueve first al segundo. Los casos especiales salen de una pregunta: ¿qué tienen que valer first y last cuando la cola está vacía? Los dos null. Por eso, si al encolar está vacía, el nuevo es el primero y el último; y si al atender se queda vacía, last también pasa a null.

Antes de programar, dibuja la cola con un nodo y pregúntate qué cambia en first, last y size al atenderlo.

El código

/** Cola de reservas con first y last: encolar por detrás y atender por delante, las dos sin recorrer. */
public class ColaRapida extends ContainerBase {
    private Node last;                        // el último nodo: así no hay que recorrer para encolar
    private int size;

    public void encolar(String socio) {
        Node nuevo = new Node(socio);
        if (first == null) {                  // cola vacía: el nuevo es el primero Y el último
            first = nuevo;
        } else {
            last.next = nuevo;                // el último de antes apunta al nuevo...
        }
        last = nuevo;                         // ...y el nuevo pasa a ser el último
        size++;
    }

    public String atender() {
        if (first == null) {
            return null;                      // nadie a quien atender
        }
        String socio = first.value;
        first = first.next;
        if (first == null) {                  // se ha quedado vacía: last también a null
            last = null;
        }
        size--;
        return socio;
    }

    public String verPrimero() {
        return first == null ? null : first.value;
    }

    public String verUltimo() {
        return last == null ? null : last.value;
    }

    public int getSize() {
        return size;
    }
}

Y la prueba:

public class PruebaRapida {
    public static void main(String[] args) {
        ColaRapida cola = new ColaRapida();
        System.out.println("Atender en vacía: " + cola.atender());
        cola.encolar("Laura");
        cola.encolar("Pablo");
        cola.encolar("Marta");
        System.out.println(cola + " | primero " + cola.verPrimero() + ", último " + cola.verUltimo() + ", size " + cola.getSize());
        System.out.println("Atiendo a " + cola.atender() + ": " + cola);
        System.out.println("Atiendo a " + cola.atender() + ": " + cola);
        System.out.println("Atiendo a " + cola.atender() + ": " + cola);
        System.out.println("Vacía: primero " + cola.verPrimero() + ", último " + cola.verUltimo() + ", size " + cola.getSize());
        cola.encolar("Nora");
        System.out.println("Llega Nora: " + cola + " | primero " + cola.verPrimero() + ", último " + cola.verUltimo());
    }
}

Salida

Atender en vacía: null
➡Laura->Pablo->Marta->null | primero Laura, último Marta, size 3
Atiendo a Laura: ➡Pablo->Marta->null
Atiendo a Pablo: ➡Marta->null
Atiendo a Marta: ➡null
Vacía: primero null, último null, size 0
Llega Nora: ➡Nora->null | primero Nora, último Nora

Con last, encolar no recorre nada. El precio: dos referencias que mantener, y la cola vacía es el caso que se olvida.

Fíjate en las tres últimas líneas: al atender a Marta la cola queda vacía y los dos extremos son null. Cuando llega Nora, encolar ve first == null, la pone como primera y como última, y la cola funciona otra vez. Atender en una cola vacía devuelve null en lugar de lanzar un NullPointerException, que es lo que suelen pedir los enunciados.

Preguntas que te puedes hacer

¿Por qué last es private y first no? first viene de ContainerBase (protected, para que la uses). last es un detalle de tu clase: nadie de fuera debería poder cambiarlo.

¿Por qué en encolar el last = nuevo va fuera del if? Porque en los dos casos el nuevo acaba siendo el último. Solo cambia quién apunta a él: first (cola vacía) o el último de antes.

¿Qué pasa si olvido el last = null de atender? Que la cola vacía sigue «recordando» a la última persona. Lo verás con salida real en el fragmento 3 de los ejercicios.

¿No debería atender devolver el nodo? No: los nodos son un detalle interno. Quien usa la cola quiere el dato (el nombre), así que devolvemos String.

Tratar la cola de un solo nodo como una más. Es la que hace que first y last coincidan, y la que rompe los programas cuando se vacía.

Pruébalo tú

Añade colarse(String socio), que inserte por delante (el PDI). ¿Hay que tocar last en algún caso?
Escribe atenderVarios(int n) que atienda a n personas y devuelva cuántas ha atendido de verdad.

Programa 2: la lista ordenada de préstamos y «eliminar todos»

La biblioteca guarda cuántos días duró cada préstamo y quiere tenerlos siempre ordenados de menor a mayor, para ver de un vistazo los más cortos y los más largos. También quiere quitar todos los préstamos de una duración (por ejemplo, los de 8 días, que eran una promoción). Lo que lo complica: hay valores repetidos, y los que se quitan pueden estar seguidos y al principio.

La idea

insertarOrdenado: si la lista está vacía o el dato va delante de la cabeza, es un «insertar delante». Si no, buscamos el último nodo menor que el dato y enganchamos el nuevo detrás de él.
eliminarTodos: primero se quitan los de la cabeza con un while (puede haber varios seguidos). Después, con una referencia anterior, se mira siempre anterior.next: si hay que borrarlo, nos lo saltamos y anterior no avanza, porque su nuevo siguiente todavía no se ha mirado.

Antes de programar, piensa por qué el bucle mira actual.next.value y no actual.value: tienes que pararte en el nodo anterior al hueco.

El código

Esta vez Node guarda un int:

public class Node {
    public int value;        // el dato: días que duró un préstamo
    public Node next;        // el siguiente nodo (null si es el último)

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

/** Días que duró cada préstamo, siempre de menor a mayor. */
public class ListaDias extends ContainerBase {
    private int size;

    public void insertarOrdenado(int dias) {
        Node nuevo = new Node(dias);
        if (first == null || dias <= first.value) {          // caso 1: vacía, o va delante de todos
            nuevo.next = first;
            first = nuevo;
        } else {
            Node actual = first;
            while (actual.next != null && actual.next.value < dias) {
                actual = actual.next;                        // paramos en el ÚLTIMO menor que dias
            }
            nuevo.next = actual.next;                        // 1. el nuevo apunta al resto...
            actual.next = nuevo;                             // 2. ...y actual apunta al nuevo
        }
        size++;
    }

    public int eliminarTodos(int dias) {
        int borrados = 0;
        while (first != null && first.value == dias) {      // los de la cabeza (puede haber varios seguidos)
            first = first.next;
            borrados++;
        }
        if (first != null) {
            Node anterior = first;
            while (anterior.next != null) {
                if (anterior.next.value == dias) {
                    anterior.next = anterior.next.next;      // saltamos el siguiente; anterior NO avanza
                    borrados++;
                } else {
                    anterior = anterior.next;
                }
            }
        }
        size -= borrados;
        return borrados;
    }

    public int getSize() {
        return size;
    }
}

El trozo delicado de insertarOrdenado es la condición del while: primero actual.next != null y después actual.next.value < dias. Si las cambias de orden, en el último nodo Java evalúa null.value y lanza NullPointerException. Y las dos líneas finales siguen la regla de oro: el nuevo apunta al resto antes de que actual apunte al nuevo.

La prueba usa un array solo para preparar los datos; la lista no lo usa por dentro:

public class PruebaDias {
    public static void main(String[] args) {
        ListaDias lista = new ListaDias();
        int[] llegadas = {15, 8, 42, 3, 27, 8, 19, 8};     // solo para la prueba: la lista no usa el array
        for (int d : llegadas) {
            lista.insertarOrdenado(d);
            System.out.println("Inserto " + d + ": " + lista);
        }
        System.out.println("Quito los de 8: " + lista.eliminarTodos(8) + " -> " + lista + " | size " + lista.getSize());
        System.out.println("Quito los de 3: " + lista.eliminarTodos(3) + " -> " + lista);
        System.out.println("Quito los de 100: " + lista.eliminarTodos(100) + " -> " + lista + " | size " + lista.getSize());
    }
}

Salida

Inserto 15: ➡15->null
Inserto 8: ➡8->15->null
Inserto 42: ➡8->15->42->null
Inserto 3: ➡3->8->15->42->null
Inserto 27: ➡3->8->15->27->42->null
Inserto 8: ➡3->8->8->15->27->42->null
Inserto 19: ➡3->8->8->15->19->27->42->null
Inserto 8: ➡3->8->8->8->15->19->27->42->null
Quito los de 8: 3 -> ➡3->15->19->27->42->null | size 5
Quito los de 3: 1 -> ➡15->19->27->42->null
Quito los de 100: 0 -> ➡15->19->27->42->null | size 4

Comprobemos el paso del 27: la lista es 3 -> 8 -> 15 -> 42; actual empieza en 3; como 8 < 27 avanza a 8, como 15 < 27 avanza a 15, y como 42 ya no es < 27 se para en 15 y el 27 queda entre 15 y 42. Al quitar los de 8 salen tres (estaban seguidos, en medio), size pasa de 8 a 5. Al quitar el 3 se borra la cabeza con el primer while. Y con 100 no se borra nada y size se queda en 4.

Traza de eliminarTodos(8) sobre 3 -> 8 -> 8 -> 8 -> 15:

Vuelta	`anterior`	`anterior.next`	¿Es 8?	Qué pasa
1	3	8 (primero)	Sí	3 se salta al segundo 8, `anterior` quieto
2	3	8 (segundo)	Sí	3 se salta al tercero
3	3	8 (tercero)	Sí	3 apunta a 15
4	3	15	No	`anterior` avanza a 15

Preguntas que te puedes hacer

¿Por qué <= en el caso de la cabeza y < en el bucle? Para que un valor igual a la cabeza entre delante sin recorrer. Con valores repetidos, el orden entre iguales no importa.

¿Por qué el primer while de eliminarTodos es un while y no un if? Porque puede haber varios iguales seguidos al principio (3, 3, 3…). Con un if solo quitarías el primero.

¿Por qué size -= borrados al final y no size-- dentro? Da lo mismo; contar los borrados además sirve para devolverlos, que es lo que pide el método.

¿Y si en la cola hubiera String? El mismo esquema, comparando con equals y, para ordenar, con compareTo (que ya viste en el tema de Comparable).

Avanzar anterior también cuando borras. Con dos valores iguales seguidos, el segundo se queda.

Pruébalo tú

Añade mediana() que devuelva el valor del centro sin usar size para nada más que saber cuántos saltar.
Escribe insertarSinRepetir(int dias), que no inserte un valor que ya está (aprovecha que la lista está ordenada para parar antes).

Programa 3: dar la vuelta a la cola sin crear nodos

Por último, la biblioteca quiere avisar a la cola de reservas del último al primero (otra norma inventada; el problema es un clásico de examen). Hay que invertir la propia lista, reutilizando los mismos nodos. Lo que lo complica: cambiar todas las flechas sin perder el camino, con la cola vacía o de una persona.

La idea

Tres referencias: anterior (empieza en null), actual (empieza en first) y siguiente. En cada vuelta: guardar siguiente = actual.next, girar la flecha actual.next = anterior y avanzar las dos. Al final, first = anterior.

Al final del bucle actual es null. ¿Dónde está entonces la antigua cola, la nueva cabeza?

El código

/** Cola de reservas que se puede dar la vuelta sin crear nodos nuevos. */
public class ColaInvertible extends ContainerBase {

    public void insertarDetras(String socio) {
        Node nuevo = new Node(socio);
        if (first == null) {
            first = nuevo;
            return;
        }
        Node actual = first;
        while (actual.next != null) {
            actual = actual.next;
        }
        actual.next = nuevo;
    }

    public void invertir() {
        Node anterior = null;
        Node actual = first;
        while (actual != null) {
            Node siguiente = actual.next;     // 1. guardar el resto ANTES de tocar nada
            actual.next = anterior;           // 2. darle la vuelta a la flecha
            anterior = actual;                // 3. avanzar anterior...
            actual = siguiente;               // 4. ...y actual
        }
        first = anterior;                     // la nueva cabeza es la antigua cola
    }
}

public class PruebaInvertir {
    public static void main(String[] args) {
        ColaInvertible cola = new ColaInvertible();
        cola.invertir();
        System.out.println("Vacía invertida: " + cola);
        cola.insertarDetras("Laura");
        cola.invertir();
        System.out.println("Un nodo invertido: " + cola);
        cola.insertarDetras("Pablo");
        cola.insertarDetras("Marta");
        cola.insertarDetras("Iván");
        System.out.println("Cola: " + cola);
        cola.invertir();
        System.out.println("Invertida: " + cola);
        cola.invertir();
        System.out.println("Otra vez: " + cola);
    }
}

Salida

Vacía invertida: ➡null
Un nodo invertido: ➡Laura->null
Cola: ➡Laura->Pablo->Marta->Iván->null
Invertida: ➡Iván->Marta->Pablo->Laura->null
Otra vez: ➡Laura->Pablo->Marta->Iván->null

Cada vuelta da la vuelta a una sola flecha. Si no guardas antes el siguiente, al girarla pierdes el camino hacia el resto de la cola.

La cola vacía y la de un nodo salen bien sin ningún if: con first a null el while no entra, y con un nodo da una vuelta que apunta a Laura a null, lo que ya hacía. Invertir dos veces deja la cola como estaba.

Ahora el mismo método con las dos primeras líneas del bucle cambiadas de orden:

public void invertir() {
    Node anterior = null;
    Node actual = first;
    while (actual != null) {
        actual.next = anterior;           // MAL: damos la vuelta a la flecha primero...
        Node siguiente = actual.next;     // ...y "el resto" ya es anterior
        anterior = actual;                // 3. avanzar anterior...
        actual = siguiente;               // 4. ...y actual
    }
    first = anterior;                     // la nueva cabeza es la antigua cola
}

Vacía invertida: ➡null
Un nodo invertido: ➡Laura->null
Cola: ➡Laura->Pablo->Marta->Iván->null
Invertida: ➡Laura->null
Otra vez: ➡Laura->null

En la primera vuelta, actual.next = anterior deja a Laura apuntando a null y, después, siguiente = actual.next guarda… null. El bucle acaba, first pasa a Laura y Pablo, Marta e Iván se quedan sin nadie que los apunte. No hay ningún error en rojo: solo una cola que ha perdido a tres personas.

Preguntas que te puedes hacer

¿Por qué siguiente se declara dentro del bucle? Porque solo hace falta durante una vuelta. Declararla fuera también funciona.

¿Hace falta tocar size? No: invertir no añade ni quita nodos. Esta clase ni siquiera lo guarda.

¿Se podría hacer con recursión? Sí, pero cada nodo es una llamada en la pila: con una lista muy larga, StackOverflowError. La iterativa no tiene ese límite.

¿Y crear una lista nueva insertando delante? También invierte, pero crea un nodo por elemento. Si el enunciado dice «sin crear nodos», es la de las tres referencias.

Girar la flecha antes de guardar el siguiente. El programa no falla: simplemente pierde el resto de la cola.

Pruébalo tú

Añade invertirDesde(int pos), que invierta solo a partir de una posición.
Escribe esCapicua() sin colecciones: invierte una copia (créala recorriendo y usando insertarDelante) y compara nodo a nodo con equals.

El patrón que debes llevarte

Patrón	Cuándo	Esqueleto
Dos extremos	Colas: entrar por detrás, salir por delante	`last.next = nuevo; last = nuevo;` y `first = first.next;` (+ `last = null` si se vacía)
Pararse en el anterior	Insertar en orden, borrar con condición	`while (anterior.next != null)` y saltar `anterior.next`
Tres referencias	Girar flechas	`siguiente = actual.next; actual.next = anterior; …`

Errores típicos en esta práctica

No poner last = null cuando la cola se vacía. verUltimo() miente.
Cambiar el orden de la condición actual.next != null && actual.next.value < x. NullPointerException en el último nodo.
Usar if en vez de while para quitar los de la cabeza. Se quedan los repetidos del principio.
Avanzar anterior también al borrar. Se quedan los repetidos seguidos.
Girar una flecha sin guardar antes el siguiente. La cola se queda en un nodo.
Guardar los datos en un array «para ordenar más fácil». Prohibido en el examen.

Míralo paso a paso en Python Tutor

Entra en Python Tutor, elige Java y pega esta versión mínima de la cola con first y last:

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

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

    public static void main(String[] args) {
        Node first = null;
        Node last = null;
        String[] llegan = {"Laura", "Pablo", "Marta"};
        for (String socio : llegan) {          // encolar: siempre por detrás
            Node nuevo = new Node(socio);
            if (first == null) {
                first = nuevo;
            } else {
                last.next = nuevo;
            }
            last = nuevo;
        }
        String atendido = first.value;          // atender: siempre por delante
        first = first.next;
        System.out.println(atendido + " | primero " + first.value + " | último " + last.value);
    }
}

Salida:

Laura | primero Pablo | último Marta

Qué observar paso a paso:

En la primera vuelta del for, first y last apuntan al mismo nodo, Laura.
En la segunda, cambia la flecha de Laura (last.next = nuevo) y después last salta a Pablo; first no se mueve.
Al terminar el for, first está en Laura y last en Marta, sin haber recorrido nada.
Al atender, solo cambia first. Laura se queda sin nadie que la apunte.

Resumen y siguiente paso

Con first y last, encolar y atender son instantáneos, pero hay que mantener los dos.
La cola vacía es el caso que rompe las colas: los dos extremos a null.
Para insertar en orden o borrar con condición, te paras en el anterior.
anterior no avanza cuando borras.
Invertir en el sitio son tres referencias y un orden fijo: guardar, girar, avanzar.
Prueba siempre la lista vacía, la de un nodo y los repetidos seguidos.

Checklist: ¿lo has practicado?

¿Has ejecutado los tres programas y comprobado las salidas?
¿Sabes qué valen first, last y size justo después de atender a la última persona?
¿Puedes explicar por qué el primer bucle de eliminarTodos es un while?
¿Puedes escribir de memoria las cuatro líneas del bucle de inversión?
¿Has intentado los «Pruébalo tú» sin mirar la teoría?

Si has respondido que sí a casi todo, estás listo para los ejercicios de LinkedList en Java, donde ya no te doy el código hecho. ¡Nos vemos allí!

Siguiente paso: ejerciciosLinkedList en Java ejercicios — la reserva de la posición N, los socios repetidos y la cola partida por la mitad (con soluciones y chuletario)

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