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

En un simulacro del Examen 3 escribí eliminarDuplicados comparando con ==. Lo probé con nombres escritos en el main y funcionó a la primera. Las pruebas del profesor leían los nombres de un archivo y mi método no borró ni uno. Era la trampa de == con los String que vimos en la teoría, y la vas a ver con salida real en el fragmento 1 de «¿Qué falla aquí?».

Ya has visto la teoría y has practicado con tres programas de la biblioteca. Ahora te toca a ti. Tres ejercicios en tres niveles sobre la misma cola de reservas de la biblioteca de la facultad: leer la reserva de una posición y buscar la posición de un socio, quitar los socios repetidos sin colecciones y partir la cola por la mitad en un solo recorrido. Los tres atacan los errores que más puntos quitan en el examen de estructuras encadenadas: avanzar un nodo de más, comparar textos con == y olvidar un extremo.

Cómo usar este artículo: intenta cada ejercicio por tu cuenta; si llevas más de diez minutos atascado, abre la pista; antes de mirar la solución, haz «¿Qué falla aquí?», y pega tu código en Python Tutor (eligiendo Java) para ver las flechas. Al final tienes un cuestionario tipo examen y el chuletario del tema.

Los tres ejercicios usan el molde del examen: los mismos Node y ContainerBase de la teoría (con first protected) y tu clase con extends ContainerBase, que lleva su propio size e insertarDetras (el mismo de la teoría). Recuerda la norma: nada de arrays ni colecciones para guardar los datos; en las pruebas solo los usamos para preparar los nombres.

LinkedList en Java ejercicios: nivel básico

Ejercicio 1: obtener la reserva de una posición y buscar a un socio

Escribe la clase ColaBuscable con dos métodos:

• String obtener(int pos): el socio de esa posición, empezando en 0 por la cabeza. Si la posición no existe (negativa o mayor o igual que size), devuelve null.
• int indiceDe(String socio): la posición de la primera aparición del socio, o -1 si no está. Tiene que funcionar aunque el texto sea otro objeto (new String("Marta")).

Con la cola vacía y después con Laura -> Pablo -> Marta -> Pablo, la salida tiene que ser:

Vacía: obtener(0) = null, indiceDe("Laura") = -1
➡Laura->Pablo->Marta->Pablo->null
obtener(0) = Laura, obtener(2) = Marta, obtener(3) = Pablo
obtener(4) = null, obtener(-1) = null
indiceDe("Pablo") = 1, indiceDe("Nora") = -1
indiceDe(new String("Marta")) = 2

LinkedList en Java ejercicios: nivel intermedio

Ejercicio 2: eliminar los socios repetidos sin colecciones

Hay socios que reservan el mismo libro dos y tres veces. Escribe la clase ColaSinRepetidos con int eliminarDuplicados(), que deje solo la primera aparición de cada socio, modificando la propia cola (sin crear otra), mantenga size correcto y devuelva cuántos ha borrado. Sin HashSet, sin ArrayList y sin arrays: el examen no los deja.

Salida esperada con estas cuatro colas:

➡Laura->Pablo->Laura->Marta->Pablo->Iván->Laura->null  =>  ➡Laura->Pablo->Marta->Iván->null (borrados 3, size 4)
➡Ana->Nora->Iván->null  =>  ➡Ana->Nora->Iván->null (borrados 0, size 3)
➡Marta->Marta->Marta->Marta->null  =>  ➡Marta->null (borrados 3, size 1)
➡null  =>  ➡null (borrados 0, size 0)

LinkedList en Java ejercicios: desafío final

Ejercicio 3: partir la cola por la mitad en un solo recorrido

La biblioteca abre un segundo mostrador y quiere repartir la cola de reservas en dos: la primera mitad se queda en el mostrador de siempre y la segunda pasa al nuevo, en el mismo orden. Si la cola tiene un número impar de personas, la del medio se queda en el primero.

Escribe ColaPartible partirPorLaMitad(), que corte la propia cola y devuelva otra ColaPartible con la segunda mitad, con los dos size correctos. La condición del desafío: un solo recorrido y sin usar size para buscar la mitad, ni crear nodos nuevos.

Salida esperada:

➡Laura->Pablo->Marta->Iván->Nora->null  =>  ➡Laura->Pablo->Marta->null (3) + ➡Iván->Nora->null (2)
➡Laura->Pablo->Marta->Iván->null  =>  ➡Laura->Pablo->null (2) + ➡Marta->Iván->null (2)
➡Ana->null  =>  ➡Ana->null (1) + ➡null (0)
➡null  =>  ➡null (0) + ➡null (0)

¿Qué falla aquí?

Tres fragmentos con un error de los que caen en los exámenes. Predice qué imprime cada uno antes de leer la explicación.

Fragmento 1: los repetidos que no se van

eliminarDuplicados con una sola diferencia: compara con ==.

public int eliminarDuplicados() {
    int borrados = 0;
    for (Node actual = first; actual != null; actual = actual.next) {
        Node anterior = actual;                       // buscamos copias de actual DETRÁS de él
        while (anterior.next != null) {
            if (anterior.next.value == actual.value) {
                anterior.next = anterior.next.next;   // saltamos la copia; anterior NO avanza
                borrados++;
            } else {
                anterior = anterior.next;
            }
        }
    }
    size -= borrados;
    return borrados;
}

La prueba mete los mismos tres nombres en dos colas: en una con los literales tal cual y en la otra con new String(s), como si llegaran de un archivo o del teclado:

public class PruebaMal {
    public static void main(String[] args) {
        ColaSinRepetidos escritos = new ColaSinRepetidos();
        ColaSinRepetidos leidos = new ColaSinRepetidos();
        for (String s : new String[] {"Laura", "Pablo", "Laura"}) {
            escritos.insertarDetras(s);               // literales: Java reutiliza el mismo objeto
            leidos.insertarDetras(new String(s));     // como si llegaran de un archivo: objetos distintos
        }
        System.out.println("Escritos: borrados " + escritos.eliminarDuplicados() + " -> " + escritos);
        System.out.println("Leídos:   borrados " + leidos.eliminarDuplicados() + " -> " + leidos);
    }
}

Escritos: borrados 1 -> ➡Laura->Pablo->null
Leídos:   borrados 0 -> ➡Laura->Pablo->Laura->null

Qué falla: == compara referencias. Los literales iguales que escribes en el código son el mismo objeto (Java los reutiliza), así que en la primera cola el truco «funciona». En la segunda, cada new String es un objeto distinto y == dice que Laura no es Laura: no se borra nada. Es justo mi simulacro: las pruebas no siempre usan literales. Arreglo: anterior.next.value.equals(actual.value).

Fragmento 2: el contador que se queda corto

public int contar() {
    int total = 0;
    Node n = first;
    while (n.next != null) {              // MAL: se para ANTES del último
        total++;
        n = n.next;
    }
    return total;
}

Se prueba con Laura -> Pablo -> Marta y después con una cola vacía:

➡Laura->Pablo->Marta->null tiene 2 nodos
Exception in thread "main" java.lang.NullPointerException: Cannot read field "next" because "n" is null
        at ColaContar.contar(ColaContar.java:12)
        at PruebaContar.main(PruebaContar.java:9)

Qué falla: dos cosas, por la misma condición. while (n.next != null) se para en el último nodo sin contarlo: con tres nodos da 2. Y con la cola vacía, n ya es null antes de entrar, así que n.next lanza el NullPointerException de la línea 12 de ColaContar.java, la del while. Fíjate en que el mensaje de Java te dice exactamente qué era null: "n". Arreglo: while (n != null), que cuenta todos y con la cola vacía no entra.

Fragmento 3: la cola vacía que recuerda a alguien

El atender de la cola con first y last de la práctica, con una línea de menos:

public String atender() {
    if (first == null) {
        return null;                      // nadie a quien atender
    }
    String socio = first.value;
    first = first.next;
    size--;
    return socio;
}

Se encola a Laura y a Pablo y se atiende a los dos:

Vacía: ➡null | primero null, último Pablo, size 0

Qué falla: al atender al último, first pasa a null pero last sigue apuntando a Pablo. La cola dice estar vacía (➡null, size 0) y a la vez tener un último. Hasta aquí solo miente; lo grave llega con el siguiente encolar: como first == null, pone el nuevo como primero y último y todo vuelve a cuadrar por casualidad. Pero si otro método tuyo usa last antes (por ejemplo, un verUltimo() en las pruebas del examen), falla la prueba. Arreglo: tras first = first.next;, if (first == null) last = null;.

Soluciones comentadas

Solución ejercicio 1

public String obtener(int pos) {
    if (pos < 0 || pos >= size) {         // validamos ANTES de movernos
        return null;
    }
    Node actual = first;
    for (int i = 0; i < pos; i++) {       // pos saltos desde la cabeza
        actual = actual.next;
    }
    return actual.value;
}

public int indiceDe(String socio) {
    int pos = 0;
    for (Node n = first; n != null; n = n.next) {
        if (n.value.equals(socio)) {
            return pos;                   // el primero que coincide
        }
        pos++;
    }
    return -1;                            // no está
}

obtener: la validación va antes del bucle porque, si no, con pos igual a size el último salto deja actual a null y actual.value lanza NullPointerException. Con pos negativa el for no daría ninguna vuelta y devolverías la cabeza, que es peor: un resultado falso sin error. Luego, pos saltos: para obtener(2), de Laura a Pablo (i = 0) y de Pablo a Marta (i = 1); con i = 2 el for termina y devolvemos Marta.

indiceDe: el contador pos avanza a la vez que n. El return dentro del bucle hace que devolvamos la primera aparición: con Pablo dos veces, sale 1, no 3. Y como comparamos con equals, new String("Marta") se encuentra en la posición 2.

Solución ejercicio 2

public int eliminarDuplicados() {
    int borrados = 0;
    for (Node actual = first; actual != null; actual = actual.next) {
        Node anterior = actual;                       // buscamos copias de actual DETRÁS de él
        while (anterior.next != null) {
            if (anterior.next.value.equals(actual.value)) {
                anterior.next = anterior.next.next;   // saltamos la copia; anterior NO avanza
                borrados++;
            } else {
                anterior = anterior.next;
            }
        }
    }
    size -= borrados;
    return borrados;
}

El for de fuera recorre la cola con actual. Para cada socio, el while de dentro empieza con anterior = actual y mira siempre anterior.next: si es una copia, la saltamos y anterior no avanza; si no, avanza. Así, cuando actual llega a un nodo, todas sus copias de detrás ya se han ido, y el for sigue con nodos que son la primera aparición de su valor.

Traza con Marta -> Marta -> Marta -> Marta (actual en la primera Marta):

Tres borrados y size 4 − 3 = 1, como en la salida. Con la primera cola, Laura borra sus dos copias, Pablo una y Marta e Iván ninguna: 2 + 1 = 3 borrados y 7 − 3 = 4 nodos.

¿Por qué O(n²)? Cada nodo recorre lo que tiene detrás. Con un HashSet de vistos sería O(n), pero el examen prohíbe las colecciones. Con colas de biblioteca de decenas de personas, da igual.

Solución ejercicio 3

public ColaPartible partirPorLaMitad() {
    ColaPartible segunda = new ColaPartible();
    if (first == null || first.next == null) {     // 0 o 1 nodos: no hay segunda mitad
        return segunda;
    }
    Node lento = first;
    Node rapido = first.next;
    while (rapido != null && rapido.next != null) {
        lento = lento.next;                        // 1 salto
        rapido = rapido.next.next;                 // 2 saltos
    }
    segunda.first = lento.next;                    // la segunda mitad empieza detrás de lento
    lento.next = null;                             // cortamos la cadena
    segunda.size = size / 2;                       // la primera se queda con el de más si es impar
    size = size - segunda.size;
    return segunda;
}

Casos especiales primero: con 0 o 1 nodos no hay segunda mitad, y el bucle no podría arrancar (first.next con first a null lanza NullPointerException). Devolvemos una cola vacía.

El bucle: rapido da dos saltos por cada uno de lento. Como empieza un nodo por delante, cuando rapido ya no puede dar dos saltos, lento está en el último de la primera mitad. Traza con cinco personas:

lento se para en Marta: la segunda mitad empieza en Iván. Con cuatro, rapido acaba en Iván (cuyo next es null) y lento en Pablo: 2 + 2. Fíjate en el dibujo: el corte son dos líneas. Primero la nueva cola guarda lento.next y después lento.next = null corta la cadena (otra vez, primero guardar y después mover).

Los tamaños: la segunda mitad tiene size / 2 (división entera: 5 / 2 = 2) y la primera, el resto (5 − 2 = 3). No hace falta volver a contar.

¿Por qué segunda.first compila? first es protected y estamos dentro de ColaPartible, que hereda de ContainerBase: podemos tocar el first de otro objeto de nuestra misma clase.

Cuestionario tipo examen

Once preguntas como las del examen de estructuras encadenadas de FP2. Contesta sin mirar el artículo y después revisa las explicaciones.

Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
a.next = b;
b.next = c;
Node nuevo = new Node("X");
nuevo.next = a.next;
a.next = nuevo;
String s = "";
for (Node n = a; n != null; n = n.next) {
    s += n.value;
}
System.out.println(s);

public int contar() {
    int total = 0;
    Node n = first;
    while (n.next != null) {
        total++;
        n = n.next;
    }
    return total;
}

Node anterior = null;
Node actual = first;
while (actual != null) {
    Node siguiente = actual.next;
    actual.next = anterior;
    anterior = actual;
    actual = siguiente;
}
first = anterior;
System.out.println(this);

String a = "Pablo";
String b = new String("Pablo");
System.out.println((a == b) + " " + a.equals(b));

Míralo paso a paso en Python Tutor

Entra en Python Tutor, elige Java y pega esta versión del ejercicio 3 con la cola de cinco personas (en Python Tutor todo va en una clase, así que Node va dentro de Tutor):

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

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

    public static void main(String[] args) {
        Node first = new Node("Laura");
        first.next = new Node("Pablo");
        first.next.next = new Node("Marta");
        first.next.next.next = new Node("Iván");
        first.next.next.next.next = new Node("Nora");

        Node lento = first;
        Node rapido = first.next;
        while (rapido != null && rapido.next != null) {
            lento = lento.next;
            rapido = rapido.next.next;
        }
        Node segunda = lento.next;    // Iván
        lento.next = null;            // la primera mitad acaba en Marta
        System.out.println(first.value + " ... " + lento.value + " | " + segunda.value + " ... " + segunda.next.value);
    }
}

Salida:

Laura ... Marta | Iván ... Nora

Qué observar paso a paso:

1. Tras las cinco líneas de next, la cadena va de Laura a Nora y la flecha de Nora es null.
2. Antes del bucle, lento apunta a Laura y rapido a Pablo, un nodo por delante.
3. En cada vuelta, la flecha de lento avanza un nodo y la de rapido, dos. Cuenta los saltos.
4. Cuando rapido pasa a null, lento está en Marta, el tercero.
5. Tras lento.next = null, Python Tutor dibuja dos cadenas separadas: Laura -> Pablo -> Marta y, aparte, Iván -> Nora, que sigue viva porque segunda la apunta.

Chuletario: LinkedList en Java

Lo esencial en 30 segundos: un Node guarda value y next; la lista solo guarda first (protected en ContainerBase) y tu clase hereda con extends. Para insertar, enlaza primero y mueve después. Para borrar, te paras en el anterior. Recorre con for (Node n = first; n != null; n = n.next); para pararte en el último, while (n.next != null). Compara textos con equals. Valida antes de avanzar y prueba siempre la lista vacía y la de un nodo.

Plantillas de los ejercicios:

Antes de entregar, pregúntate:

1. ¿Funciona con la lista vacía y con un solo nodo?
2. ¿Hay algún .value o .next sobre algo que pueda ser null?
3. ¿He enlazado antes de mover en todos los cambios de referencias?
4. ¿Siguen size (y last, si lo tengo) diciendo la verdad después de mi método?
5. ¿He comparado los textos con equals?

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