In questo nuovo articolo della serie parliamo di strutture dati cercando di capire cosa sono e a cosa servono nell'ambito dell'informatica.

Come al solito faremo un discorso molto generale senza entrare troppo in dettagli tecnici e senza addentrarci nel codice di cui ci occuperemo in seguito.

In questo momento è importante fare una panoramica sull’argomento così da comprendere il ruolo delle strutture dati nell'ambito dello sviluppo del software.

Per prima cosa partiamo dalla definizione:

una struttura dati è un agglomerato di elementi caratterizzati da una organizzazione sistematica e su cui è possibile effettuare delle operazioni.

Cosa significa in concreto?

Essenzialmente in una struttura dati abbiamo un insieme di elementi che sono organizzati secondo un criterio logico ben preciso e su cui è possibile effettuare delle operazioni.

Quindi ciò che differenzia una struttura dati da un'altra è appunto l’organizzazione dei suoi elementi e di conseguenza le operazioni applicabili agli stessi.

Non interessa la natura degli elementi, che possono sfruttare i tipi primitivi di un certo linguaggio di programmazione come valori numerici, stringhe, caratteri, ecc. oppure dei tipi definiti dal programmatore.

Questi ultimi sono i cosiddetti abstract data type (ADT) ovvero tipi che non sono supportati nativamente dal linguaggio ma creati dallo sviluppatore.

La prima classificazione distingue le strutture lineari da quelle non lineari.

Nelle prime gli elementi sono organizzati in forma di sequenza per cui abbiamo un primo elemento, un secondo, un terzo e così via.

Nelle altre la disposizione degli elementi non è sequenziale per cui non c’è un ordinamento posizionale tra gli stessi.

Vediamo alcuni esempi pratici con riferimento a situazioni reali che affrontiamo quotidianamente.

Tra le strutture lineari troviamo prima di tutto le liste che sono l'equivalente degli elenchi ovvero una struttura in cui gli elementi sono organizzati secondo una sequenza e su cui si possono effettuare delle operazioni di lettura, inserimento e cancellazione.

L'accesso è consentito a qualsiasi elemento e in qualsiasi posizione.

Quindi abbiamo le code che sono ancora delle sequenze, ma in questo caso abbiamo un elemento di testa e uno di coda che rappresentano gli unici due punti di accesso alla struttura. In una coda non possiamo accedere direttamente ad un qualsiasi elemento ma solo all'elemento di testa (l'unico che può essere processato) e a quello di coda dove è possibile effettuare degli inserimenti.

L'esempio più banale è rappresentato dalle file che facciamo quotidianamente al supermercato piuttosto che all'ufficio postale, dove in genere le persone vengono servite secondo l'ordine di arrivo.

In gergo si parla anche di strutture FIFO (First In First out), ovvero il primo elemento che arriva è anche il primo che esce, cioè che viene elaborato.

In base a questa organizzazione degli elementi le operazioni possibili sono quelle di lettura/scrittura del valore, l’inserimento di un nuovo elemento ma solo in fondo alla coda e l’estrazione dalla testa.

In informatica le code si usano spesso per gestire i messaggi nell’ambito della comunicazione nei sistemi distribuiti.

Proseguiamo con le pile che sono sostanzialmente delle strutture lineari in cui cambia la modalità di inserimento e gestione degli elementi. Basti pensare ad una pila di fascicoli: se devo inserire un nuovo fascicolo non posso inserirlo in un punto qualsiasi ma devo posizionarlo in cima, per cui la testa della pila è l'unico punto di accesso sia per gli inserimenti che per le rimozioni che per gli accessi in lettura/scrittura.

In effetti l'elemento che può essere estratto è il primo, cioè quello posizionato sopra tutti gli altri, così come l'inserimento può essere effettuato posizionando un nuovo elemento al di sopra dell’attuale posto in cima.

Anche in questo caso sono diverse le applicazioni in ambito informatico come la gestione delle chiamate alle funzioni: in pratica durante l'esecuzione di un programma è possibile che vengano chiamate delle procedure o funzioni per cui il controllo sequenziale passa ad un altro blocco di codice e in seguito bisogna gestire il rientro a partire dall'istruzione successiva a quella della chiamata.

Se il modulo chiamato a sua volta ne chiama un altro, per gestire in maniera ordinata il rientro si utilizzano delle strutture dati chiamate stack, termine inglese per indicare proprio la pila e la gestione degli elementi avviene appunto in maniera inversa rispetto all'inserimento, ovvero nella modalità LIFO (Last In First Out).

In poche parole l'ultimo elemento inserito è il primo ad essere estratto.

Passando alle strutture non lineari parliamo in primo luogo dei grafi, un termine che a molti potrebbe non dire nulla.

In realtà è una struttura dati utilizzata quotidianamente nel mondo reale in quanto permette di rappresentare delle relazioni tra oggetti.

Ogni volta che si parla di reti questo termine è associato al concetto di grafo: per esempio una rete di trasporti (ferroviaria o autostradale) è un esempio di grafo in cui le stazioni o i caselli possono essere considerati come i nodi connessi tra loro attraverso delle tratte che rappresentano i cosiddetti archi.

Anche le reti sociali, meglio note come social network che utilizziamo quotidianamente, si basano proprio su questo tipo di strutture dati che permettono di creare delle relazioni: quando ad esempio all'interno di Facebook o di altri social abbiamo la possibilità di vedere i nostri amici, gli amici degli amici, tutti i vari collegamenti e di conseguenza tutti i suggerimenti di amicizia o collegamento che ci arrivano direttamente dalla piattaforma, tutto ciò è reso possibile dal fatto che le singole persone sono rappresentate da nodi interconnessi tra loro.

Quindi anche se io non sono direttamente in contatto con un'altra persona posso arrivarci attraverso i miei collegamenti e ciò è possibile grazie ad una serie di algoritmi che permettono di visitare i grafi secondo determinati criteri.

Gli stessi stessi navigatori satellitari ci permettono di trovare il percorso più breve per andare da un luogo ad un altro basandosi sul fatto che tutta la rete stradale viene rappresentata nella forma di un grafo, più precisamente un grafo pesato in cui ciascuna tratta (arco) ha dei valori associati, come ad esempio la distanza, il tempo di percorrenza dipendente dallo stato del traffico o da eventuali interruzioni ecc.

Gli algoritmi interni permettono di tracciare il percorso sulla base di determinati criteri che abbiamo impostato. (GUARDA IL VIDEO DI APPROFONDIMENTO)

I grafi sono importanti anche perché da loro deriva un altro tipo di struttura dati: gli alberi.

Anche in questo caso si tratta di qualcosa che utilizziamo quotidianamente forse in maniera inconsapevole. Pensiamo all'albero genealogico o in generale a tutte quelle situazioni in cui abbiamo la necessità di rappresentare delle informazioni organizzate in forma gerarchica tipo l’organigramma di una azienda.

E in effetti l'albero è fatto proprio in questo modo: c'è un nodo alla base, ovvero la radice, e poi altri nodi che sono organizzati in vari livelli. Si utilizza tutta una nomenclatura che include appunto radice, foglie (cioè nodi che non hanno figli), fratelli (nodi allo stesso livello) ecc.

Riguardo alle operazioni anche per gli alberi esistono degli algoritmi di visita con cui esaminare i nodi e ovviamente tutte quelle operazioni con cui possiamo fare inserimenti di nuovi nodi oppure potarne alcuni con tutti i loro discendenti (in gergo sottoalberi).

Proseguiamo la nostra disamina con gli insiemi, ripresi in qualche modo dal mondo della matematica.

Anche in questo caso non possiamo parlare di strutture lineari perché di fatto in un insieme non abbiamo una sequenza, non si può individuare un primo elemento, un secondo e così via.

Ovviamente si possono definire delle relazioni d'ordine ma in linea di massima quando abbiamo un insieme possiamo stabilire l'appartenenza o meno di un elemento, fare le classiche operazioni insiemistiche come unione, intersezione, differenza.

Dopo questa semplice panoramica affrontiamo il tema della specifica delle strutture dati, ovvero la loro definizione ad un alto livello, in gergo livello astratto, cioè indipendente da una particolare implementazione.

Infatti stiamo descrivendo ciascuna struttura dati per come è fatta e per quali operazioni supporta. Poi bisogna considerare le diverse possibili implementazioni, cioè come realizzare materialmente queste strutture dati utilizzando un determinato linguaggio di programmazione.

Tipicamente per una struttura dati esistono differenti implementazioni.

Ad esempio nel caso di Java le liste si possono realizzare utilizzando gli array con tutte le problematiche ad essi associate, prima fra tutte l’allocazione di memoria indipendente dal tasso di riempimento effettivo della struttura dati.

Ad esempio se decido di utilizzare un array per memorizzare 100 elementi devo allocare tutta la memoria necessaria a prescindere dal fatto che la mia lista avrà un elemento, due elementi oppure tutti e 100.

In alternativa si possono realizzare le linked list in cui i singoli elementi vengono allocati all'occorrenza e mantengono un riferimento alla posizione del nodo successivo così da ricostruire l'intera struttura dati.

Evidentemente questa soluzione è più flessibile ed efficiente perché la struttura occupa meno spazio e può crescere o decrescere dinamicamente.

Tutto ciò ha un costo maggiore dovuto alla gestione più complessa (ad esempio per inserimento e rimozione di nodi e aggiornamento dei puntatori) rispetto ad un array dove l’accesso è immediato, specificando l’indice che individua la posizione dell’elemento richiesto.

Un discorso simile può essere fatto per i grafi che offrono diverse implementazioni come le matrici di adiacenza o di incidenza e le liste di incidenza e di cui parleremo in dettaglio in un altro articolo.

In conclusione evidenziamo come le strutture dati siano strettamente legate agli algoritmi, che ne hanno bisogno per elaborare i loro dati.

Molto spesso la scelta della struttura dati adeguata al tipo di problema da risolvere può incidere notevolmente sull’efficienza dell'algoritmo.

Ritornando ai nostri esempi è chiaro che se dobbiamo gestire tanti messaggi e processarli secondo l'ordine di arrivo bisogna ricorrere ad una coda. Se dobbiamo lavorare su una rete di trasporti, su una rete sociale o di altro genere è chiaro che dovremo orientarci verso i grafi perché sono le strutture più adeguate in tale contesto.

In linea di massima si possono scegliere anche altre strutture dati non ottimizzate per quel genere di problema. Magari si arriverà allo stesso risultato ma facendo un numero maggiore di operazioni, impiegando più memoria e rendendo gli algoritmi ancora più complessi.

Quindi conoscere le strutture dati, sapere in quali contesti utilizzarle, è fondamentale per progettare algoritmi efficienti e quindi software di qualità.

[VIDEO YOUTUBE]