LinkedList és la segona implementació de List del JDK i probablement la més malinterpretada de tot el Framework. La frase que es repeteix als tutorials, a les entrevistes de feina i als comentaris de codi és sempre la mateixa: "fes servir ArrayList per accedir per índex i LinkedList per inserir i esborrar, que és O(1)". Aquesta frase és, tal com sona, falsa, i creure-se-la porta a escriure codi considerablement més lent pensant que s'està optimitzant.

En aquesta lliçó entendràs exactament què és una llista doblement enllaçada, quines operacions són realment O(1) i sota quina condició precisa, i per què a la pràctica —fins i tot en els casos que semblen el seu terreny— ArrayList acostuma a guanyar. També veuràs on LinkedList sí que té sentit: no tant com a List, sinó com a Deque, és a dir, com a cua de doble extrem. I acabaràs amb l'únic cas de BiblioTech on la seva semàntica encaixa de debò: la cua de reserves pendents, que es consumeix per un extrem i creix per l'altre.

Aquesta lliçó no va només d'una classe. Va d'aprendre a raonar honestament sobre estructures de dades, distingint el que diu la teoria del que fa el processador.

1. L'estructura: nodes doblement enllaçats
2. Què implica per a la memòria i per a la memòria cau
3. El matís que gairebé tothom explica malament
4. ArrayList enfront de LinkedList, operació per operació
5. La conclusió honesta i actual
6. LinkedList com a Deque
7. ListIterator: recorregut bidireccional i inserció
8. Mesurar el rendiment de manera honesta
9. Quan LinkedList sí que és l'elecció correcta: la cua de reserves
10. Errors Habituals i Consells
11. Exercicis

Un ArrayList guarda els elements en un bloc contigu de memòria. Una LinkedList no guarda res contigu: guarda una cadena de nodes, cadascun al seu propi racó del heap, units per referències.

Aquest és el node real del JDK, i cap en cinc línies:

I la llista en si guarda només tres camps:

Les fletxes contínues són els next; les puntejades, els prev. Que hi hagi enllaços en tots dos sentits és el que la fa doblement enllaçada, i té dues conseqüències importants: es pot recórrer cap enrere, i des d'un node es pot eliminar aquest node sense conèixer l'anterior.

D'aquesta estructura se'n dedueixen immediatament les seves dues característiques fonamentals:

No hi ha índexs. Els nodes no estan numerats ni col·locats en posicions calculables. Per arribar a l'element 500 cal començar a first i saltar 500 vegades. No hi ha cap manera de fer-ho més ràpid, i aquí hi ha la debilitat estructural de LinkedList.

No hi ha capacitat. Cada node es crea quan cal i es descarta quan s'elimina. No hi ha redimensionaments, no hi ha còpies, no hi ha array intern per omplir. Afegir l'element un milió costa exactament el mateix que afegir el segon.

Veure com s'insereix un node al mig ho explica tot la resta:

L'operació consisteix a crear el node X i canviar quatre referències: A.next = X, X.prev = A, X.next = B, B.prev = X. Quatre assignacions. Cap element no es mou, ni el primer ni el milionèsim. Això és el que vol dir "inserció O(1)". I ara ve el matís.

Abans del matís, dos costos que les taules de complexitat no mostren i que a la pràctica pesen més que la mateixa O().

En un ArrayList, cada element ocupa una referència a l'array intern: 4 bytes amb compressió de punters, 8 sense.

En una LinkedList, cada element necessita un objecte Node complet:

Enfront dels ~4 bytes per element d'un ArrayList ben dimensionat, això són unes set vegades més memòria només en infraestructura, sense comptar els objectes apuntats. Per a un milió d'elements: uns 4 MB enfront d'uns 28 MB. I cada node és un objecte que el recol·lector de brossa ha de rastrejar (mòdul 10-07).

Aquest és el factor decisiu i el que més gent ignora. Com explicava 05-01, el processador no llegeix memòria byte a byte: porta blocs de 64 bytes a la seva memòria cau. En un ArrayList, llegir l'element 0 porta també els 15 següents de franc; recórrer la llista és pràcticament lectura seqüencial, el patró que més agrada al maquinari.

En una LinkedList, cada node pot ser a qualsevol lloc del heap. Si els vas crear en ordre potser són a prop, però després d'un temps d'altes i baixes, i després de diverses passades del recol·lector, queden dispersos. Recórrer significa llavors un salt impredictible de memòria per element, i cada salt que falla a la memòria cau costa de l'ordre de cent vegades més que un accés en memòria cau.

El resultat mesurat una vegada i una altra: recórrer una LinkedList sol ser entre 2 i 10 vegades més lent que recórrer un ArrayList de la mateixa mida, encara que totes dues operacions siguin O(n). La notació O() ignora les constants, i aquí la constant importa moltíssim.

Repetim l'afirmació popular: "inserir i esborrar en LinkedList és O(1)".

El correcte és: inserir i esborrar és O(1) SI JA TENS LA POSICIÓ, és a dir, si ja tens a la mà una referència al node (o ets en un extrem). Arribar a aquesta posició costa O(n).

Mira-t'ho al codi real del JDK:

linkBefore és O(1): quatre assignacions. Però node(index) recorre fins a la meitat de la llista. El mètode complet és O(n). L'optimització de començar per l'extrem més proper només divideix entre dos: continua sent O(n).

Conseqüència directa: aquest bucle, que sembla raonable, és un desastre.

Mil crides × 50 000 salts = 50 milions de salts de punter. El mateix bucle amb ArrayList faria mil System.arraycopy de 50 000 referències, que és la mateixa O() però executada per una instrucció de còpia de bloc optimitzada pel maquinari: a la pràctica, unes quantes vegades més ràpid.

Només en tres situacions:

1. Als extrems. addFirst, addLast, removeFirst, removeLast accedeixen directament a first i last. Genuïnament O(1), sense recorregut.

2. Amb un iterador que ja és a la posició.

El recorregut complet és O(n), però cada inserció individual és O(1), i no hi ha desplaçament d'elements. Aquí LinkedList sí que és teòricament superior a ArrayList, on cada add(i, e) desplaçaria la resta.

3. Iterator.remove() durant un recorregut. Mateix raonament: l'iterador ja té el node.

La regla resumida, que convé memoritzar:

A LinkedList l'operació és barata; arribar al lloc és car. A ArrayList arribar al lloc és gratis; l'operació és cara.

I com que "arribar al lloc" és el que fa qualsevol mètode indexat, el resultat net gairebé sempre afavoreix ArrayList.

Presta especial atenció a la fila del for indexat, perquè és un error de rendiment que s'hi cola amb facilitat:

Si el paràmetre del teu mètode és List i no saps quina implementació t'arribarà, recorre sempre amb for-each. Aquesta és una de les raons per les quals existeix la interfície marcadora RandomAccess (05-03): permet a un algorisme genèric preguntar si l'accés indexat és barat.

Al teu codi no escriuràs això gairebé mai —fes servir for-each i au—, però és útil saber per què existeix.

És la part de la lliçó que més s'aparta del discurs habitual, així que va amb noms i arguments.

A la pràctica, ArrayList guanya gairebé sempre. Fins i tot en escenaris que semblen afavorir LinkedList, les mesures repetides en JVM modernes donen la victòria a l'array, perquè:

1. La localitat de memòria cau domina. La diferència entre un accés a la memòria cau L1 i una fallada que va a memòria principal és de dos ordres de magnitud. Cap avantatge algorísmic no sobreviu a això quan l'O() és la mateixa.
2. System.arraycopy és una instrucció nativa que copia blocs de memòria a velocitat de maquinari. Desplaçar 10 000 referències contigües és sorprenentment barat; seguir 10 000 punters dispersos, no.
3. Els nodes pressionen el recol·lector. Un milió d'elements són un milió d'objectes Node per rastrejar, enfront d'un sol array.
4. Les insercions "al mig" gairebé mai no són al mig de debò. Al codi real s'insereix al final, o s'elimina per criteri amb removeIf, o s'ordena. Totes aquestes operacions afavoreixen l'ArrayList.

Aquesta és també l'opinió pública de Joshua Bloch, autor de Java Eficaç i coautor del mateix Framework de Col·leccions, que ha arribat a dir que a dia d'avui LinkedList no aporta valor suficient per justificar-ne l'ús general.

Llavors LinkedList no serveix per a res? Serveix, però no com a List: com a Deque. Quan el que vols és una cua o una pila —afegir per un extrem, treure per l'altre— LinkedList compleix amb O(1) real i sense capacitat que gestionar.

I tot i així, en aquest terreny té un competidor millor: ArrayDeque, que veuràs a 05-07, i que és més ràpid i consumeix menys memòria perquè fa servir un array circular. La recomanació oficial del JDK per a cues i piles és ArrayDeque, no LinkedList.

El resum pràctic, sense embuts:

Que continuïs aprenent LinkedList té tres motius sòlids: te la trobaràs en codi existent, és l'exemple canònic de llista enllaçada —una estructura que apareix en mil llocs— i entendre per què no és la resposta t'ensenya a raonar sobre rendiment millor que qualsevol regla memoritzada.

LinkedList implementa dues interfícies alhora, i aquí hi ha el seu tret distintiu:

És l'única classe del JDK que és List i Deque simultàniament. Això li dona accés a tota la família d'operacions pels extrems, totes genuïnament O(1):

La distinció entre les dues famílies —llançar excepció o retornar null— és una decisió de disseny important de Queue i Deque, i s'explica a fons a 05-07. De moment queda't amb la regla: fes servir peek/poll/offer quan la col·lecció buida sigui una situació normal; fes servir getFirst/removeFirst/addFirst quan que estigui buida signifiqui que alguna cosa va malament.

Exemple amb les dues semàntiques sobre la mateixa classe:

Fixa't en el tipus de la variable: aquí està declarada com a LinkedList perquè necessitem mètodes que List no té. Si només la faràs servir com a cua, el correcte segons la regla d'or de 05-02 és declarar-la per la interfície que reflecteixi el seu ús:

L'ús de cua i pila en detall són les lliçons 05-07 i 05-08.

ListIterator és una extensió d'Iterator exclusiva de les llistes, i és la forma correcta d'inserir o substituir elements mentre recorres. La seva API:

La clau conceptual: un ListIterator no assenyala un element, assenyala un forat entre elements (un cursor). next() salta l'element que té a la dreta i en retorna el valor; previous() salta el de la seva esquerra.

Els ^ són les posicions possibles del cursor. Amb el cursor a ^1, next() retorna B i deixa el cursor a ^2; previous() retornaria A i el deixaria a ^0.

Aquest és l'ús que justifica la seva existència:

Tres detalls que cal entendre:

1. it.add(x) insereix a la posició del cursor, que després de next() és just darrere de l'element retornat. Per això l'avís apareix darrere de la baixa.
2. L'element inserit no es torna a visitar. add avança el cursor per damunt del que s'ha inserit, així que no hi ha bucle infinit. Comprova-ho: si add no ho fes, el nou element s'examinaria i en podria generar un altre, indefinidament.
3. No hi ha ConcurrentModificationException. L'iterador és qui modifica, així que actualitza el seu expectedModCount (05-02).

Intentar el mateix amb un for-each i llista.add(...) donaria l'excepció immediatament. I fer-ho amb índexs sobre un ArrayList obligaria a recalcular la posició després de cada inserció, un generador clàssic de fallades de límit.

Equivalent a replaceAll quan la condició és simple, però permet lògica arbitrària i decidir element a element.

Sobre una LinkedList això és eficient gràcies als enllaços prev; sobre un ArrayList també, perquè l'accés indexat és O(1). En tots dos casos és més clar que un for decreixent quan a més necessites inserir o eliminar.

Avís important: barrejar un ListIterator amb modificacions directes de la llista ho trenca tot. Mentre un iterador estigui viu, tots els canvis han de passar per ell.

Compararem les dues implementacions amb un experiment senzill. Abans, un advertiment que cal prendre's seriosament.

Els microbenchmarks en Java són traïdors. La JVM compila el codi a mesura que s'executa (JIT), així que les primeres iteracions són molt més lentes que les següents; el recol·lector de brossa pot saltar enmig de la mesura; i el compilador pot eliminar per complet un bucle el resultat del qual no es fa servir, donant-te temps de zero. L'eina correcta és JMH (Java Microbenchmark Harness), la llibreria oficial d'OpenJDK, que gestiona l'escalfament, les iteracions i el consum de resultats. El que ve a continuació és una aproximació il·lustrativa, útil per veure ordres de magnitud, no per publicar xifres.

Resultats típics en una màquina d'escriptori, amb l'ordre de magnitud com a única informació fiable:

L'última fila resumeix la lliçó: l'únic cas clar a favor de LinkedList és inserir pel principi, i per a això existeix una estructura millor.

I una conclusió metodològica igual de valuosa: mesura abans d'optimitzar. Si algú canvia un ArrayList per un LinkedList "perquè insereix més ràpid" sense haver mesurat, hi ha moltes probabilitats que hagi empitjorat el programa.

Arriba el cas real de BiblioTech. Quan un material està prestat, un empleat el pot reservar. Les reserves formen una cua: s'atenen per ordre d'arribada, s'afegeixen pel final i es consumeixen pel principi. És el patró exacte en què una llista enllaçada és adequada: zero accés per índex, tot pels extrems.

Primer, la classe Reserva. Com que és una dada amb identitat pròpia i estat (atesa), la modelem com a classe, no com a record (04-07):

I la cua de reserves d'un material:

Ús complet:

Fixa't en tres decisions deliberades d'aquest codi:

• posicioDe recorre amb for-each, mai amb get(i). Sobre una LinkedList, el bucle indexat seria O(n²).
• cancellarUltimaDe fa servir descendingIterator i it.remove(): l'iterador ja té el node, així que l'eliminació és O(1) real. És el cas legítim de l'apartat 3.
• avancar és honest sobre el seu cost: el remove(Object) és O(n) perquè cal localitzar la reserva; només l'addFirst és O(1). Aquest mètode seria el primer candidat a revisar si la cua creixés molt, i una PriorityQueue (05-07) resoldria millor el problema de les urgències.

I una nota final de disseny: encara que LinkedList funciona bé aquí, la declaració canònica d'una cua és Deque<Reserva> pendents = new ArrayDeque<>(). S'ha fet servir LinkedList perquè a més necessitem removeIf i recorreguts, i perquè aquest era el seu cas natural; a 05-07 veuràs la versió amb ArrayDeque i per què sol ser millor.

Recórrer una LinkedList amb for indexat. for (int i = 0; i < llista.size(); i++) llista.get(i) és O(n²): cada get recorre la cadena des d'un extrem. Amb 100 000 elements passa de mil·lisegons a minuts. Fes servir sempre for-each o un iterador.

Creure que add(i, e) és O(1) a LinkedList. La inserció sí que ho és; arribar a l'índex i no. El mètode complet és O(n). Només els extrems i les insercions via iterador són O(1) de debò.

Triar LinkedList "perquè insereix més ràpid" sense mesurar. A la pràctica perd gairebé sempre per localitat de memòria cau i per consum de memòria. Comença per ArrayList i canvia només amb dades a la mà.

Fer servir LinkedList com a cua quan existeix ArrayDeque. ArrayDeque és més ràpid i ocupa menys. L'única raó per preferir LinkedList és necessitar List i Deque a la mateixa variable, o admetre elements null.

Confondre get/remove amb peek/poll. Sobre una llista buida, getFirst() i removeFirst() llancen NoSuchElementException; peekFirst() i pollFirst() retornen null. Tria segons si la cua buida és normal o és un error.

Modificar la llista mentre hi ha un ListIterator viu. Qualsevol llista.add, llista.remove o llista.clear directe invalida l'iterador i provoca ConcurrentModificationException a l'operació següent. Mentre l'iterador existeixi, tot hi passa per ell.

Oblidar que it.add(x) no torna a visitar el que s'ha inserit. És el que evita el bucle infinit, i és el correcte; però si esperaves que el nou element s'avalués, no passarà.

Ordenar una LinkedList sovint. sort aboca a un array, ordena i reconstrueix tota la cadena de nodes. Si ordenaràs amb freqüència, fes servir ArrayList; si necessites ordre permanent, TreeSet o PriorityQueue (05-06, 05-07).

Consell: declara per la interfície que reflecteixi l'ús. Si és una llista, List<X> l = new ArrayList<>(). Si és una cua, Deque<X> d = new ArrayDeque<>(). Declarar LinkedList<X> només es justifica quan necessites les dues cares alhora.

Consell: LinkedList és un magnífic exercici mental. Implementar-la a mà —amb nodes, prev i next— ensenya més sobre punters i estructures de dades que molts llibres. Però en producció, ArrayList.

Escriu HistorialOperacions que guardi les últimes N operacions del catàleg (cadenes com ara "alta:978-0000000001"), fent servir una LinkedList com a estructura interna:

• void registrar(String operacio): afegeix al final i, si se supera el màxim, elimina la més antiga (la primera).
• String ultima() i String mesAntiga(): sense eliminar-les, retornant null si és buit.
• List<String> enOrdreInvers(): de la més recent a la més antiga, amb descendingIterator.
• int eliminarPerPrefix(String prefix): elimina totes les que comencin per aquest prefix i retorna quantes n'ha tret.

Justifica en comentaris quines operacions són O(1) reals i quines no.

Escriu un mètode estàtic void inserirSeparadors(List<Material> cataleg) que recorri un catàleg ja ordenat per tipus i insereixi, abans del primer material de cada tipus, un Material especial de tipus separador (fes servir un Llibre amb títol "--- LLIBRES ---" o crea una petita classe Separador extends Material).

Ha de funcionar amb ListIterator i sense provocar ConcurrentModificationException ni bucles infinits. Explica per què la inserció no es torna a visitar.

Afegeix després una versió inserirSeparadorsMalament que intenti el mateix amb un for-each i documenta què falla exactament.

Escriu BancDeProves que compari ArrayList i LinkedList en quatre escenaris, amb escalfament previ i amb protecció contra l'eliminació de codi pel JIT:

1. Afegir N elements al final.
2. Recórrer amb for-each sumant.
3. Inserir 10 000 elements pel principi.
4. Eliminar per criteri amb removeIf.

Imprimeix una taula amb els temps i escriu, en un comentari final, la teva conclusió raonada i l'advertiment sobre JMH.

Solució 1

Prova:

Aquest és el cas d'ús ideal de LinkedList: una finestra lliscant. Cada registre afegeix per un extrem i treu per l'altre, totes dues O(1) reals. Amb ArrayList, cada remove(0) desplaçaria tota la llista. Dit això, la resposta professional per a una finestra lliscant és ArrayDeque (05-07), que fa el mateix amb un array circular, sense nodes i sense pressió sobre el recol·lector.

Solució 2

La seqüència previous() → add(...) → next() mereix una explicació acurada. Després d'it.next() el cursor és darrere del material actual, però el separador ha d'anar davant. previous() retrocedeix el cursor a la posició anterior (i retorna el mateix material, que descartem). add insereix aquí i deixa el cursor darrere del que s'ha inserit, és a dir, encara davant del material. next() el torna a saltar per continuar.

Aquest avanç automàtic del cursor després d'add és exactament el que impedeix el bucle infinit: l'element inserit mai no és retornat per next(). Si add no ho fes, el next() següent retornaria el separador, el tipus del qual tampoc no coincidiria amb tipusAnterior, i s'inseriria un altre separador, indefinidament.

I sobre la versió incorrecta, hi ha dues fallades apilades: la ConcurrentModificationException i, més de fons, que cataleg.add(x) insereix al final, no on estàs recorrent. És un bon recordatori que el for-each no coneix la seva pròpia posició.

Solució 3

Sortida típica (els valors absoluts varien molt segons la màquina; el que importa és la relació):

Conclusió raonada. LinkedList guanya en un sol escenari, el 3, i el guanya per molt: inserir pel principi és el seu terreny natural. En els altres tres perd, i en el recorregut —l'operació més freqüent en qualsevol programa real— és unes set vegades més lenta amb la mateixa complexitat O(n): la diferència és purament localitat de memòria cau.

L'escenari 4 és especialment revelador. removeIf és O(n) en totes dues i elimina en O(1) en totes dues (per iterador), però LinkedList continua perdent, perquè recórrer els nodes dispersos domina el temps total.

I l'observació decisiva: si afegeixes al banc de proves un ArrayDeque amb addFirst, l'escenari 3 baixa a aproximadament 1 ms, guanyant a totes dues. És a dir, fins i tot en l'únic cas on LinkedList guanya ArrayList, no és la millor eina disponible. Per això la recomanació pràctica és: ArrayList per a llistes, ArrayDeque per a cues i piles, LinkedList gairebé mai.

Repeteix l'advertiment amb cada número que vegis: per a decisions de rendiment reals, mesura amb JMH sobre la teva càrrega de treball concreta.

Ja saps què és una llista doblement enllaçada: una cadena de nodes amb prev, item i next, sense array, sense capacitat i sense índexs. Entens el que això implica de debò: ~28 bytes per element enfront dels ~4 d'un ArrayList, i nodes dispersos pel heap que destrueixen la localitat de memòria cau i fan que recórrer-la sigui unes quantes vegades més lent encara que la complexitat sigui la mateixa O(n). Has vist al codi del mateix JDK que node(index) recorre la cadena, i amb això has desmuntat el mite: inserir i esborrar és O(1) només si ja tens la posició, cosa que passa únicament als extrems i a través d'un iterador; arribar-hi per índex costa O(n).

Tens la taula comparativa operació per operació i la conclusió honesta que se'n deriva: ArrayList guanya gairebé sempre, perquè System.arraycopy és una instrucció de bloc nativa, perquè la memòria cau domina, perquè els nodes pressionen el recol·lector i perquè les insercions "al mig" gairebé mai no ho són. Saps que el mateix coautor del Framework la considera prescindible avui, i que el seu nínxol real no és ser una List sinó ser un Deque, terreny en què ArrayDeque la supera. També saps llegir l'error de rendiment que més s'hi cola: un for indexat sobre una LinkedList és O(n²) disfressat.

Coneixes la seva doble naturalesa List + Deque i tota la família d'operacions pels extrems, amb la distinció entre la variant que llança excepció (getFirst, removeFirst) i la que retorna null (peekFirst, pollFirst) —que 05-07 desenvoluparà—. I domines el ListIterator: el cursor que viu entre elements, el recorregut bidireccional, add i set durant el recorregut, per què el que s'insereix no es torna a visitar i per què és l'única forma correcta d'inserir mentre recorres.

Saps mesurar amb honestedat: escalfar la JVM, consumir els resultats perquè el JIT no elimini els bucles, desconfiar dels números absoluts i recórrer a JMH quan la decisió importi de debò. I per damunt de tot, has adoptat el criteri professional: mesura abans d'optimitzar, perquè canviar ArrayList per LinkedList "perquè insereix més ràpid" és, gairebé sempre, empitjorar el programa.

BiblioTech ha guanyat la classe Reserva i una CuaReserves que encua pel final, atén pel principi, cancel·la mitjançant iterador descendent en O(1) real i caduca les reserves antigues amb removeIf. És l'únic punt del projecte on una llista enllaçada estava justificada, i tot i així has vist per què a 05-07 la reescriuràs amb ArrayDeque.

I queda una debilitat que ja s'està fent insuportable. Cataleg.eliminar(referencia) recorre la llista sencera. GestorPrestecs.retornar(referencia, dia) recorre la llista sencera. CuaReserves.posicioDe(empleat) recorre la llista sencera. Cada vegada que BiblioTech ha de trobar alguna cosa pel seu identificador, mira un per un. Amb cinc materials és gratis; amb cinquanta mil, cada cerca són cinquanta mil comparacions, i agrupar préstecs per empleat amb bucles imbricats és O(n²).

A la lliçó següent, HashMap, això s'acaba. Veuràs l'estructura que troba un element per la seva clau en temps constant sense importar quants n'hi hagi: com funciona la funció hash, què són els cubells, què passa quan dues claus col·lideixen, per què el factor de càrrega és 0,75 i què passa en un rehash. I allà es complirà per fi la promesa que es va fer al mòdul 3: veuràs amb una demostració pràctica per què equals i hashCode havien d'anar sempre junts, i què li passa exactament a un objecte que entra en un mapa amb un dels dos mal implementat.