TAD Lista: Estáticas, Dinámicas y Enlazadas

Desde acá el curso cambia de tema. Ya sabés modelar objetos y, en la lección Arrays de Objetos: Guardar y Recorrer Muchas Instancias, ya guardaste muchos en un array con su contador de cantidad. Ahora vas a formalizar esa idea y —esto es lo importante— a elegir la organización correcta según lo que vayas a hacer con los datos.

Empecemos con una pregunta que parece tonta: si ya existe ArrayList, ¿para qué implementar una lista a mano?

Porque ArrayList es rapidísimo para algunas cosas y desastroso para otras, y si no sabés por qué, vas a elegir mal. Implementarla una vez es lo que te enseña esa diferencia para siempre.

1. Qué es un TAD

Un Tipo Abstracto de Dato es la separación entre dos cosas que solemos mezclar:

• La especificación: qué operaciones ofrece y qué garantiza cada una. El qué.
• La implementación: cómo se guardan los datos en memoria y cómo se ejecuta cada operación. El cómo.

En Java el TAD se escribe como una interfaz —justo lo que viste en la lección Clases Abstractas, Interfaces y Organización del Código—:

public interface Lista<T> {
    void agregar(T dato);
    boolean eliminar(T dato);
    T obtener(int indice);
    int tamanio();
    boolean estaVacia();
}

Quien programa contra Lista<T> no sabe ni le importa si adentro hay un arreglo o una cadena de nodos. Esa ignorancia es exactamente el objetivo.

2. Dos formas de guardar lo mismo, con costos opuestos

Quedate con esta idea, porque es la que ordena todo lo que viene:

El arreglo paga la inserción para que la lectura sea gratis. La lista enlazada paga la lectura para que la inserción sea gratis.

3. El nodo: la clase más importante de la lección

Un nodo es un objeto minúsculo con dos cosas: un dato y una referencia al nodo siguiente.

public class Nodo<T> {
    T dato;
    Nodo<T> siguiente;   // ← una referencia a otro Nodo, del mismo tipo

    public Nodo(T dato) {
        this.dato = dato;
        this.siguiente = null;   // por defecto no apunta a nadie
    }
}

Esa línea Nodo<T> siguiente; es la que suele trabar a todo el mundo: una clase que se referencia a sí misma. No hay ninguna recursión infinita ahí. Acordate de la lección Fundamentos de POO: Clases, Objetos y Atributos: un atributo de tipo objeto no guarda el objeto, guarda una referencia (o null). Un nodo no contiene a otro nodo: sabe dónde encontrarlo.

4. Lista enlazada simple, paso a paso

La lista completa se reduce a una sola referencia: la que apunta al primer nodo.

public class ListaEnlazada<T> {
    private Nodo<T> cabeza;   // si es null, la lista está vacía
    private int tamanio;

    public boolean estaVacia() { return cabeza == null; }
    public int tamanio() { return tamanio; }
}

agregarAlInicio: el baile de referencias

Estas tres líneas son el corazón de toda la estructura, y el orden entre ellas no es negociable:

public void agregarAlInicio(T dato) {
    Nodo<T> nuevo = new Nodo<>(dato);
    nuevo.siguiente = cabeza;   // 2. el nuevo engancha lo que había
    cabeza = nuevo;             // 3. la lista adopta al nuevo como primero
    tamanio++;
}

Si invertís las dos últimas líneas, cabeza pasa a apuntar al nodo nuevo antes de que nadie guarde dónde estaba el viejo primero. Esa referencia se pierde, y con ella toda la lista. Compila perfecto. Se rompe en silencio.

Recorrer: el patrón que vas a repetir toda tu vida

public void mostrar() {
    Nodo<T> actual = cabeza;          // un puntero temporal, nunca movemos cabeza
    while (actual != null) {
        System.out.print(actual.dato + " → ");
        actual = actual.siguiente;    // el paso que evita el bucle infinito
    }
    System.out.println("null");
}

Nunca uses cabeza como variable de recorrido. Si la movés, perdés el principio de la lista y no hay vuelta atrás. Siempre una variable auxiliar.

Agregar al final

public void agregarAlFinal(T dato) {
    Nodo<T> nuevo = new Nodo<>(dato);
    if (cabeza == null) {             // caso especial: lista vacía
        cabeza = nuevo;
        tamanio++;
        return;
    }
    Nodo<T> actual = cabeza;
    while (actual.siguiente != null) {   // ojo: siguiente != null, no actual != null
        actual = actual.siguiente;       // hay que caminar TODA la lista
    }
    actual.siguiente = nuevo;
    tamanio++;
}

Fijate la diferencia con el recorrido anterior: acá la condición es actual.siguiente != null, porque queremos quedarnos parados en el último nodo, no pasarnos a null. Es un error clásico.

Y notá el costo: agregar al final recorre la lista entera. Es la debilidad de la enlazada simple, y se resuelve guardando también una referencia cola.

5. Variantes: doble y circular

En la doblemente enlazada, el nodo suma una referencia hacia atrás:

public class NodoDoble<T> {
    T dato;
    NodoDoble<T> siguiente;
    NodoDoble<T> anterior;   // el que la vuelve reversible
}

Con eso podés recorrer para atrás y, sobre todo, eliminar un nodo teniendo solo ese nodo, sin recorrer nada para encontrar al anterior. Es lo que usa LinkedList de Java internamente.

En la circular, el último apunta al primero. Sirve para turnos rotativos, buffers y reproductores en modo repetición. El recorrido cambia de forma:

// En una lista circular, esto sería un bucle infinito:
// while (actual != null) { ... }

Nodo<T> actual = cabeza;
do {
    System.out.print(actual.dato + " → ");
    actual = actual.siguiente;
} while (actual != cabeza);   // el corte es volver al punto de partida

6. La tabla que decide

Y la conclusión práctica, que es la que importa:

En el 95 % de los casos usá ArrayList. Los recorridos secuenciales sobre memoria contigua son muchísimo más rápidos de lo que la tabla sugiere, porque el procesador precarga bloques enteros de memoria contigua en su caché. Una LinkedList con nodos dispersos pierde esa ventaja por completo.

LinkedList gana cuando insertás y eliminás constantemente en los extremos y casi nunca accedés por índice. Ese caso existe —lo vas a ver en la próxima lección, con pilas y colas— pero es minoritario.

7. Errores frecuentes

8. Ejercicio práctico guiado

Desafío: eliminar(T dato) en la lista enlazada simple

Implementá eliminar de forma que:

1. Devuelva true si eliminó algo y false si el dato no estaba.
2. Funcione cuando la lista está vacía.
3. Funcione cuando el elemento a borrar es la cabeza.
4. Funcione cuando está en el medio o al final.
5. Actualice tamanio correctamente.

Pensá los cuatro casos antes de escribir. Ahí está toda la dificultad del ejercicio.

public class ListaEnlazada<T> {
    private Nodo<T> cabeza;
    private int tamanio;

    public void agregarAlInicio(T dato) {
        Nodo<T> nuevo = new Nodo<>(dato);
        nuevo.siguiente = cabeza;
        cabeza = nuevo;
        tamanio++;
    }

    public boolean eliminar(T dato) {
        // CASO 1: lista vacía. Sin esto, la línea siguiente explota.
        if (cabeza == null) {
            return false;
        }

        // CASO 2: el elemento buscado es la cabeza.
        // Es distinto porque no hay un nodo "anterior" al que reengancharle.
        if (java.util.Objects.equals(cabeza.dato, dato)) {
            cabeza = cabeza.siguiente;   // la lista arranca en el segundo
            tamanio--;
            return true;
        }

        // CASO 3 y 4: medio o final.
        // Nos paramos SIEMPRE un nodo antes del candidato, porque para
        // desenganchar un nodo hay que modificar el 'siguiente' del anterior.
        Nodo<T> anterior = cabeza;
        while (anterior.siguiente != null) {
            if (java.util.Objects.equals(anterior.siguiente.dato, dato)) {
                anterior.siguiente = anterior.siguiente.siguiente;   // el salto
                tamanio--;
                return true;
            }
            anterior = anterior.siguiente;
        }

        // Recorrimos todo y no estaba.
        return false;
    }

    public void mostrar() {
        Nodo<T> actual = cabeza;
        StringBuilder sb = new StringBuilder();
        while (actual != null) {
            sb.append(actual.dato).append(" → ");
            actual = actual.siguiente;
        }
        System.out.println(sb.append("null").append("  (tamaño ").append(tamanio).append(")"));
    }

    public static void main(String[] args) {
        ListaEnlazada<Integer> lista = new ListaEnlazada<>();
        lista.agregarAlInicio(30);
        lista.agregarAlInicio(20);
        lista.agregarAlInicio(10);
        lista.mostrar();                                    // 10 → 20 → 30 → null  (tamaño 3)

        System.out.println(lista.eliminar(20));  // true  — caso medio
        lista.mostrar();                                    // 10 → 30 → null  (tamaño 2)

        System.out.println(lista.eliminar(10));  // true  — caso cabeza
        lista.mostrar();                                    // 30 → null  (tamaño 1)

        System.out.println(lista.eliminar(99));  // false — no estaba
        System.out.println(lista.eliminar(30));  // true  — último elemento
        lista.mostrar();                                    // null  (tamaño 0)

        System.out.println(lista.eliminar(1));   // false — lista vacía
    }
}

Para llevarte

• Un TAD separa el qué (la especificación) del cómo (la implementación). En Java el qué se escribe como una interfaz.
• Arreglo y lista enlazada tienen costos inversos: uno paga la inserción para que la lectura sea gratis, el otro al revés.
• Un nodo es un objeto con un dato y una referencia a otro nodo. No lo contiene: sabe dónde está.
• En agregarAlInicio, el orden de las dos asignaciones no es negociable: enganchar primero, mover cabeza después.
• Recorré siempre con una variable auxiliar; mover cabeza destruye la lista.
• Los cuatro casos de toda operación son: lista vacía, primer elemento, elemento del medio, elemento inexistente.
• La doble permite ir para atrás y borrar sin buscar al anterior; la circular no tiene null y cambia la condición de corte.
• En producción, ArrayList casi siempre. La memoria contigua le gana a la teoría gracias a la caché del procesador.