struttureDinamiche

Nella costruzione di un programma non sempre è possibile stabilire il numero esatto di dati che dovrà usare quando sarà eseguito, per questo sono essenziali le strutture dati dinamiche come i vettori. Poniamo che ad esempio io debba leggere un elenco di nomi da un file su disco: quanti saranno quei nomi?

I vettori sono strutture dinamiche perché posso dimensionarli a tempo di esecuzione hanno però un limite: la loro lunghezza viene stabilita al momento della creazione e non può più essere variata né tanto meno posso essere rimossi elementi da un vettore. Quando queste condizioni risultano essere limitanti si può far ricorso ad altre strutture che possono cambiare la loro dimensione durante l'esecuzione del programma.

ArrayList

Molto spesso quando serve avere una struttura che si espande dinamicamente in java si usa java.util.ArrayList. Questo oggetto è molto flessibile e permette di inserire/rimuovere/leggere elementi da qualsiasi punto dell'elenco che implementa. Alcuni metodi utili dell'ArrayList sono:

add( elemento )

aggiunge "elemento" in fondo alla coda

add( posizione, elemento)

inserisce "elemento" alla posizione specificata

get( posizione )

ritorna l'elemento presente alla posizione specificata

size()

ritorna il numero di elementi presenti nella lista

remove(posizione)

rimuove l'elemento presente alla posizione specificata

Proviamo a vedere un esempio:

// alla creazione di un ArrayiList specifico il tipo degli oggetti che conterrà
ArrayList<String> elenco = new ArrayList<String>();
elenco.add("cane");     // elenco conterrà ["cane"] 
elenco.add("gatto");    // elenco conterrà ["cane", "gatto"]
nome = elenco.get(0);
System.out.println(nome); // stamperà "cane"
nome = elenco.get(1);
System.out.println(nome); // stamperà "gatto"
elenco.add(0,"pollo");  // elenco conterrà ["pollo", "cane", "gatto"]
nome = elenco.get(0);
System.out.println(nome); // stamperà pollo 
System.out.println(elenco.size()); // stamperà "3" 
elenco.remove(1);       // elenco conterrà ["pollo", "gatto"]
System.out.println(elenco.size()); // stamperà "2"

Le code

Una coda (a volte chiamata anche lista) è in pratica l'implemantazione informatica di una coda alla cassa del supermercato: può contenere un elenco di oggetti di lunghezza indefinita (nel senso che si espande e contrae all'occorrenza) e nella sua forma più elementare ci consente soltanto due operazioni: inserire oggetti ad un estremo ed astrarli dall'altro. Questa struttura è normalmente classificata come "FIFO": First In First Out, il primo elemento che entra è anche il primo ad uscire.

L'implementazione di base di questo oggetto prevede due sole operazioni:

inserisci

inserisce un elemento in fondo alla coda

estrai

estrae un elemento dalla testa della coda

Nella foto di esempio sono stati inserirti nell'ordine i numeri 44, 31, 17 e alla fine 10. Quando si andranno ad estrarre il primo numero ad uscire sarà il 44. Una volta estratto un elemento questo sparisce dalla struttura dati: nel nostro esempio dopo aver estratto il 44 la coda sarà composta da tre soli elementi: "10, 17, 31".

Alcune implementazioni delle code permettono anche di fare ulteriori operazioni come ad esempio controllare quanto è lunga una coda o inserire/cancellare elementi in posizioni arbitrarie.

Le code nella libreria standard java

Formalmente nella libreria standard java ci sono diversi oggetti che implementano le code, va bene ad esempio java.util.LinkedList che in realtà ha qualche metodo in più rispetto all'implemtazione di base, vediamo un esempio:

String nome;
LinkedList<String> codaDiNomi = new LinkedList<String>();
codaDiNomi.add("mario"); // la coda ha un solo elemento: "mario"
codaDiNomi.add("lucia"); // in fondo alla coda adesso c'è "lucia"
codaDiNomi.add("paola"); // in fondo alla coda adesso c'è "paola"
nome = codaDiNomi.remove();  // "mario" perché è l'elemento in testa alla coda
System.out.println( nome );
nome = codaDiNomi.element(); // "lucia" perché è l'elemento in testa alla coda
System.out.println( nome );
nome = codaDiNomi.remove();  // ancora "lucia" perché element() non lo aveva estratto
System.out.println( nome );

Le pile

Una pila gestisce gli oggetti un po' come... la pila dei piatti: l'ultimo piatto che metto sulla pila è il primo che prenderò quando mi servirà un piatto. Anche la pila può contenere un elenco di oggetti di lunghezza indefinita (nel senso che si espande e contrae all'occorrenza) e nella sua forma più elementare ci consente soltanto due operazioni: inserire oggetti ad un estremo ed astrarli dalla stessa parte. Questa struttura è normalmente classificata come "LIFO": Last In First Out, l'ultimo elemento che entra è anche il primo ad uscire.

L'implementazione di base di questo oggetto prevede due sole operazioni:

inserisci

inserisce un elemento in testa alla pila

estrai

estrae un elemento dalla testa della pila (una volta estratto non si trova più nella pila)

È possibile che una implementazione della pila prevada due ulteriori operazioni:

leggiTesta

legge l'elemento in testa alla pila senza estrarlo

vuota

ritorna true se la pila è vuota

Nella foto di esempio sono stati inserirti nell'ordine i numeri 44, 31, 17 e alla fine 10. Quando si andranno ad estrarre il primo numero ad uscire sarà il 10. Una volta estratto un elemento questo sparisce dalla struttura dati. Nel nostro esempio dopo aver estratto il 10 la pila sarà composta da tre soli elementi: "17, 31, 44".

Le pile nella libreria standard java

Nella libreria standard di java esiste una implementazione funzionante dell'oggetto pila: java.util.Stack che fa esattamente quello che dovrebbe fare una pila e una cosa in più: ci permette di guardare il primo elemento senza estrarlo. L'operazione di inserimento si chiama push mentre quella di estrazione pop, sono i nomi standard che si usano in questo contesto. Il metodo peek guarda in cima alla pila ma non rimuove l'elemento. Proviamo a vedere un esempio:

String nome;
Stack<String> pilaDiNomi = new Stack<String>();
pilaDiNomi.push("mario"); // la pila ha un solo elemento: "mario"
pilaDiNomi.push("lucia"); // in testa (in cima) alla pila adesso c'è "lucia"
pilaDiNomi.push("paola"); // in testa alla pila adesso c'è "paola"
nome = pilaDiNomi.pop();  // "paola" perché è l'elemento in testa alla pila
System.out.println( nome );
nome = pilaDiNomi.peek(); // "lucia" perché è l'elemento in testa alla pila
System.out.println( nome );
nome = pilaDiNomi.pop();  // ancora "lucia" perché peek() non lo aveva estratto
System.out.println( nome );
nome = pilaDiNomi.pop();  // "mario", quello rimasto in cima alla pila
System.out.println( nome );