Nel 2009, ho sfidato me stesso a scrivere un post sul blog a settimana per tutto l’anno. Avevo letto che il modo migliore per guadagnare più traffico verso un blog era quello di pubblicare in modo coerente. Un post a settimana sembrava un obiettivo realistico a causa di tutte le idee di articoli che avevo, ma si è scoperto che ero ben a corto di 52 idee. Ho scavato in alcuni capitoli mezzi scritti che sarebbero poi diventati Professional JavaScript e ho trovato un sacco di materiale su argomenti classici dell’informatica, tra cui strutture dati e algoritmi. Ho preso quel materiale e l’ho trasformato in diversi post nel 2009 e (e alcuni nel 2012), e ho avuto un sacco di feedback positivi su di essi.

Ora, al decimo anniversario di quei post, ho deciso di aggiornare, ripubblicare ed espandere su di essi usando JavaScript nel 2019. È stato interessante vedere cosa è cambiato e cosa no, e spero che vi piacciano.

Cos’è una lista collegata?

Una lista collegata è una struttura dati che memorizza più valori in modo lineare. Ogni valore in una lista collegata è contenuto in un proprio nodo, un oggetto che contiene i dati insieme a un link al nodo successivo della lista. Il collegamento è un puntatore ad un altro oggetto nodo o null se non c’è un nodo successivo. Se ogni nodo ha solo un puntatore ad un altro nodo (più frequentemente chiamato next) allora la lista è considerata una lista collegata singolarmente (o solo lista collegata) mentre se ogni nodo ha due collegamenti (di solito previous e next) allora è considerata una lista doppiamente collegata. In questo post, mi concentrerò sulle liste collegate singolarmente.

Perché usare una lista collegata?

Il vantaggio principale delle liste collegate è che possono contenere un numero arbitrario di valori mentre usano solo la quantità di memoria necessaria per quei valori. Preservare la memoria era molto importante nei vecchi computer dove la memoria era scarsa. A quel tempo, un array integrato in C richiedeva di specificare quanti elementi l’array potesse contenere e il programma avrebbe riservato quella quantità di memoria. Riservare quella memoria significava che non poteva essere usata per il resto del programma o per qualsiasi altro programma in esecuzione allo stesso tempo, anche se la memoria non veniva mai riempita. Su macchine con poca memoria, si poteva facilmente esaurire la memoria disponibile usando gli array. Le liste collegate furono create per aggirare questo problema.

Anche se originariamente erano intese per una migliore gestione della memoria, le liste collegate divennero popolari quando gli sviluppatori non sapevano quanti elementi un array avrebbe contenuto alla fine. Era molto più facile usare una lista collegata e aggiungere valori come necessario piuttosto che indovinare accuratamente il numero massimo di valori che un array avrebbe potuto contenere. Come tale, le liste collegate sono spesso usate come base per le strutture dati incorporate in vari linguaggi di programmazione.

Il tipo incorporato in JavaScript Arraynon è implementato come una lista collegata, sebbene la sua dimensione sia dinamica ed è sempre la migliore opzione per iniziare. Potresti passare tutta la tua carriera senza aver bisogno di usare una lista collegata in JavaScript, ma le liste collegate sono ancora un buon modo per imparare a creare le tue strutture dati.

Il design di una lista collegata

La parte più importante di una lista collegata è la sua struttura a nodi. Ogni nodo deve contenere alcuni dati e un puntatore al nodo successivo della lista. Ecco una semplice rappresentazione in JavaScript:

class LinkedListNode { constructor(data) { this.data = data; this.next = null; }}

Nella classe LinkedListNode, la proprietà data contiene il valore che l’elemento della lista collegata deve conservare e la proprietà next è un puntatore al prossimo elemento della lista. La proprietà next inizia come null perché non si conosce ancora il nodo successivo. Puoi quindi creare una lista collegata usando la classe LinkedListNode come questa:

// create the first nodeconst head = new LinkedListNode(12);// add a second nodehead.next = new LinkedListNode(99);// add a third nodehead.next.next = new LinkedListNode(37);

Il primo nodo in una lista collegata è tipicamente chiamato testa, quindi l’identificatore head in questo esempio rappresenta il primo nodo. Il secondo nodo viene creato e assegnato a head.next per creare una lista con due elementi. Un terzo nodo viene aggiunto assegnandolo a head.next.next, che è il puntatore next del secondo nodo della lista. Il puntatore next del terzo nodo della lista rimane null. L’immagine seguente mostra la struttura dei dati risultante.

La struttura di una lista collegata ti permette di attraversare tutti i dati seguendo il puntatore next di ogni nodo. Ecco un semplice esempio di come attraversare una lista collegata e stampare ogni valore sulla console:

let current = head;while (current !== null) { console.log(current.data); current = current.next;}

Questo codice usa la variabile current come puntatore che si muove attraverso la lista collegata. La variabile current è inizializzata alla testa della lista e il ciclo while continua fino a quando current è null. All’interno del ciclo, il valore memorizzato sul nodo current viene stampato e poi il puntatore next viene seguito fino al nodo successivo.

La maggior parte delle operazioni delle liste collegate usa questo algoritmo di attraversamento o qualcosa di simile, quindi comprendere questo algoritmo è importante per capire le liste collegate in generale.

La classe LinkedList

Se steste scrivendo una lista collegata in C, potreste fermarvi a questo punto e considerare il vostro compito completo (anche se usereste una struct invece di una classe per rappresentare ogni nodo). Tuttavia, nei linguaggi orientati agli oggetti come JavaScript, è più usuale creare una classe per incapsulare questa funzionalità. Ecco un semplice esempio:

const head = Symbol("head");class LinkedList { constructor() { this = null; }}

La classe LinkedList rappresenta una lista collegata e conterrà metodi per interagire con i dati che contiene. L’unica proprietà è una proprietà simbolo chiamata head che conterrà un puntatore al primo nodo della lista. Una proprietà simbolo è usata al posto di una proprietà stringa per rendere chiaro che questa proprietà non è destinata ad essere modificata al di fuori della classe.

Aggiungere nuovi dati alla lista

Aggiungere un elemento in una lista collegata richiede di percorrere la struttura per trovare la posizione corretta, creare un nuovo nodo, e inserirlo al suo posto. L’unico caso speciale è quando la lista è vuota, nel qual caso si crea semplicemente un nuovo nodo e lo si assegna a head:

const head = Symbol("head");class LinkedList { constructor() { this = null; } add(data) { // create a new node const newNode = new LinkedListNode(data); //special case: no items in the list yet if (this === null) { // just set the head to the new node this = newNode; } else { // start out by looking at the first node let current = this; // follow `next` links until you reach the end while (current.next !== null) { current = current.next; } // assign the node into the `next` pointer current.next = newNode; } }}

Il metodo add() accetta un singolo argomento, qualsiasi dato, e lo aggiunge alla fine della lista. Se la lista è vuota (this è null) allora si assegna this uguale al nuovo nodo. Se la lista non è vuota, allora è necessario attraversare la lista già esistente per trovare l’ultimo nodo. La traversata avviene in un ciclo while che parte da this e segue i next collegamenti di ogni nodo fino a quando non si trova l’ultimo nodo. L’ultimo nodo ha una proprietà next uguale a null, quindi è importante fermare l’attraversamento a quel punto piuttosto che quando current è null (come nella sezione precedente). Potete quindi assegnare il nuovo nodo a quella proprietà next per aggiungere i dati nella lista.

La complessità del metodo add() è O(n) perché dovete attraversare l’intera lista per trovare la posizione per inserire un nuovo nodo. Potete ridurre questa complessità a O(1) tracciando la fine della lista (di solito chiamata coda) oltre alla testa, permettendovi di inserire immediatamente un nuovo nodo nella posizione corretta.

Recuperare i dati dalla lista

Le liste collegate non permettono un accesso casuale al suo contenuto, ma potete comunque recuperare i dati in qualsiasi posizione attraversando la lista e restituendo i dati. Per farlo, aggiungerete un metodo get() che accetta un indice basato su zero dei dati da recuperare, come questo:

class LinkedList { // other methods hidden for clarity get(index) { // ensure `index` is a positive value if (index > -1) { // the pointer to use for traversal let current = this; // used to keep track of where in the list you are let i = 0; // traverse the list until you reach either the end or the index while ((current !== null) && (i < index)) { current = current.next; i++; } // return the data if `current` isn't null return current !== null ? current.data : undefined; } else { return undefined; } }}

Il metodo get() prima controlla che index sia un valore positivo, altrimenti ritorna undefined. La variabile i è usata per tenere traccia di quanto in profondità è andato l’attraversamento nella lista. Il ciclo stesso è la stessa traversata di base che avete visto prima con l’aggiunta della condizione che il ciclo dovrebbe uscire quando i è uguale a index. Ciò significa che ci sono due condizioni sotto le quali il ciclo può uscire:

1. current è null, il che significa che la lista è più corta di index.
2. i è uguale a index, il che significa che current è il nodo nella posizione index.

Se current è null allora viene restituito undefined e altrimenti current.data. Questo controllo assicura che get() non darà mai un errore per un index che non si trova nella lista (anche se si potrebbe decidere di dare un errore invece di restituire undefined).

La complessità del metodo get() va da O(1) quando si rimuove il primo nodo (non è necessario alcun attraversamento) a O(n) quando si rimuove l’ultimo nodo (è necessario attraversare l’intera lista). È difficile ridurre la complessità perché è sempre necessaria una ricerca per identificare il valore corretto da restituire.

Rimozione dei dati da una lista collegata

Rimozione dei dati da una lista collegata è un po’ complicata perché è necessario assicurarsi che tutti i next puntatori rimangano validi dopo la rimozione di un nodo. Per esempio, se volete rimuovere il secondo nodo in una lista a tre nodi, dovrete assicurarvi che la proprietà next del primo nodo ora punti al terzo nodo invece che al secondo. Saltare il secondo nodo in questo modo lo rimuove effettivamente dalla lista.

L’operazione di rimozione è in realtà due operazioni:

1. Trova l’indice specificato (lo stesso algoritmo di get())
2. Rimuovi il nodo a quell’indice

Trovare l’indice specificato è lo stesso del metodo get(), ma in questo ciclo devi anche tenere traccia del nodo che viene prima di current perché dovrai modificare il puntatore next del nodo precedente.

Ci sono anche quattro casi speciali da considerare:

1. La lista è vuota (nessuna traversata è possibile)
2. L’indice è minore di zero
3. L’indice è maggiore del numero di elementi della lista
4. L’indice è zero (rimozione della testa)

Nei primi tre casi, l’operazione di rimozione non può essere completata, e quindi ha senso lanciare un errore; il quarto caso speciale richiede la riscrittura della proprietà this. Ecco come appare l’implementazione di un metodo remove():

class LinkedList { // other methods hidden for clarity remove(index) { // special cases: empty list or invalid `index` if ((this === null) || (index < 0)) { throw new RangeError(`Index ${index} does not exist in the list.`); } // special case: removing the first node if (index === 0) { // temporary store the data from the node const data = this.data; // just replace the head with the next node in the list this = this.next; // return the data at the previous head of the list return data; } // pointer use to traverse the list let current = this; // keeps track of the node before current in the loop let previous = null; // used to track how deep into the list you are let i = 0; // same loops as in `get()` while ((current !== null) && (i < index)) { // save the value of current previous = current; // traverse to the next node current = current.next; // increment the count i++; } // if node was found, remove it if (current !== null) { // skip over the node to remove previous.next = current.next; // return the value that was just removed from the list return current.data; } // if node wasn't found, throw an error throw new RangeError(`Index ${index} does not exist in the list.`); }}

Il metodo remove() controlla prima due casi speciali, una lista vuota (this è null) e un index che è minore di zero. Un errore viene lanciato in entrambi i casi.

Il prossimo caso speciale è quando index è 0, il che significa che state rimuovendo la testa della lista. La nuova testa della lista dovrebbe essere il secondo nodo della lista, quindi puoi impostare this uguale a this.next. Non importa se c’è un solo nodo nella lista perché this finirebbe per essere uguale a null, il che significa che la lista è vuota dopo la rimozione. L’unico trucco è quello di memorizzare i dati della testa originale in una variabile locale, data, in modo da poterli restituire.

Con tre dei quattro casi speciali presi in considerazione, si può ora procedere con un traversal simile a quello trovato nel metodo get(). Come accennato in precedenza, questo ciclo è leggermente diverso in quanto la variabile previous è usata per tenere traccia del nodo che appare appena prima di current, poiché questa informazione è necessaria per rimuovere propabilmente un nodo. Simile a get(), quando il ciclo esce current può essere null, indicando che l’indice non è stato trovato. Se ciò accade, viene lanciato un errore, altrimenti, previous.next viene impostato a current.next, rimuovendo effettivamente current dalla lista. I dati memorizzati su current vengono restituiti come ultimo passo.

La complessità del metodo remove() è la stessa di get() e va da O(1) quando si rimuove il primo nodo a O(n) quando si rimuove l’ultimo nodo.

Rendere la lista iterabile

Per poter essere usata con il ciclo JavaScript for-of e la destrutturazione degli array, le collezioni di dati devono essere iterabili. Le collezioni integrate in JavaScript come Array e Set sono iterabili per default, e potete rendere le vostre classi iterabili specificando un metodo generatore Symbol.iterator sulla classe. Io preferisco implementare prima un metodo generatore values() (per corrispondere al metodo che si trova nelle classi di raccolta integrate) e poi avere Symbol.iterator che chiama direttamente values().

Il metodo values() deve solo fare una traversata di base della lista e yield i dati che ogni nodo contiene:

class LinkedList { // other methods hidden for clarity *values(){ let current = this; while (current !== null) { yield current.data; current = current.next; } } () { return this.values(); } }

Il metodo values() è marcato con un asterisco (*) per indicare che è un metodo generatore. Il metodo attraversa la lista, usando yield per restituire ogni dato che incontra. (Notate che il metodo Symbol.iterator non è segnato come generatore perché sta restituendo un iteratore dal metodo generatore values().)

Utilizzare la classe

Una volta completata, puoi usare l’implementazione della lista collegata come questa:

const list = new LinkedList();list.add("red");list.add("orange");list.add("yellow"); // get the second item in the listconsole.log(list.get(1)); // "orange"// print out all itemsfor (const color of list) { console.log(color);}// remove the second item in the list console.log(list.remove(1)); // "orange" // get the new first item in the listconsole.log(list.get(1)); // "yellow"// convert to an arrayconst array1 = ;const array2 = ;

Questa implementazione di base di una lista collegata può essere completata con una proprietà size per contare il numero di nodi nella lista, e altri metodi familiari come indexOf(). Il codice sorgente completo è disponibile su GitHub al mio progetto Computer Science in JavaScript.

Conclusione

Le liste collegate non sono qualcosa che probabilmente userete ogni giorno, ma sono una struttura dati fondamentale in informatica. Il concetto di usare nodi che puntano l’uno all’altro è usato in molte altre strutture di dati e sono integrate in molti linguaggi di programmazione di livello superiore. Una buona comprensione di come funzionano le liste collegate è importante per una buona comprensione generale di come creare e usare altre strutture dati.

Per la programmazione JavaScript, è quasi sempre meglio usare le classi di raccolta integrate come Array piuttosto che crearne di proprie. Le classi di raccolta incorporate sono già state ottimizzate per l’uso in produzione e sono ben supportate in tutti gli ambienti di esecuzione.

Si consiglia di utilizzare le classi di raccolta incorporate.