Uno dei primi argomenti che viene trattato nei corsi accademici, è senza dubbio, quello delle strutture dati. Quando si parla di dati in informatica, si ci riferisce alla rappresentazione digitale della descrizione elementare di una realtà. Il dato è uno dei pilastri fondamentali dell’informatica e saperlo manipolare è uno degli obiettivi primari. Una delle prime problematiche da risolvere è come rappresentare e come memorizzare i dati in un contenitore logico che sia di facile gestione. A questo, ci pensano le strutture dati. Una struttura dati è una entità utilizzata per organizzare un insieme di dati all’interno della memoria del computer, attraverso l’uso di un opportuno algoritmo.
Il più delle volte la nostra conoscenza si limita all’utilizzo di una struttura dati ad un alto livello di astrazione, ma capire come si comportano le diverse strutture di dati ai livelli inferiori è fondamentale quando si tratta di selezionare quella ottimale per una determinata attività. In questo articolo analizzeremo le strutture dati più diffuse in ordine di complessità via via sempre maggiore.
L’array
L’array è la più semplice e più utilizzata struttura dati in qualsiasi linguaggio di programmazione. L’array memorizza un numero fisso di dati di un singolo tipo di dati. Gli elementi in un array vengono memorizzati in un blocco di slot di memoria contigui. Per questo motivo, agli elementi di un array vengono assegnati numeri consecutivi, a partire da 0, come loro “indici”.
È possibile accedere al valore contenuto nel singolo elemento utilizzando il suo indice univoco. L’accesso a un elemento utilizzando l’indice ha una complessità di Θ (1). La lettura o l’aggiornamento degli elementi dell’array utilizzano il medesimo indice. L’attraversamento degli array è più veloce rispetto alla maggior parte delle altre strutture di dati, proprio per la posizione contigua degli elementi dell’array.
Tuttavia, l’inserimento o l’eliminazione di un elemento da un array è un’attività a volte complessa e dispendiosa in termini di tempo. Durante l’inserimento, tutti gli elementi nell’array vengono copiati in un array appena creato con dimensioni maggiori e il nuovo elemento viene aggiunto alla fine del nuovo array. Anche l’eliminazione è implementata in modo simile per ridurre la dimensione dell’array. Questo comporta numerosi svantaggi in termini di prestazioni.
Gli array possono essere monodimensionali oppure multidimensionali (array di array) e questo li rende una buona scelta per memorizzare matrici e vettori. Gli array vengono spesso utilizzati per implementare altre strutture di dati come liste, heap, stack e code.
La coda
La struttura dei dati della coda è simile alla coda che vediamo nella nostra vita quotidiana: la prima persona che entra in coda è la prima persona che ha la prossima possibilità di uscire dalla coda. Per questo si dice che la coda è una struttura FIFO, First In First Out. Ogni nuovo elemento di dati aggiunto alla coda viene memorizzato all’estremità posteriore e ogni elemento rimosso dalla coda viene prelevato dall’inizio della coda.
Le classiche operazioni che si possono effettuare sulla coda sono quelle per inserire ed estrarre gli elementi, cioè enqueue e dequeue.
- Enqueue: Inserimento di un elemento alla fine della coda. Un elemento appena aggiunto diventa l’elemento posteriore della coda.
- Dequeue: rimozione di un elemento dalla parte anteriore della coda. Entrambe le operazioni di accodamento e rimozione dalla coda hanno una complessità temporale di Θ (1).
Le code vengono utilizzate per implementare i buffer. Il multithreading utilizza le code per gestire le attività in attesa di essere implementate dai thread.
La pila
Gli stack (o pile) sono abbastanza simili alle code, ma sono implementati sul concetto di LIFO, Last In First Out invece che FIFO. L’ultimo elemento che entra nella pila è il primo ad uscire. Pensiamo ad esempio a una pila di piatti in cui l’ultimo piatto che viene aggiunto è il primo che verrà rimosso per essere lavato.
Le tipiche operazioni sulla pila sono:
- push: inserisce un nuovo elemento in cima alla pila. Un elemento appena aggiunto diventa il nuovo top.
- pop: rimuove un elemento dalla cima della pila.
Entrambe le operazioni push e pop hanno una complessità temporale di Θ (1).
Le pile sono utilizzate per gestire e valutare espressioni matematiche. Sono anche utilizzati negli algoritmi che utilizzano una procedura di backtracking. Anche nelle funzioni ricorsive viene applicato il concetto di stack. Chi ha la fortuna di programmare in C, ricorderà il fatidico errore “stack overflow”, il quale è legato, tra gli altri fattori, anche alla dimensione dello stack che viene creato per gestire la ricorsione. Quando è usata troppa memoria nello stack si dice che avviene un overflow, e si verifica un crash del programma.
Lista collegata
La lista collegata, a differenza di un array è una struttura dati dinamica. Questo significa che il numero di elementi di dati memorizzati in un elenco collegato può facilmente espandersi o ridursi dinamicamente senza allocare in anticipo lo spazio in memoria. Ciò permette alle liste collegate una maggiore flessibilità rispetto agli array che hanno una dimensione fissa.
Le liste collegate memorizzano ogni elemento come un oggetto separato. Ciò significa che gli elementi di una lista collegata non vengono archiviati in slot di memoria contigui, invece, ogni elemento (chiamato nodo) contiene un puntatore alla posizione del nodo successivo. Questi puntatori mantengono la connessione tra i nodi. Oltre al puntatore al nodo successivo, un nodo contiene anche un campo dati.
Ci sono due nodi importanti in un elenco collegato: head e tail.
- head: rappresenta il primo nodo della lista collegata (testa).
- tail: rappresenta l’ultimo nodo della lista collegata (coda). Il puntatore di tail è impostato su null, poichè appunto rappresenta l’ultimo elemento.
Quando si inserisce un nuovo elemento, il nuovo campo dati viene archiviato in una posizione particolare in memoria e il puntatore nel nodo precedente viene aggiornato per puntare al nuovo nodo. Il nuovo nodo memorizza il puntatore precedentemente memorizzato nel nodo precedente.
Quando si elimina un nodo, al nodo che precede il nodo eliminato viene assegnato il puntatore precedentemente memorizzato nel nodo eliminato.
Con gli elenchi collegati, non è possibile accedere direttamente a un singolo elemento senza attraversare l’elenco a partire dalla testa. Ciò conferisce all’operazione di accesso una complessità temporale di Θ (n).
Esistono diverse tipologie di liste, divise per tipologia di collegamento. Possiamo infatti avere:
- Lista collegata singolarmente: in questo caso un nodo contiene solo un puntatore al nodo successivo.
- Lista a doppio collegamento: in questo caso un nodo contiene puntatori al nodo precedente e successivo. In tal modo, l’attraversamento dell’elenco può essere eseguito in entrambi i sensi (avanti e indietro).
- Lista collegata circolare: in questo caso il puntatore della coda punta alla testa invece che null, e quindi, un elenco collegato circolare non ha una coda, ma ha solo una testa.
Le liste collegate vengono utilizzati per implementare strutture di dati come stack, code e grafici. Quando si eseguono operazioni di algebra polinomiale, vengono utilizzate liste concatenate per memorizzare le costanti.
Grafo
Una particolare e utilissima struttura dati è il grafo. Il grafo è costituito da un numero finito di elementi di dati chiamati vertici. Alcune coppie di questi vertici sono collegate tra loro tramite gli archi o spigoli. Due vertici collegati da un arco sono adiacenti l’uno all’altro.
I grafici possono essere classificati utilizzando diversi attributi. Una di queste categorizzazioni è rappresentata dai grafici orientato e dai grafici non orientati .
- Nei grafi orientati, uno spigolo che collega due vertici ha un vertice iniziale e un vertice finale. Quando si attraversa il grafico, lo spigolo può essere attraversato solo dal vertice iniziale al vertice finale, cosi come stabilito dall’orientamento.
- Nei grafici non orientati, uno spigolo può essere attraversato in entrambe le direzioni senza limitazioni.
Le applicazioni di social media come Facebook utilizzano grafici per rappresentare i propri utenti come vertici e le loro amicizie come spigoli. L’algoritmo di posizionamento delle pagine di Google utilizzava grafici per rappresentare pagine web e link che le collegavano. Google Maps utilizza grafici per rappresentare la rete stradale e i tragitti da seguire.
Albero binario
Un albero binario è, per certi versi, simile a un grafo ordinato. La differenza tra i due è che, in un albero binario, i dati vengono memorizzati in una struttura gerarchica, dove i nodi di livello superiore sono chiamati genitori e i nodi di livello inferiore sono chiamati figli. Il motivo per cui gli alberi binari vengono utilizzati più spesso degli alberi n-ary per la ricerca è che gli alberi n-ary sono più complessi, ma di solito non offrono un reale vantaggio di velocità.
Diamo un’occhiata ad alcuni termini associati agli alberi binari.
- Radice: il nodo nella parte superiore dell’albero. Non ha un nodo padre.
- Foglia: un nodo nella parte inferiore dell’albero. Non ha nodi figli.
- Chiave: il valore dei dati archiviati in un nodo.
- Sottostruttura: l’albero costituito da tutti i discendenti di un nodo
Esistono numerosi alberi binari speciali come Binary Search Tree, Treap, Binary Tries e Heap.
Albero di ricerca binario
Un nodo in un albero binario può avere un solo genitore e al massimo due figli. L’albero binario di ricerca (BST) memorizza i valori dei dati in ordine ordinato. Il figlio sinistro di un nodo in un albero binario di ricerca deve avere un valore minore del genitore e il figlio destro deve avere un valore maggiore del genitore. Ad esempio il nodo 27 è la radice che ha due figli (14 e 35). Ciascun nodo che sia padre, deve rispettare la regola già descritta.
Il vantaggio principale di un BST è la possibilità di cercare rapidamente i dati memorizzati. La complessità temporale della ricerca di un elemento memorizzato in un BST è O (log n).
Gli alberi binari di ricerca vengono utilizzati per implementare mappe e impostare oggetti nei linguaggi di programmazione
Heap
Heap è un altro caso speciale di alberi binari. La chiave della radice viene confrontata con la chiave dei suoi figli per disporli in un modo specifico. Esistono due tipi di heap.
- Heap Max: la chiave del genitore è maggiore o uguale a quella del figlio. Il nodo radice memorizza il valore massimo nel set di dati specificato.
- Heap Min: la chiave del genitore è minore o uguale a quella del figlio. Il nodo radice memorizza il valore minimo nel set di dati specificato.
Se consideriamo un set di valori interi, possiamo costruire un heap max e un heap min come segue:
L’inserimento, l’eliminazione e l’estrazione delle funzioni negli head max e min una complessità temporale pari a O (log n). Ma trovare il massimo (o il minimo) ha solo una complessità temporale di O (1).
Gli heap vengono utilizzati nell’implementazione dell’algoritmo heapsort. Gli heap vengono utilizzati anche per implementare le code di priorità perché il primo elemento dell’heap memorizza sempre il valore con la priorità massima (o minima).
Tabella hash
La tabella hash è una delle strutture dati più efficienti che possiamo utilizzare quando vogliamo mantenere la velocità delle operazioni di ricerca e inserimento su un set di dati di grandi dimensioni. Ogni valore di dati memorizzato in una tabella hash è associato a una chiave che fornisce un accesso rapido al valore memorizzato se conosciamo la chiave. Pensiamo a un sistema di registrazione degli studenti in cui ogni studente ha un ID studente univoco che può essere utilizzato come chiave per memorizzare i propri dati in una tabella hash.
Le tabelle hash utilizzano array per memorizzare i valori dei dati. La chiave viene utilizzata per trovare l’indice all’interno della matrice in cui è memorizzato il valore. Ma come fanno le tabelle hash a mappare queste chiavi con i loro valori?
Uno dei metodi che possono essere utilizzati è l’indirizzamento diretto. Utilizza una mappatura uno a uno: ogni chiave punta alla posizione esatta in cui sono archiviati i dati. Ma questo approccio non utilizza la memoria in modo efficiente, soprattutto quando il numero di coppie chiave-valore aumenta e le chiavi diventano di dimensioni maggiori. Per ottimizzare questo problema, le tabelle hash usano le funzioni hash.
Una funzione hash viene usata per mappare i valori dei dati alle rispettive chiavi. Converte un intervallo di valori chiave in un intervallo di indici di matrice. L’indice o il valore generato passando la chiave alla funzione hash è chiamato valore hash. Ecco un esempio di funzione hash.
h(k) = k % m
- h è la funzione hash
- h (k) è il valore hash corrispondente alla chiave k
- k è la chiave
- m è la dimensione della tabella hash. Una buona scelta per m è un numero primo che non è vicino a una potenza di 2.
Consideriamo i valori hash di diverse chiavi con m = 20.
- k = 1001, h (k) = 1001% 20 = 1
- k = 1055, h (k) = 1055% 20 = 15
- k = 20123, h (k) = 20123% 20 = 3
Per i valori k = 1001, 1055 e 20123, i valori associati vengono archiviati rispettivamente negli indici 1, 15 e 3 nella tabella hash.
Consideriamo adesso il valore hash della chiave 2021, che risulta 1. Tuttavia, abbiamo visto precedentemente che il valore associato alla chiave 1001 è memorizzato proprio all’indice 1 nella tabella hash. Quando i valori hash generati da due chiavi sono simili, avviene una collisione. Le tabelle hash utilizzano tecniche come il concatenamento e l’indirizzamento aperto per risolvere il problema della collisione.
Le tabelle hash hanno la complessità del tempo di ricerca e inserimento di O (1).
Le tabelle hash vengono utilizzate per implementare gli indici del database. I compilatori utilizzano tabelle hash per identificare le parole chiave in un linguaggio di programmazione. I computer utilizzano tabelle hash per collegare i nomi dei file con i relativi percorsi.
