Che cos'è una struttura di dati?

Le strutture di dati combinano tipi di dati primitivi come numeri, caratteri, booleani e numeri interi in un formato coeso. Da solo, ognuno di questi tipi di dati primitivi possiede un solo valore. Quando vengono combinati in una struttura di dati, invece, abilitano operazioni di livello superiore come l'ordinamento, la ricerca, l'inserimento e l'eliminazione.

Immaginiamo ad esempio un team di vendita che desidera tenere traccia dei dati di vendita giornalieri. Invece di registrare ogni punto dati separatamente, il team può memorizzare questi dati in un tipo di struttura dati chiamata "array". (Per maggiori informazioni, vedi "Tipi di strutture di dati").

In Python, l'array è simile a questo:

daily_sales = [500, 800, 600, 1200, 950]

L'uso di un array consente al team di tenere insieme tutti questi dati, recuperare facilmente i punti dati quando necessario ed eseguire funzioni sia sui singoli elementi che sull'intero array.

I programmatori informatici si affidano alle strutture di dati per creare applicazioni efficaci. Nei campi dell'informatica e della data science, le strutture di dati sono essenziali per sistemi operativi, database, siti web, grafica, analytics, blockchain, applicazioni di machine learning (ML) e altro ancora.

Poiché le strutture di dati sono fondamentali per scrivere codice efficace, sono spesso tra le prime lezioni insegnate ai principianti della programmazione, nonché un argomento comune nei colloqui per i candidati al lavoro di programmazione informatica.

Le strutture di dati sono importanti perché consentono ai computer di elaborare più facilmente set di informazioni grandi e complessi. Organizzando logicamente gli elementi di dati, le strutture di dati aumentano l'efficienza del codice informatico e rendono il codice più semplice da comprendere.

I programmatori utilizzano le strutture di dati per migliorare la velocità e la forza degli algoritmi, che sono insiemi di istruzioni per completare un'attività informatica. Nella programmazione informatica, questa combinazione è nota come "DSA" per le strutture e gli algoritmi di dati. Il DSA aiuta i programmatori ad indirizzare la duplice sfida della complessità temporale e della complessità spaziale.

La complessità temporale è una misura del tempo impiegato da un algoritmo per completare un'attività in base alla quantità di input. La complessità spaziale è una misura della quantità di memoria utilizzata dall'algoritmo in base alla quantità di input.

Utilizzando la notazione metrica matematica Big O, i programmatori possono misurare la complessità dello spazio e del tempo, per poi determinare quali strutture di dati e algoritmi forniscono il tempo di esecuzione più veloce e la massima efficienza dello spazio per un'attività specifica.

Le strutture di dati svolgono anche un ruolo importante nella programmazione dinamica, una tecnica per risolvere rapidamente problemi complessi.

La programmazione dinamica utilizza la ricorsione per separare un problema in componenti più piccoli. Quindi, il programma trova soluzioni per tali componenti e riassembla le sotto-soluzioni in una soluzione completa al problema originale.

Le strutture di dati rendono possibile la programmazione dinamica dando al programma un modo per archiviare e recuperare ogni sotto-soluzione e mantenendo gli elementi di dati organizzati logicamente durante il processo.

Ad esempio, i valori calcolati possono essere mantenuti in una matrice. Invece di ricalcolare questi valori quando è il momento di formulare la soluzione completa, il programma può recuperarli dall'array.

Con queste funzionalità, i programmatori possono risparmiare tempo e risolvere i problemi in modo più efficiente.

Le strutture di dati sono divise in 2 categorie principali: lineari e non lineari.

In una struttura di dati lineare, i dati sono disposti in linea, con ogni elemento posizionato uno dopo l'altro in sequenza. Questa disposizione semplifica l'attraversamento e l'accesso agli elementi in ordine.

Le strutture di dati lineari sono considerate semplici e facili da implementare. Le più comuni in questa categoria includono array, elenchi collegati e code.

In una struttura di dati non lineare, la logica organizzativa è qualcosa di diverso da una disposizione lineare e sequenziale. Ad esempio, i punti dati possono essere ordinati in modo gerarchico o collegati in una rete.

Poiché non sono collegati tra loro in una singola linea, gli elementi di una struttura non lineare non possono essere attraversati e accessibili in un unico passaggio, come avviene in una struttura di dati lineare. Alcuni esempi di strutture dati non lineari includono alberi e grafi.

Esistono diversi tipi di strutture di dati che i programmatori possono utilizzare a seconda dei sistemi che stanno costruendo e di ciò che devono fare con i dati. Le più comuni includono:

• Array
• Code
• Stack
  
• Elenchi collegati
• Alberi
• Grafici
• Hash 

Gli array sono uno dei tipi di strutture di dati più basilari e ampiamente utilizzati. Memorizzano elementi di dati simili in posizioni di memoria adiacenti. Questa struttura consente di localizzare e accedere facilmente agli oggetti dello stesso tipo.

Usi: gli usi comuni degli array includono l'ordinamento, la memorizzazione, la ricerca e l'accesso ai dati. Gli array possono essere utilizzati anche come base per l'implementazione di altre strutture di dati, come code e stack.

Esempio: una array di punteggi medi di soddisfazione dei clienti di un call center ogni giorno potrebbe essere simile a questo:

average_customer_score = [4, 3.5, 3.7, 4.1, 3.4, 4.9]

Una struttura di dati in coda esegue le operazioni sui dati in un ordine predeterminato chiamato "FIFO" ("first in, first out"). Ciò significa che il primo elemento di dati da aggiungere sarà il primo ad essere rimosso. I programmatori utilizzano spesso questa struttura di dati per creare code di priorità, simili a delle liste d'attesa.

Usi: le strutture di dati delle code possono essere utilizzate per determinare il brano successivo in una playlist, il prossimo utente ad avere accesso a una stampante condivisa o la prossima chiamata a cui rispondere in un call center.

Esempio: i clienti in attesa di parlare con un rappresentante del call center potrebbero essere messi in una coda come questa:

queue = [customer 1, customer 2, customer 3]

Quando un rappresentante è disponibile, si connette automaticamente con il primo cliente in coda, che viene poi rimosso dall'elenco. Ora, la coda avrà questo aspetto:

queue = [customer 2, customer 3]

Come una coda, una struttura di dati in stack esegue le operazioni sui dati in un ordine predeterminato. Tuttavia, invece del formato FIFO, gli stack utilizzano il formato "LIFO", che sta per "last in, first out", in cui k'ultimo elemento di dati da aggiungere sarà il primo a essere rimosso.

Usi: gli stack possono essere utilizzati per garantire la corretta apertura e chiusura di parentesi o tag nei codici informatici, tenere traccia della cronologia recente del browser o annullare le operazioni recenti in un'applicazione.

Esempio: molte app utilizzano gli stack per tenere traccia delle azioni degli utenti in modo che possano essere annullate facilmente. Ad esempio, un editor di testo potrebbe mantenere uno stack simile al seguente:

recent_actions = [typing ‘.’, space, typing ‘T’]

Quando un utente preme il pulsante "annulla", l'azione più recente nello stack, ovvero "digitazione di 'T'", viene annullata. Ora lo stack si presenta così:

recent_actions = [typing ‘.’, space]

Gli elenchi collegati memorizzano gli elementi di dati in un ordine lineare, in cui ogni elemento collegato all'elemento successivo nell'elenco. Questa struttura semplifica l'inserimento di nuovi elementi o l'eliminazione di quelli esistenti senza dover spostare l'intera raccolta di dati.

Usi: gli elenchi collegati vengono spesso utilizzati per inserimenti ed eliminazioni frequenti in scenari, come cronologie del browser web, playlist di lettori multimediali e operazioni di annullamento o ripristino nelle applicazioni.

Esempio: una versione semplificata di un elenco collegato di video in un lettore multimediale potrebbe essere simile a questa:

Video 1 – Video 2 – Video 3

Ogni oggetto nell'elenco punta a quello successivo, quindi quando il Video 1 è finito, indirizzerà il lettore multimediale ad avviare il Video 2. 

Una struttura di dati ad albero, talvolta chiamata albero di prefisso, è utile per stabilire relazioni gerarchiche tra gli elementi di dati. Un singolo nodo padre si trova in cima alla struttura ad albero, mentre i sottonodi figli si diramano nei livelli successivi sottostanti.

Diverse classi di alberi, come gli alberi di ricerca binari, gli alberi AVL e gli alberi b, hanno proprietà diverse e supportano funzioni diverse. Ad esempio, in un albero di ricerca binario, ogni nodo ha al massimo 2 figli. Questa struttura consente di supportare ricerche rapide di set di dati. 

Usi: gli alberi vengono spesso usati per rappresentare gerarchie nelle mappe organizzative, nei file system, nei sistemi di nomi di dominio, nell'indicizzazione dei database e negli alberi decisionali nelle applicazioni di machine learning.

Esempio:

Una struttura di dati a grafo organizza le relazioni tra oggetti diversi utilizzando vertici e edge. I vertici sono punti dati "rappresentati" da punti e le edge sono linee che collegano i vertici.

Ad esempio, su una mappa, le città sarebbero vertici e le strade che le collegano sarebbero edge. Su Facebook, gli utenti sarebbero i vertici e le amicizie che li uniscono sarebbero edge.

Usi: le strutture di dati a grafo vengono spesso utilizzate con algoritmi di ricerca che cercano dati all'interno di complesse reti di relazioni. Gli esempi più comuni includono le ricerche breadth-first, che effettuano ricerche tra i dati livello per livello, e le ricerche depth-first, che analizzano più livelli di dati per trovare informazioni.

Esempio:

Una struttura di dati hash, a volte chiamata "tabella hash" o "mappa hash", utilizza una funzione hash per memorizzare i valori dei dati. La funzione hash crea un hash, ovvero una chiave digitale univoca che corrisponde alla posizione di un valore di dati specifico in memoria.

La tabella hash contiene un indice ricercabile di ogni coppia hash e valore di dati che rende facile e veloce l'accesso, l'aggiunta e la rimozione di dati dalla tabella.

Usi: le strutture di dati hash possono aiutare a recuperare rapidamente i dati dalle rubriche telefoniche, dai dizionari e dagli elenchi del personale. Possono anche essere utilizzati per indicizzare database, memorizzare password e bilanciare il carico dei sistemi IT.

Esempio: una versione semplificata di una tabella hash che organizza l'elenco dei contatti di uno smartphone potrebbe essere simile a questa:

La funzione hash esegue la mappatura di ogni tasto all'indice appropriato. Quindi, quando un utente inserisce una chiave (il nome di un contatto), la tabella hash restituisce il valore associato allo stesso indice (il numero del contatto).

Le strutture di dati sono critiche nella progettazione di applicazioni software perché implementano forme concrete di tipi di dati astratti.

Un tipo di dati astratto è un modello matematico che classifica il comportamento di un tipo di dati e le operazioni che possono essere eseguite su di esso. Ad esempio, il tipo di dati astratto di una coda definisce il comportamento della coda (seguendo il principio di FIFO). La struttura di dati della coda fornisce un modo per formattare i dati in una coda, in modo tale che un programma per computer applichi il principio FIFO a quei dati.

Molti linguaggi di programmazione, come Python, Java e JavaScript, includono strutture dati integrate per aiutare gli sviluppatori a lavorare in modo più efficiente.

I casi d'uso comuni per le strutture di dati nei programmi per computer includono:

• Organizzazione e data storage
• Indicizzazione
• Scambio di dati
• Ricerca
• Scalabilità

Le strutture di dati possono memorizzare i dati in modo logico ed efficiente con alti livelli di persistenza, in modo che rimangano facilmente accessibili dai database e da altre applicazioni. Le strutture di dati possono anche fornire un'organizzazione logica per grandi quantità di dati in modo che possano essere ordinati, ordinati ed elaborati più facilmente.

Ad esempio, un sito web può utilizzare elenchi collegati per memorizzare i registri delle attività degli utenti. Gli elenchi registrano gli eventi in ordine cronologico e i collegamenti tra gli eventi dipingono un quadro completo di ciò che un utente fa durante ogni sessione.  

Le strutture di dati possono indicizzare le informazioni mappando i valori dei dati ai corrispondenti elementi di dati in un database, facilitando l'individuazione e l'accesso a tali record di dati.

Ad esempio, un sito di e-commerce può utilizzare una tabella hash per indicizzare i prodotti in categorie. Quando un utente desidera visualizzare solo una categoria, il sito web può utilizzare il valore hash per recuperare rapidamente tutti i prodotti correlati invece di cercare nel database di ogni singolo prodotto.

Le strutture di dati organizzano i dati in modo che possano essere facilmente condivisi tra le applicazioni. Ad esempio, molte app usano le code per gestire e inviare pacchetti su protocolli come TCP/IP. Le code aiutano a garantire che i pacchetti siano inviati e ricevuti nell'ordine in cui sono stati creati. 

Organizzando i dati in modo che siano più semplici da comprendere per le applicazioni e gli utenti finali, le strutture di dati facilitano la ricerca e l'individuazione dei dati.

Ad esempio, le strutture di dati in grafo possono rendere più facile per gli utenti trovare persone che conoscono sui siti di social media. Le strutture dati in grafo registrano le relazioni tra vertici o nodi. Gli algoritmi di ricerca possono seguire le connessioni da un nodo all'altro per individuare in modo efficiente gli utenti correlati.

Le strutture di dati supportano la scalabilità del sistema aiutando i programmi per computer a elaborare set di dati di grandi dimensioni, risolvere problemi complessi e utilizzare le risorse in modo più efficiente.

Ad esempio, sia le tabelle hash che le strutture ad albero possono semplificare l'individuazione delle informazioni rilevanti in set di dati di grandi dimensioni. Invece di ispezionare ogni elemento, i sistemi devono solo utilizzare la chiave giusta o seguire il percorso corretto attraverso l'albero. Questo aiuta a mantenere prestazioni elevate perché il sistema non ha bisogno di utilizzare troppe risorse per cercare tra enormi quantità di dati.