Le informazioni sono tutte intorno a noi.

Nel mondo del software, il modo in cui scegliamo di organizzare le nostre informazioni è metà della battaglia. Il punto però è questo: ci sono tanti modi per risolvere un problema. E quando si tratta di organizzare i nostri dati, ci sono molti strumenti che potrebbero funzionare per il lavoro. Il trucco è sapere quale strumento è quello giusto da usare.

Indipendentemente dalla lingua in cui iniziamo a programmare, una delle prime cose che incontriamo sono le strutture dei dati , che sono i diversi modi in cui possiamo organizzare i nostri dati; variabili , array , hash e oggetti sono tutti i tipi di strutture dati. Ma queste sono ancora solo la punta dell'iceberg quando si tratta di strutture dati; ce ne sono molti di più, alcuni dei quali iniziano a sembrare super complicati man mano che ne senti parlare.

Una di quelle cose complicate per me sono sempre state le liste collegate . Conosco gli elenchi concatenati da alcuni anni, ma non riesco mai a ricordarmeli. Ci penso davvero solo quando mi preparo (oa volte, nel bel mezzo di) un colloquio tecnico e qualcuno me ne chiede. Farò una piccola ricerca e penserò di aver capito di cosa si tratta, ma dopo alcune settimane li dimentico di nuovo. L'intera cosa è piuttosto inefficiente, e tutto deriva dal fatto che so che esistono, ma fondamentalmente non li capisco ! Quindi, è ora di cambiare la situazione e rispondere alla domanda: che diavolo è una lista collegata, comunque?

Strutture dati lineari

Se vogliamo davvero capire le basi delle liste collegate, è importante che parliamo di che tipo di struttura dati sono.

Una caratteristica degli elenchi concatenati è che sono strutture dati lineari , il che significa che esiste una sequenza e un ordine per il modo in cui vengono costruiti e attraversati. Possiamo pensare a una struttura dati lineare come un gioco di campana : per arrivare alla fine dell'elenco, dobbiamo scorrere tutti gli elementi nell'elenco in ordine o in sequenza . Le strutture lineari, tuttavia, sono l'opposto delle strutture non lineari. Nelle strutture dati non lineari , gli elementi non devono essere disposti in ordine, il che significa che potremmo attraversare la struttura dati in modo non sequenziale .

Potremmo non rendercene conto sempre, ma tutti i giorni lavoriamo con strutture dati lineari e non lineari! Quando organizziamo i nostri dati in hash (a volte chiamati dizionari ), stiamo implementando una struttura dati non lineare. Alberi e grafici sono anche strutture di dati non lineari che attraversiamo in modi diversi, ma ne parleremo più approfonditamente più avanti nel corso dell'anno.

Allo stesso modo, quando usiamo array nel nostro codice, stiamo implementando una struttura dati lineare! Può essere utile pensare agli array e agli elenchi collegati come simili nel modo in cui sequenziamo i dati. In entrambe queste strutture, l' ordine è importante . Ma cosa rende diversi gli array e gli elenchi collegati?

Gestione della memoria

Il principale fattore di differenziazione tra array ed elenchi collegati è il modo in cui utilizzano la memoria nelle nostre macchine. Quelli di noi che lavorano con linguaggi tipizzati dinamicamente come Ruby, JavaScript o Python non devono pensare a quanta memoria usa un array quando scriviamo il nostro codice giorno per giorno perché ci sono diversi livelli di astrazione che finiscono per con noi non doversi preoccupare affatto dell'allocazione della memoria.

Ma questo non significa che l'allocazione della memoria non avvenga! L'astrazione non è magia, è solo la semplicità di nascondere cose che non hai bisogno di vedere o affrontare tutto il tempo. Anche se non dobbiamo pensare all'allocazione della memoria quando scriviamo codice, se vogliamo veramente capire cosa sta succedendo in un elenco collegato e cosa lo rende potente, dobbiamo scendere al livello rudimentale.

Abbiamo già imparato a conoscere il binario e come i dati possono essere suddivisi in bit e byte. Proprio come caratteri, numeri, parole, frasi richiedono byte di memoria per rappresentarli, così fanno le strutture di dati.

Quando viene creato un array , è necessaria una certa quantità di memoria. Se avessimo 7 lettere da memorizzare in un array, avremmo bisogno di 7 byte di memoria per rappresentare quell'array. Ma avremmo bisogno di tutta quella memoria in un blocco contiguo . Vale a dire, il nostro computer avrebbe bisogno di individuare 7 byte di memoria libera, un byte accanto all'altro, tutti insieme, in un unico posto.

D'altra parte, quando nasce una lista concatenata , non ha bisogno di 7 byte di memoria tutti in un unico posto. Un byte potrebbe vivere da qualche parte, mentre il byte successivo potrebbe essere archiviato in un altro posto nella memoria! Gli elenchi collegati non devono occupare un singolo blocco di memoria; invece, la memoria che usano può essere dispersa ovunque .

La differenza fondamentale tra gli array e gli elenchi collegati è che gli array sono strutture di dati statiche , mentre gli elenchi collegati sono strutture di dati dinamiche . Una struttura dati statica richiede che tutte le sue risorse vengano allocate quando viene creata; ciò significa che anche se la struttura dovesse crescere o ridursi di dimensione e gli elementi dovessero essere aggiunti o rimossi, ha comunque sempre bisogno di una data dimensione e quantità di memoria. Se è necessario aggiungere più elementi a una struttura dati statica e questa non dispone di memoria sufficiente, è necessario copiare i dati di quell'array, ad esempio, e ricrearli con più memoria, in modo da poter aggiungere elementi a esso.

D'altra parte, una struttura dati dinamica può ridursi e crescere in memoria. Non ha bisogno di una quantità prestabilita di memoria da allocare per esistere, e le sue dimensioni e forma possono cambiare, e anche la quantità di memoria di cui ha bisogno può cambiare.

A questo punto, possiamo già iniziare a vedere alcune importanti differenze tra array ed elenchi collegati. Ma questo pone la domanda: cosa permette a una lista collegata di avere la sua memoria sparsa ovunque? Per rispondere a questa domanda, dobbiamo esaminare il modo in cui è strutturato un elenco collegato.

Parti di un elenco collegato

Un elenco collegato può essere piccolo o enorme, ma indipendentemente dalle dimensioni, le parti che lo compongono sono in realtà abbastanza semplici. Una lista collegata è composta da una serie di nodi , che sono gli elementi della lista.

Il punto di partenza della lista è un riferimento al primo nodo, che viene chiamato testa . Quasi tutte le liste collegate devono avere un'intestazione, perché questo è effettivamente l'unico punto di ingresso alla lista e a tutti i suoi elementi, e senza di essa, non sapresti da dove cominciare! La fine dell'elenco non è un nodo, ma piuttosto un nodo che punta a null o un valore vuoto.

Un singolo nodo è anche piuttosto semplice. Ha solo due parti: dati o le informazioni che il nodo contiene e un riferimento al nodo successivo .

Se riusciamo a capire questo, allora siamo a metà strada. Il modo in cui funzionano i nodi è super importante e super potente e potrebbe essere riassunto come segue:

Un nodo sa solo quali dati contiene e chi è il suo vicino.

Un singolo nodo non sa quanto è lungo l'elenco collegato e potrebbe non sapere nemmeno dove inizia o dove finisce. Tutto ciò che interessa a un nodo sono i dati che contiene e il nodo a cui fa riferimento il suo puntatore - il nodo successivo nell'elenco.

Ed è proprio questo il motivo per cui un elenco collegato non necessita di un blocco di memoria contiguo. Poiché un singolo nodo ha l '"indirizzo" o un riferimento al nodo successivo, non è necessario che risiedano l'uno accanto all'altro, come devono fare gli elementi in un array. Invece, possiamo semplicemente fare affidamento sul fatto che possiamo attraversare la nostra lista appoggiandoci ai riferimenti del puntatore al nodo successivo, il che significa che le nostre macchine non hanno bisogno di bloccare un singolo pezzo di memoria per rappresentare la nostra lista.

Questa è anche la spiegazione del motivo per cui gli elenchi collegati possono crescere e ridursi dinamicamente durante l'esecuzione di un programma. Aggiungere o rimuovere un nodo con un elenco collegato diventa semplice come riorganizzare alcuni puntatori, piuttosto che copiare gli elementi di un array! Tuttavia, ci sono anche alcuni inconvenienti negli elenchi collegati che non ti sto ancora menzionando, ma ne parleremo la prossima settimana.

Per ora, ci crogioleremo nella gloria di quanto siano fantastici gli elenchi collegati!

Elenchi per tutte le forme e dimensioni

Anche se le parti di un elenco collegato non cambiano, il modo in cui strutturiamo le nostre liste collegate può essere molto diverso. Come la maggior parte delle cose nel software, a seconda del problema che stiamo cercando di risolvere, un tipo di elenchi collegati potrebbe essere uno strumento migliore per il lavoro di un altro.

Gli elenchi collegati singolarmente sono il tipo più semplice di elenchi collegati, basato esclusivamente sul fatto che vanno in una sola direzione. C'è una singola traccia in cui possiamo attraversare l'elenco; iniziamo alla testa nodo ed attraversare dalla radice fino alla ultimo nodo, che terminerà in un vuoto nullo valore.

Ma proprio come un nodo può fare riferimento al suo successivo nodo vicino, può anche avere un puntatore di riferimento al suo nodo precedente! Questo è ciò che chiamiamo una lista doppiamente concatenata , perché ci sono due riferimenti contenuti all'interno di ogni nodo: un riferimento al nodo successivo , così come al nodo precedente . Questo può essere utile se volessimo essere in grado di attraversare la nostra struttura dati non solo in una singola traccia o direzione, ma anche all'indietro.

Ad esempio, se volessimo essere in grado di saltare tra un nodo e il nodo precedente senza dover tornare all'inizio della lista , una lista doppiamente collegata sarebbe una struttura dati migliore di una lista collegata singolarmente. Tuttavia, tutto richiede spazio e memoria, quindi se il nostro nodo dovesse memorizzare due puntatori di riferimento invece di uno solo, sarebbe un'altra cosa da considerare.

Un elenco collegato circolare è un po 'strano in quanto non termina con un nodo che punta a un valore nullo. Invece, ha un nodo che funge da coda dell'elenco (anziché il nodo principale convenzionale) e il nodo dopo il nodo di coda è l'inizio dell'elenco. Questa struttura organizzativa rende davvero facile aggiungere qualcosa alla fine della lista, perché puoi iniziare ad attraversarla dal nodo di coda , poiché il primo elemento e l'ultimo elemento puntano l'uno verso l'altro. Le liste collegate circolari possono iniziare a diventare davvero pazze perché possiamo trasformare sia una lista collegata singolarmente che una lista doppiamente collegata in una lista collegata circolare!

Ma non importa quanto sia complicato un elenco collegato, se possiamo ricordare i fondamenti di un nodo e come funziona e come sono strutturati i diversi riferimenti a puntatore nel nostro elenco, non esiste un elenco collegato che non possiamo affrontare!

La prossima settimana, nella parte 2 di questa serie, affonderemo i denti nella complessità spazio-temporale degli elenchi concatenati e nel modo in cui si confrontano con il loro cugino, l'array. Prometto che in realtà è molto più divertente di quanto sembri!

Risorse

Se pensi che gli elenchi collegati siano fantastici, dai un'occhiata a queste risorse utili.

1. Differenze tra array ed elenchi collegati , Damien Wintour
2. Strutture dati: array vs elenchi collegati , mycodeschool
3. Elenchi collegati: The Basics , Dr. Edward Gehringer
4. Introduzione agli elenchi collegati , Dr. Victor Adamchik
5. Strutture dati e implementazioni , Dr. Jennifer Welch
6. Strutture di dati statiche e strutture di dati dinamiche , Ayoma Gayan Wijethunga