Java LinkedList

LinkedList<E> es una lista doblemente enlazada: cada elemento vive en su propio nodo en el heap con un puntero al nodo siguiente y un puntero al anterior. Esto le otorga el perfil de rendimiento opuesto al de ArrayList: insertar y eliminar en los extremos es O(1), pero get(i) tiene que recorrer el camino desde un extremo hasta el índice — O(n). La clase es también la única List integrada de Java que implementa además Deque<E>, por lo que funciona también como una cola. Este capítulo explica cuándo esa combinación es la herramienta adecuada, y la lista (un poco más larga) de casos en los que no lo es.

La estructura de datos

Cada elemento es un nodo:

node:  prev ←—— element ——→ next

La lista mantiene dos referencias de campo — first y last — y un contador size. Para añadir en cualquier extremo, se asigna un nodo, se ensambla ajustando dos punteros y se incrementa size. Sin array, sin redimensionamiento, sin memoria sobrante. Ese es el atractivo.

El coste está en todo lo demás:

• Cada elemento paga por un objeto nodo — tres referencias y una cabecera de objeto. La sobrecarga de memoria por elemento es mucho mayor que el array plano de ArrayList.
• get(i), set(i, x), add(i, x), remove(i) recorren todos desde el extremo más cercano. Por tanto, list.get(size/2) es O(n/2). Para listas largas, eso se agrava considerablemente.
• La localidad de caché es deficiente — los nodos están dispersos por el heap, por lo que el recorrido falla en la caché del CPU y se ralentiza incluso cuando el algoritmo parece lineal.

Cuándo LinkedList es la elección correcta

La respuesta honesta en 2026: raramente como List, a veces como Deque, casi nunca para "acelerar inserciones." El folclore "usa LinkedList porque harás muchas inserciones" no ha envejecido bien — para la mayoría de las cargas de trabajo, la eficiencia de caché de ArrayList más su append amortizado O(1) supera el rastreo de punteros extra de una lista enlazada, incluso cuando el algoritmo llama add(0, x) ocasionalmente. Los casos en los que LinkedList realmente gana:

• Necesitas un Deque (añadir/eliminar en ambos extremos) y no tienes ya un ArrayDeque disponible. ArrayDeque es más rápido; LinkedList es más familiar.
• Mantienes referencias persistentes a nodos específicos (mediante ListIterator) y quieres insertar/eliminar O(1) en esas posiciones exactas. Este es el caso de uso clásico de lista enlazada — y casi nunca aparece en el Java cotidiano.
• Quieres una implementación de Queue que también exponga métodos de List para inspección. Ejemplo real: una cola de trabajos que ocasionalmente se vuelca en un log.

Para "lista a la que añado elementos y leo por índice," usa ArrayList. Para "cola o deque," usa ArrayDeque. LinkedList se sitúa entre ambas y raramente es la mejor opción para ninguna de las dos tareas.

Crear una instancia y usarla como List

La mitad de la API correspondiente a List es idéntica a la de ArrayList:

List<String> tasks = new LinkedList<>();
tasks.add("compile");
tasks.add("test");
tasks.add(0, "lint");          // O(1) — at the head
String first = tasks.get(0);   // O(1) — head
String last  = tasks.get(tasks.size() - 1);   // O(1) — tail
String mid   = tasks.get(tasks.size() / 2);   // O(n/2) — has to walk

El constructor no tiene parámetro de capacidad — no hay nada que predimensionar, porque los nodos se asignan de uno en uno.

Usarla como Queue y Deque

Como LinkedList implementa tanto Queue<E> como Deque<E>, obtienes los métodos de cola además de los de List:

Deque<String> stack = new LinkedList<>();
stack.push("a");          // adds to head
stack.push("b");
String top = stack.pop(); // removes from head → "b"

Queue<String> jobs = new LinkedList<>();
jobs.offer("j1");         // adds to tail
jobs.offer("j2");
String next = jobs.poll();// removes from head → "j1"

Si tu necesidad es puramente "cola FIFO" o "pila LIFO," declara la variable como Queue<E> o Deque<E> — y prefiere new ArrayDeque<>() como implementación. La interfaz es la misma; la implementación respaldada por array es notablemente más rápida.

Iteración y ConcurrentModificationException

El mismo modelo fail-fast que ArrayList. Mutar durante un bucle for-each lanza una excepción:

LinkedList<Integer> xs = new LinkedList<>(List.of(1, 2, 3, 4));
for (int x : xs) if (x % 2 == 0) xs.remove(Integer.valueOf(x));  // throws

removeIf y el Iterator.remove() explícito son las dos formas seguras — idéntico al capítulo de ArrayList. El giro interesante para LinkedList es el ListIterator: como el iterador mantiene una referencia directa al nodo actual, sus métodos add y remove son genuinamente O(1). Si realmente necesitas iteración con inserción-en-posición rápida, LinkedList.listIterator() es la API que cumple lo que promete el libro de texto.

Seguridad en hilos

El mismo caso que ArrayList: ninguna. Usa Collections.synchronizedList(new LinkedList<>()) para bloqueo general, o — mucho mejor — un ConcurrentLinkedDeque si tu caso de uso es realmente una cola concurrente.

La comparación con ArrayDeque en un párrafo

Cuando recurres a LinkedList para usarla como cola o pila, mira primero ArrayDeque. ArrayDeque es un array circular — sin nodo por elemento, sin rastreo de punteros, sin reglas de rechazo de null que recordar. En cargas de trabajo reales de pila/cola con muchos elementos, generalmente supera a LinkedList — a veces por un margen amplio — porque evita un nodo heap y una cabecera por elemento y mantiene sus datos contiguos en memoria. No implementa List, que es su única desventaja real. (No sobreinterpretes un benchmark pequeño en ninguna dirección; ve el ejemplo práctico a continuación.)

Un ejemplo práctico: la misma tarea, dos estructuras de datos

El programa a continuación construye la misma cola con ArrayList, LinkedList y ArrayDeque — push a un extremo, pop desde el otro 200 000 veces — e imprime el tiempo de reloj de pared para cada uno. Lee los números en contexto: son un micro-benchmark aproximado de una sola ejecución sobre una JVM fría, no un resultado riguroso, así que toma el orden relativo — no los milisegundos exactos — como la lección. ArrayList es dramáticamente más lento que los otros dos porque remove(0) es O(n), por lo que el bucle de vaciado es cuadrático. LinkedList y ArrayDeque son ambos rápidos: cada uno hace trabajo O(1) en la cabeza. Cuál de los dos toma la delantera depende de la máquina, el JIT y el boxing de Integer — eso es exactamente por qué nunca deberías apoyarte en un benchmark tan pequeño para elegir entre ellos.

Dos conclusiones:

• Los primeros dos tiempos muestran por qué nunca indexar una LinkedList en un bucle. La forma for-each recorre la lista una vez en O(n); la forma por índice la recorre una vez por cada índice, dando O(n²). Para 10 000 elementos eso ya es doloroso; para 100 000 son segundos.
• Los tres tiempos de cola muestran la verdadera división: está entre ArrayList (vaciado cuadrático) y las dos estructuras con O(1) en la cabeza, no entre LinkedList y ArrayDeque. Una vez descartado ArrayList para trabajo de cola, prefiere igualmente ArrayDeque — no asigna ningún nodo por elemento y tiene una localidad de caché mucho mejor en colas grandes y de larga vida, que un bucle de arranque en frío de 200 000 elementos no expone del todo. La razón genuina restante para usar LinkedList es "quiero un Deque y una List", y eso también es raro.

Qué sigue

LinkedList y ArrayList son las dos implementaciones de List de propósito general más interesantes. La tercera — más antigua, sincronizada, principalmente histórica — es Vector. Saber por qué no es la elección correcta en código nuevo forma parte de dominar el framework.

Práctica