LinkedList y diferencias con ArrayList

Qué es LinkedList

java.util.LinkedList<E> es una implementación de List, Deque y Queue basada en una lista doblemente enlazada: cada elemento es un nodo que guarda referencias al anterior y al siguiente.

null ← [A] ↔ [B] ↔ [C] ↔ [D] a null
 head tail

Cada nodo es un objeto independiente en el heap. Esto tiene consecuencias profundas en rendimiento y uso de memoria.

Estructura interna

Internamente, LinkedList mantiene:

• Referencia al primer nodo (head).
• Referencia al último nodo (tail).
• Tamaño total.

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

Al añadir al principio/final, solo se ajustan 2-3 punteros. Al eliminar, lo mismo. Pero para acceder a un índice concreto, hay que recorrer desde el extremo más cercano.

Comparativa con ArrayList

| Operación | ArrayList | LinkedList | |-----------|-----------|------------| | get(i) | O(1) | O(n) | | set(i, e) | O(1) | O(n) | | add(e) (al final) | O(1) amortizado | O(1) | | add(0, e) (al principio) | O(n) | O(1) | | add(i, e) (posición arbitraria) | O(n) | O(n) (recorrer + ajustar) | | remove(i) | O(n) | O(n) (recorrer + ajustar) | | removeFirst() / removeLast() |: | O(1) | | Memoria por elemento | Baja | Alta (3 objetos por nodo: dato + next + prev) | | Localidad de caché | Buena | Mala | | Iteración (for-each) | Rápida | Aceptable |

Conclusiones sorprendentes:

• ArrayList es mejor en la mayoría de los casos reales.
• LinkedList solo gana cuando añades/quitas en los extremos y usas Deque/Queue.
• Para Deque, ArrayDeque suele ser aún mejor que LinkedList.

Cuándo usar LinkedList

Pocos casos justifican elegir LinkedList:

1. Cola FIFO con inserción al final y extracción al principio: funciona, pero ArrayDeque es más eficiente.
2. Lista con muchas inserciones/eliminaciones al inicio y pocas lecturas por índice: LinkedList puede ser razonable, aunque también ArrayDeque cumple.
3. Necesitas ambas caras: List por índice (ocasional) y Deque simultáneamente: LinkedList implementa las dos. Aunque suele ser señal de mal diseño (elige una abstracción).

En 99% de los casos reales, ArrayList es la opción correcta.

El antipatrón clásico: get(i) en un bucle

// MAL con LinkedList
LinkedList<String> lista = ...; // digamos 10.000 elementos
for (int i = 0; i < lista.size(); i++) {
    process(lista.get(i)); // O(n) cada llamada = O(n²) total
}

Cada lista.get(i) recorre desde el inicio (o final) del enlace: 10.000 * 5.000 ≈ 50 millones de operaciones. Terrible.

La forma correcta es usar el iterador (el for-each lo hace por ti):

// BIEN
for (String s : lista) { // O(n) total
    process(s);
}

El iterador mantiene la posición actual, avanzando un solo puntero por iteración.

LinkedList como Deque / Queue

Aunque ArrayDeque es preferible, LinkedList puede usarse como tal:

LinkedList<String> cola = new LinkedList<>();
cola.offerLast("a");
cola.offerLast("b");
cola.offerLast("c");
String primero = cola.pollFirst(); // "a"

// Como pila
cola.push("top");
String top = cola.pop();

Implementa Deque, Queue, List: es muy polivalente pero esa polivalencia viene con coste.

Memoria: el coste oculto

Cada elemento en LinkedList es un objeto con tres referencias:

• El dato.
• Puntero al nodo siguiente.
• Puntero al nodo anterior.

Más la cabecera de objeto (12-16 bytes en JVM HotSpot). Una LinkedList<Integer> con 1.000.000 enteros puede ocupar mucho más que una ArrayList<Integer> equivalente (que usa un array compacto de referencias).

Además, la localidad de caché es mala: los nodos están dispersos en memoria, lo que obliga a la CPU a cargas costosas cuando iteras.

Cuándo ArrayDeque supera a LinkedList

ArrayDeque es, en la práctica:

• Más rápida para cola FIFO.
• Más rápida para pila LIFO.
• Usa menos memoria.
• Tiene mejor localidad de caché.

Solo dos razones para preferir LinkedList sobre ArrayDeque:

1. Necesitas List además de Deque (mal diseño: elige).
2. Tu colección crecerá y empequeñecerá mucho y quieres evitar que ArrayDeque se quede con memoria sobredimensionada (argumento muy marginal).

Métodos específicos útiles

Aparte de List y Deque, LinkedList añade:

• descendingIterator(): iterador desde el final.
• clone(): copia superficial.
• Métodos Sequenced* (Java 21+).

Ejemplo completo

import java.util.LinkedList;

public class Cola {
    public static void main(String[] args) {
        LinkedList<String> cola = new LinkedList<>();

        // Añadir al final
        cola.offer("Ana");
        cola.offer("Bob");
        cola.offer("Carmen");

        // Procesar en orden FIFO
        while (!cola.isEmpty()) {
            String siguiente = cola.poll();
            System.out.println("Atendiendo a " + siguiente);
        }
    }
}

En este caso concreto, ArrayDeque sería preferible. Pero LinkedList también funciona y está en el JDK.

Resumen

| Criterio | Elige | |----------|-------| | Lista general, acceso por índice | ArrayList | | Deque o cola eficiente | ArrayDeque | | List + Deque (caso mixto raro) | LinkedList | | Thread-safe | CopyOnWriteArrayList, ConcurrentLinkedDeque | | Inmutable | List.of(...) / List.copyOf(x) |

La regla práctica: usa ArrayList por defecto. Considera LinkedList solo si has medido y verificado que tu caso específico la beneficia: y antes prueba con ArrayDeque.

LinkedList es un clásico del JDK con pocos casos de uso real. Saber no usarla en situaciones donde ArrayList gana es una señal de criterio en un desarrollador Java.