LinkedList es la segunda implementación de List del JDK y probablemente la más malinterpretada de todo el Framework. La frase que se repite en tutoriales, en entrevistas de trabajo y en comentarios de código es siempre la misma: "usa ArrayList para acceder por índice y LinkedList para insertar y borrar, que es O(1)". Esa frase es, tal como suena, falsa, y creerla lleva a escribir código considerablemente más lento pensando que se está optimizando.

En esta lección vas a entender exactamente qué es una lista doblemente enlazada, qué operaciones son realmente O(1) y bajo qué condición precisa, y por qué en la práctica —incluso en los casos que parecen su terreno— ArrayList suele ganar. También verás dónde LinkedList sí tiene sentido: no tanto como List, sino como Deque, es decir, como cola de doble extremo. Y terminarás con el único caso de BiblioTech donde su semántica encaja de verdad: la cola de reservas pendientes, que se consume por un extremo y crece por el otro.

Esta lección no va solo de una clase. Va de aprender a razonar honestamente sobre estructuras de datos, distinguiendo lo que dice la teoría de lo que hace el procesador.

1. La estructura: nodos doblemente enlazados
2. Qué implica para la memoria y para la caché
3. El matiz que casi todo el mundo explica mal
4. ArrayList frente a LinkedList, operación por operación
5. La conclusión honesta y actual
6. LinkedList como Deque
7. ListIterator: recorrido bidireccional e inserción
8. Medir el rendimiento de forma honesta
9. Cuándo LinkedList sí es la elección correcta: la cola de reservas
10. Errores Comunes y Consejos
11. Ejercicios

Un ArrayList guarda los elementos en un bloque contiguo de memoria. Una LinkedList no guarda nada contiguo: guarda una cadena de nodos, cada uno en su propio rincón del heap, unidos por referencias.

Este es el nodo real del JDK, y cabe en cinco líneas:

Y la lista en sí guarda solo tres campos:

Las flechas continuas son los next; las punteadas, los prev. Que haya enlaces en ambos sentidos es lo que la hace doblemente enlazada, y tiene dos consecuencias importantes: se puede recorrer hacia atrás, y desde un nodo se puede eliminar ese nodo sin conocer el anterior.

De esta estructura se deducen inmediatamente sus dos características fundamentales:

No hay índices. Los nodos no están numerados ni colocados en posiciones calculables. Para llegar al elemento 500 hay que empezar en first y saltar 500 veces. No existe forma de hacerlo más rápido, y ahí está la debilidad estructural de LinkedList.

No hay capacidad. Cada nodo se crea cuando hace falta y se descarta cuando se elimina. No hay redimensionados, no hay copias, no hay array interno que llenar. Añadir el elemento un millón cuesta exactamente lo mismo que añadir el segundo.

Ver cómo se inserta un nodo en medio explica el resto:

La operación consiste en crear el nodo X y cambiar cuatro referencias: A.next = X, X.prev = A, X.next = B, B.prev = X. Cuatro asignaciones. Ningún elemento se mueve, ni el primero ni el millonésimo. Eso es lo que quiere decir "inserción O(1)". Y ahora viene el matiz.

Antes del matiz, dos costes que las tablas de complejidad no muestran y que en la práctica pesan más que la propia O().

En un ArrayList, cada elemento ocupa una referencia en el array interno: 4 bytes con compresión de punteros, 8 sin ella.

En una LinkedList, cada elemento necesita un objeto Node completo:

Frente a los ~4 bytes por elemento de un ArrayList bien dimensionado, eso es unas siete veces más memoria solo en infraestructura, sin contar los objetos apuntados. Para un millón de elementos: unos 4 MB frente a unos 28 MB. Y cada nodo es un objeto que el recolector de basura tiene que rastrear (módulo 10-07).

Este es el factor decisivo y el que más gente ignora. Como explicaba 05-01, el procesador no lee memoria byte a byte: trae bloques de 64 bytes a su caché. En un ArrayList, leer el elemento 0 trae también los 15 siguientes gratis; recorrer la lista es prácticamente lectura secuencial, el patrón que más le gusta al hardware.

En una LinkedList, cada nodo puede estar en cualquier parte del heap. Si los creaste en orden puede que estén cerca, pero después de un tiempo de altas y bajas, y tras varias pasadas del recolector, quedan dispersos. Recorrer significa entonces un salto impredecible de memoria por elemento, y cada salto que falla en caché cuesta del orden de cien veces más que un acceso en caché.

El resultado medido una y otra vez: recorrer una LinkedList suele ser entre 2 y 10 veces más lento que recorrer un ArrayList del mismo tamaño, aunque ambas operaciones sean O(n). La notación O() ignora las constantes, y aquí la constante importa muchísimo.

Repitamos la afirmación popular: "insertar y borrar en LinkedList es O(1)".

Lo correcto es: insertar y borrar es O(1) SI YA TIENES LA POSICIÓN, es decir, si ya tienes en la mano una referencia al nodo (o estás en un extremo). Llegar a esa posición cuesta O(n).

Míralo en el código real del JDK:

linkBefore es O(1): cuatro asignaciones. Pero node(index) recorre hasta la mitad de la lista. El método completo es O(n). La optimización de empezar por el extremo más cercano solo divide entre dos: sigue siendo O(n).

Consecuencia directa: este bucle, que parece razonable, es un desastre.

Mil llamadas × 50 000 saltos = 50 millones de saltos de puntero. El mismo bucle con ArrayList haría mil System.arraycopy de 50 000 referencias, que es la misma O() pero ejecutada por una instrucción de copia de bloque optimizada por el hardware: en la práctica, varias veces más rápido.

Solo en tres situaciones:

1. En los extremos. addFirst, addLast, removeFirst, removeLast acceden directamente a first y last. Genuinamente O(1), sin recorrido.

2. Con un iterador que ya está en la posición.

El recorrido completo es O(n), pero cada inserción individual es O(1), y no hay desplazamiento de elementos. Aquí LinkedList sí es teóricamente superior a ArrayList, donde cada add(i, e) desplazaría el resto.

3. Iterator.remove() durante un recorrido. Mismo razonamiento: el iterador ya tiene el nodo.

La regla resumida, que conviene memorizar:

En LinkedList la operación es barata; llegar al sitio es caro. En ArrayList llegar al sitio es gratis; la operación es cara.

Y como "llegar al sitio" es lo que hace cualquier método indexado, el resultado neto casi siempre favorece a ArrayList.

Presta especial atención a la fila del for indexado, porque es un error de rendimiento que se cuela con facilidad:

Si el parámetro de tu método es List y no sabes qué implementación te llegará, recorre siempre con for-each. Esa es una de las razones por las que existe la interfaz marcadora RandomAccess (05-03): permite a un algoritmo genérico preguntar si el acceso indexado es barato.

En tu código no escribirás esto casi nunca —usa for-each y ya está—, pero es útil saber por qué existe.

Es la parte de la lección que más se aparta del discurso habitual, así que va con nombres y argumentos.

En la práctica, ArrayList gana casi siempre. Incluso en escenarios que parecen favorecer a LinkedList, las mediciones repetidas en JVM modernas dan la victoria al array, porque:

1. La localidad de caché domina. La diferencia entre un acceso en caché L1 y un fallo que va a memoria principal es de dos órdenes de magnitud. Ninguna ventaja algorítmica sobrevive a eso cuando la O() es la misma.
2. System.arraycopy es una instrucción nativa que copia bloques de memoria a velocidad de hardware. Desplazar 10 000 referencias contiguas es sorprendentemente barato; seguir 10 000 punteros dispersos, no.
3. Los nodos presionan al recolector. Un millón de elementos son un millón de objetos Node que rastrear, frente a un solo array.
4. Las inserciones "en medio" casi nunca son en medio de verdad. En el código real se inserta al final, o se elimina por criterio con removeIf, o se ordena. Todas esas operaciones favorecen al ArrayList.

Esta es también la opinión pública de Joshua Bloch, autor de Java Efectivo y coautor del propio Framework de Colecciones, que ha llegado a decir que a día de hoy LinkedList no aporta valor suficiente para justificar su uso general.

¿Entonces LinkedList no sirve para nada? Sirve, pero no como List: como Deque. Cuando lo que quieres es una cola o una pila —añadir por un extremo, sacar por el otro— LinkedList cumple con O(1) real y sin capacidad que gestionar.

Y aun así, en ese terreno tiene un competidor mejor: ArrayDeque, que verás en 05-07, y que es más rápido y consume menos memoria porque usa un array circular. La recomendación oficial del JDK para colas y pilas es ArrayDeque, no LinkedList.

El resumen práctico, sin rodeos:

Que sigas aprendiendo LinkedList tiene tres motivos sólidos: la vas a encontrar en código existente, es el ejemplo canónico de lista enlazada —una estructura que aparece en mil sitios— y entender por qué no es la respuesta te enseña a razonar sobre rendimiento mejor que cualquier regla memorizada.

LinkedList implementa dos interfaces a la vez, y ahí está su rasgo distintivo:

Es la única clase del JDK que es List y Deque simultáneamente. Eso le da acceso a toda la familia de operaciones por los extremos, todas genuinamente O(1):

La distinción entre las dos familias —lanzar excepción o devolver null— es una decisión de diseño importante de Queue y Deque, y se explica a fondo en 05-07. Por ahora quédate con la regla: usa peek/poll/offer cuando la colección vacía sea una situación normal; usa getFirst/removeFirst/addFirst cuando esté vacía signifique que algo va mal.

Ejemplo con las dos semánticas sobre la misma clase:

Fíjate en el tipo de la variable: aquí está declarada como LinkedList porque necesitamos métodos que List no tiene. Si solo vas a usarla como cola, lo correcto según la regla de oro de 05-02 es declararla por la interfaz que refleje su uso:

El uso de cola y pila en detalle son las lecciones 05-07 y 05-08.

ListIterator es una extensión de Iterator exclusiva de las listas, y es la forma correcta de insertar o sustituir elementos mientras recorres. Su API:

La clave conceptual: un ListIterator no señala un elemento, señala un hueco entre elementos (un cursor). next() salta el elemento a su derecha y devuelve su valor; previous() salta el de su izquierda.

Los ^ son las posiciones posibles del cursor. Con el cursor en ^1, next() devuelve B y deja el cursor en ^2; previous() devolvería A y lo dejaría en ^0.

Este es el uso que justifica su existencia:

Tres detalles que hay que entender:

1. it.add(x) inserta en la posición del cursor, que tras next() está justo después del elemento devuelto. Por eso el aviso aparece detrás de la baja.
2. El elemento insertado no se vuelve a visitar. add avanza el cursor por encima de lo insertado, así que no hay bucle infinito. Compruébalo: si add no lo hiciera, el nuevo elemento se examinaría y podría generar otro, indefinidamente.
3. No hay ConcurrentModificationException. El iterador es quien modifica, así que actualiza su expectedModCount (05-02).

Intentar lo mismo con un for-each y lista.add(...) daría la excepción de inmediato. Y hacerlo con índices sobre un ArrayList obligaría a recalcular la posición tras cada inserción, un clásico generador de fallos de límite.

Equivalente a replaceAll cuando la condición es simple, pero permite lógica arbitraria y decidir elemento a elemento.

Sobre una LinkedList esto es eficiente gracias a los enlaces prev; sobre un ArrayList también, porque el acceso indexado es O(1). En ambos casos es más claro que un for decreciente cuando además necesitas insertar o eliminar.

Aviso importante: mezclar un ListIterator con modificaciones directas de la lista rompe todo. Mientras un iterador esté vivo, todos los cambios deben pasar por él.

Vamos a comparar las dos implementaciones con un experimento sencillo. Antes, una advertencia que hay que tomarse en serio.

Los microbenchmarks en Java son traicioneros. La JVM compila el código a medida que se ejecuta (JIT), así que las primeras iteraciones son mucho más lentas que las siguientes; el recolector de basura puede saltar en mitad de la medición; y el compilador puede eliminar por completo un bucle cuyo resultado no se usa, dándote tiempos de cero. La herramienta correcta es JMH (Java Microbenchmark Harness), la librería oficial de OpenJDK, que gestiona el calentamiento, las iteraciones y el consumo de resultados. Lo que sigue es una aproximación ilustrativa, útil para ver órdenes de magnitud, no para publicar cifras.

Resultados típicos en una máquina de escritorio, con el orden de magnitud como única información fiable:

La última fila resume la lección: el único caso claro a favor de LinkedList es insertar por el principio, y para eso existe una estructura mejor.

Y una conclusión metodológica igual de valiosa: mide antes de optimizar. Si alguien cambia un ArrayList por un LinkedList "porque inserta más rápido" sin haber medido, hay muchas probabilidades de que haya empeorado el programa.

Llega el caso real de BiblioTech. Cuando un material está prestado, un empleado puede reservarlo. Las reservas forman una cola: se atienden por orden de llegada, se añaden por el final y se consumen por el principio. Es el patrón exacto en que una lista enlazada es adecuada: cero acceso por índice, todo por los extremos.

Primero, la clase Reserva. Como es un dato con identidad propia y estado (atendida), la modelamos como clase, no como record (04-07):

Y la cola de reservas de un material:

Uso completo:

Fíjate en tres decisiones deliberadas de este código:

• posicionDe recorre con for-each, nunca con get(i). Sobre una LinkedList, el bucle indexado sería O(n²).
• cancelarUltimaDe usa descendingIterator y it.remove(): el iterador ya tiene el nodo, así que la eliminación es O(1) real. Es el caso legítimo del apartado 3.
• adelantar es honesto sobre su coste: el remove(Object) es O(n) porque hay que localizar la reserva; solo el addFirst es O(1). Este método sería el primer candidato a revisar si la cola creciera mucho, y una PriorityQueue (05-07) resolvería mejor el problema de las urgencias.

Y una nota final de diseño: aunque LinkedList funciona bien aquí, la declaración canónica de una cola es Deque<Reserva> pendientes = new ArrayDeque<>(). Se ha usado LinkedList porque además necesitamos removeIf y recorridos, y porque este era su caso natural; en 05-07 verás la versión con ArrayDeque y por qué suele ser mejor.

Recorrer una LinkedList con for indexado. for (int i = 0; i < lista.size(); i++) lista.get(i) es O(n²): cada get recorre la cadena desde un extremo. Con 100 000 elementos pasa de milisegundos a minutos. Usa siempre for-each o un iterador.

Creer que add(i, e) es O(1) en LinkedList. La inserción sí lo es; llegar al índice i no. El método completo es O(n). Solo los extremos y las inserciones vía iterador son O(1) de verdad.

Elegir LinkedList "porque inserta más rápido" sin medir. En la práctica pierde casi siempre por localidad de caché y por consumo de memoria. Empieza por ArrayList y cambia solo con datos en la mano.

Usar LinkedList como cola cuando existe ArrayDeque. ArrayDeque es más rápido y ocupa menos. La única razón para preferir LinkedList es necesitar List y Deque en la misma variable, o admitir elementos null.

Confundir get/remove con peek/poll. Sobre una lista vacía, getFirst() y removeFirst() lanzan NoSuchElementException; peekFirst() y pollFirst() devuelven null. Elige según si la cola vacía es normal o es un error.

Modificar la lista mientras hay un ListIterator vivo. Cualquier lista.add, lista.remove o lista.clear directo invalida el iterador y provoca ConcurrentModificationException en la siguiente operación. Mientras el iterador exista, todo pasa por él.

Olvidar que it.add(x) no vuelve a visitar lo insertado. Es lo que evita el bucle infinito, y es lo correcto; pero si esperabas que el nuevo elemento se evaluara, no ocurrirá.

Ordenar una LinkedList a menudo. sort vuelca a un array, ordena y reconstruye toda la cadena de nodos. Si vas a ordenar con frecuencia, usa ArrayList; si necesitas orden permanente, TreeSet o PriorityQueue (05-06, 05-07).

Consejo: declara por la interfaz que refleje el uso. Si es una lista, List<X> l = new ArrayList<>(). Si es una cola, Deque<X> d = new ArrayDeque<>(). Declarar LinkedList<X> solo se justifica cuando necesitas las dos caras a la vez.

Consejo: LinkedList es un magnífico ejercicio mental. Implementarla a mano —con nodos, prev y next— enseña más sobre punteros y estructuras de datos que muchos libros. Pero en producción, ArrayList.

Escribe HistorialOperaciones que guarde las últimas N operaciones del catálogo (cadenas como "alta:978-0000000001"), usando una LinkedList como estructura interna:

• void registrar(String operacion): añade al final y, si se supera el máximo, elimina la más antigua (la primera).
• String ultima() y String masAntigua(): sin eliminarlas, devolviendo null si está vacío.
• List<String> enOrdenInverso(): de la más reciente a la más antigua, con descendingIterator.
• int eliminarPorPrefijo(String prefijo): elimina todas las que empiecen por ese prefijo y devuelve cuántas quitó.

Justifica en comentarios qué operaciones son O(1) reales y cuáles no.

Escribe un método estático void insertarSeparadores(List<Material> catalogo) que recorra un catálogo ya ordenado por tipo e inserte, antes del primer material de cada tipo, un Material especial de tipo separador (usa un Libro con título "--- LIBROS ---" o crea una pequeña clase Separador extends Material).

Debe funcionar con ListIterator y sin provocar ConcurrentModificationException ni bucles infinitos. Explica por qué la inserción no se vuelve a visitar.

Añade después una versión insertarSeparadoresMal que intente lo mismo con un for-each y documenta qué falla exactamente.

Escribe BancoDePruebas que compare ArrayList y LinkedList en cuatro escenarios, con calentamiento previo y con protección contra la eliminación de código por el JIT:

1. Añadir N elementos al final.
2. Recorrer con for-each sumando.
3. Insertar 10 000 elementos por el principio.
4. Eliminar por criterio con removeIf.

Imprime una tabla con los tiempos y escribe, en un comentario final, tu conclusión razonada y la advertencia sobre JMH.

Solución 1

Prueba:

Este es el caso de uso ideal de LinkedList: una ventana deslizante. Cada registro añade por un extremo y quita por el otro, ambas O(1) reales. Con ArrayList, cada remove(0) desplazaría toda la lista. Dicho eso, la respuesta profesional para una ventana deslizante es ArrayDeque (05-07), que hace lo mismo con un array circular, sin nodos y sin presión sobre el recolector.

Solución 2

La secuencia previous() → add(...) → next() merece una explicación cuidadosa. Tras it.next() el cursor está detrás del material actual, pero el separador debe ir delante. previous() retrocede el cursor a la posición anterior (y devuelve el mismo material, que descartamos). add inserta ahí y deja el cursor detrás de lo insertado, es decir, todavía delante del material. next() vuelve a saltarlo para continuar.

Ese avance automático del cursor tras add es exactamente lo que impide el bucle infinito: el elemento insertado nunca es devuelto por next(). Si add no lo hiciera, el siguiente next() devolvería el separador, cuyo tipo tampoco coincidiría con tipoAnterior, y se insertaría otro separador, indefinidamente.

Y sobre la versión incorrecta, hay dos fallos apilados: la ConcurrentModificationException y, más de fondo, que catalogo.add(x) inserta al final, no donde estás recorriendo. Es un buen recordatorio de que el for-each no conoce su propia posición.

Solución 3

Salida típica (los valores absolutos varían mucho según la máquina; lo que importa es la relación):

Conclusión razonada. LinkedList gana en un solo escenario, el 3, y lo gana por mucho: insertar por el principio es su terreno natural. En los otros tres pierde, y en el recorrido —la operación más frecuente en cualquier programa real— es unas siete veces más lenta con la misma complejidad O(n): la diferencia es puramente localidad de caché.

El escenario 4 es especialmente revelador. removeIf es O(n) en ambas y elimina en O(1) en las dos (por iterador), pero LinkedList sigue perdiendo, porque recorrer los nodos dispersos domina el tiempo total.

Y la observación decisiva: si añades al banco de pruebas un ArrayDeque con addFirst, el escenario 3 baja a aproximadamente 1 ms, batiendo a las dos. Es decir, incluso en el único caso donde LinkedList gana a ArrayList, no es la mejor herramienta disponible. Por eso la recomendación práctica es: ArrayList para listas, ArrayDeque para colas y pilas, LinkedList casi nunca.

Repite la advertencia con cada número que veas: para decisiones de rendimiento reales, mide con JMH sobre tu carga de trabajo concreta.

Ya sabes qué es una lista doblemente enlazada: una cadena de nodos con prev, item y next, sin array, sin capacidad y sin índices. Entiendes lo que eso implica de verdad: ~28 bytes por elemento frente a los ~4 de un ArrayList, y nodos dispersos por el heap que destruyen la localidad de caché y hacen que recorrerla sea varias veces más lento aunque la complejidad sea la misma O(n). Has visto en el código del propio JDK que node(index) recorre la cadena, y con ello has desmontado el mito: insertar y borrar es O(1) solo si ya tienes la posición, lo que ocurre únicamente en los extremos y a través de un iterador; llegar por índice cuesta O(n).

Tienes la tabla comparativa operación por operación y la conclusión honesta que se deriva de ella: ArrayList gana casi siempre, porque System.arraycopy es una instrucción de bloque nativa, porque la caché domina, porque los nodos presionan al recolector y porque las inserciones "en medio" casi nunca lo son. Sabes que el propio coautor del Framework la considera prescindible hoy, y que su nicho real no es ser una List sino ser un Deque, terreno en el que ArrayDeque la supera. También sabes leer el error de rendimiento que más se cuela: un for indexado sobre una LinkedList es O(n²) disfrazado.

Conoces su doble naturaleza List + Deque y toda la familia de operaciones por los extremos, con la distinción entre la variante que lanza excepción (getFirst, removeFirst) y la que devuelve null (peekFirst, pollFirst) —que 05-07 desarrollará—. Y dominas el ListIterator: el cursor que vive entre elementos, el recorrido bidireccional, add y set durante el recorrido, por qué lo insertado no se vuelve a visitar y por qué es la única forma correcta de insertar mientras recorres.

Sabes medir con honestidad: calentar la JVM, consumir los resultados para que el JIT no elimine los bucles, desconfiar de los números absolutos y recurrir a JMH cuando la decisión importe de verdad. Y por encima de todo, has adoptado el criterio profesional: mide antes de optimizar, porque cambiar ArrayList por LinkedList "porque inserta más rápido" es, casi siempre, empeorar el programa.

BiblioTech ha ganado la clase Reserva y una ColaReservas que encola por el final, atiende por el principio, cancela mediante iterador descendente en O(1) real y caduca las reservas antiguas con removeIf. Es el único punto del proyecto donde una lista enlazada estaba justificada, y aun así has visto por qué en 05-07 la reescribirás con ArrayDeque.

Y queda una debilidad que ya se está haciendo insoportable. Catalogo.eliminar(referencia) recorre la lista entera. GestorPrestamos.devolver(referencia, dia) recorre la lista entera. ColaReservas.posicionDe(empleado) recorre la lista entera. Cada vez que BiblioTech tiene que encontrar algo por su identificador, mira uno por uno. Con cinco materiales es gratis; con cincuenta mil, cada búsqueda son cincuenta mil comparaciones, y agrupar préstamos por empleado con bucles anidados es O(n²).

En la lección siguiente, HashMap, eso se acaba. Verás la estructura que encuentra un elemento por su clave en tiempo constante sin importar cuántos haya: cómo funciona la función hash, qué son las cubetas, qué ocurre cuando dos claves colisionan, por qué el factor de carga es 0,75 y qué pasa en un rehash. Y ahí se cumplirá por fin la promesa que se hizo en el módulo 3: verás con una demostración práctica por qué equals y hashCode tenían que ir siempre juntos, y qué le ocurre exactamente a un objeto que entra en un mapa con uno de los dos mal implementado.