02. Strutture lineari dinamiche

Le strutture dati dinamiche prevedono l'allocazione dinamica della memoria e pertanto gli elementi possono essere inseriti nella struttura man mano che servono, collegati tra loro in modi diversi.

Le strutture dinamiche quindi, si ridimensionano in base all'occorrenza.

E' anche possibile, tuttavia, che il ridimensionamento della memoria sia solo "percepito" dall'utilizzatore ma non sia implementato realmente.


Pila o stack

Questa struttura dati si comporta come un contenitore con una sola apertura attraverso la quale quale è possibile inserire o estrarre elementi.

Gli elementi vengono impilati uno sull'altro ed è possibile estrarre di volta in volta solo l'elemento in cima alla pila.

La pila è una struttura di tipo LIFO, un acronimo che significa Last In First Out. In altri termini l'ultimo elemento inserito è il primo ad essere estratto.

A questa struttura si associano due funzioni, solitamente indicate con Push() e Pop(). La prima inserisce un elemento la seconda estrae l'elemento in testa.

E' possibile implementare questa struttura basandosi su un array. In questo caso la pila risultante appare all'utilizzatore come una struttura dinamica ma di fatto l'occupazione di memoria resta costante.

Coda o queue

Questa struttura dati si comporta come un tubo nel quale è possibile inserire elementi da un lato ed estrarli dal lato opposto. Come si capisce bene dalla metafora, il primo elemento ad essere inserito è anche il primo che può essere estratto. L'acronimo che si usa per caratterizzare una coda è FIFO, che significa First In First Out (il primo inserito è il primo ad essere estratto).

Le due funzioni tipiche che consentono di gestire questa struttura dati sono dette Enqueue() e Dequeue(). La prima è utilizzata per inserire un elemento nella coda, la seconda per estrarre elementi.

Lista

La lista è funzionalmente simile all'array con alcune importanti differenze implementative, che non sono facilmente percepite a livello funzionale.

Le liste, consentono di ospitare elementi eterogenei, indirizzabili tramite un indice.

A differenza degli array, le liste sono costruite dinamicamente e il tempo di accesso ai diversi elementi non è costante.

Inoltre è possibile inserire elementi in coda alla lista in qualsiasi momento.

Dizionario o array associativi

In questa struttura dinamica, ogni elemento è costituito da una coppia le cui due parti sono dette chiave e valore.

E' possibile paragonare un dizionario ad una lista in cui al posto degli indici si utilizzano delle generiche chiavi (ad esempio stringhe).

E' possibile eliminare elementi del dizionario che siano stati precedentemente inseriti nella struttura.