Liste concatenate

Aggiungere un valore in testa a una lista concatenata cambia due puntatori, che la lista contenga 4 valori o 4 milioni.

Valori che puntano al successivo

Un array tiene i valori uno accanto all'altro, ed è per questo che cambiarne la testa costa caro. Una lista concatenata abbandona questa regola. Ogni valore vive in un piccolo record tutto suo chiamato nodo, e i nodi possono stare in qualsiasi punto della memoria. Gli appunti del corso 6.006 del MIT descrivono un nodo con due campi: l'elemento e next, un puntatore al nodo seguente. La lista ricorda soltanto il primo nodo, chiamato head (testa). Il next dell'ultimo nodo è null, e segna la fine.

Per leggere la lista parti da head e segui i puntatori next uno alla volta, come una catena di bigliettini in cui ognuno dice dove è nascosto il successivo. Questo ha un costo. Non esiste una formula per l'indirizzo del quarto nodo, quindi prendere il valore in posizione i significa visitare i + 1 nodi. Il MIT indica get at(i) per una lista concatenata come O(n), mentre l'array lo faceva in un passo.

// un nodo per valore: { value, next }
let head = null;
for (const v of [4, 30, 7, 12]) head = { value: v, next: head };
// percorri la lista
for (let n = head; n !== null; n = n.next) console.log(n.value); // 12, 7, 30, 4

Modificare la lista ricollegando

Il vantaggio arriva quando modifichi la lista. Per mettere un nuovo valore in testa, crea un nodo il cui next è l'attuale head, poi fai puntare head al nuovo nodo. Due modifiche di puntatori, e nient'altro si sposta. Eliminare il nodo in testa è una sola modifica: fai puntare head a head.next. Confrontalo con l'array, dove le stesse operazioni spostavano ogni valore.

Nel mezzo, il lavoro sta nel trovare il punto giusto. Per inserire in posizione i cammini fino al nodo subito prima (i visite), poi fai le stesse due modifiche di puntatori: new.next = prev.next, poi prev.next = new. L'ordine conta. Se imposti prima prev.next, il resto della lista va perso, perché niente punta più a esso. Nel laboratorio un passo è un nodo visitato o un puntatore modificato, quindi inserire in posizione 2 in una lista di 4 nodi costa 2 visite più 2 modifiche, cioè 4 passi.

Quando usarla

Una lista concatenata è adatta quando la maggior parte delle modifiche avviene in un punto di cui hai già un puntatore, come la testa, e raramente ti serve la posizione i. Code e pile si possono costruire con liste concatenate, e così le catene dentro una tabella hash nella prossima unità. Esistono varianti. Una lista doppiamente concatenata dà a ogni nodo anche un puntatore prev, così puoi camminare all'indietro ed eliminare un nodo in un passo una volta che lo hai. Tenere un puntatore tail oltre a head rende economico aggiungere in fondo.

Nel JavaScript di tutti i giorni scrivi raramente una lista concatenata, perché gli array sono ben ottimizzati e le cache dei processori moderni favoriscono i valori memorizzati uno accanto all'altro. L'idea conta comunque: alberi, grafi e molte strutture delle librerie sono costruiti con nodi e puntatori proprio in questo modo.