liste

first in first out

Le strutture dati dinamiche sono essenziali per sviluppare software: come sarebbe possibile creare un programma che elabora un elenco di numeri senza usare i vettori?

Questa struttura dati ha però un limite: la sua 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 a delle strutture dati che possono cambiare la loro dimensione durante l'esecuzione del programma.

Prima di addentrarci nella loro realizzazione dobbiamo ricordare che in Java le variabili di tipo non base sono in pratica dei riferimenti a zone di memoria in cui l'oggetto viene memorizzato. Questi riferimenti non sono però direttamente manipolabili come in altri linguaggi.

Proviamo avedere...

TextField b = new TextField("pluto");
TextField a = new TextField("paperino");
String x;
a=b;
x = a.getText();

Quanto varrà la variabile x alla fine del frammento di programma sopra?

errore no, il programma è corretto "paperino"no, a=b cambia l'oggetto riferito dalla variabile a "pluto" giusto, a=b rende a un riferimento allo stesso oggetto a cui si riferisce b

E che fine ha fatto l'oggetto (il TextField) che contiene la scritta "paperino"? È andato perso! La memoria occupata dall'oggetto verrà resa libera automaticamente da java (da una parte della JVM che si chiama garbage collector).

Le liste

La struttura dati da cui iniziamo è la lista: può contenere un elenco di oggetti e nella sua forma più elementare ci consente di inserire oggetti e di estrarli nello stesso ordine in cui sono stati inseriti. Questa struttura è normalmente classificata come "FIFO": First In First Out, il primo elemento che entra è anche il primo ad uscire.

In pratica la lista viene realizzata come un insieme di blocchi concatenati tra loro.

Nodo

L'elemento base viene chiamato Nodo e contiene una informazione (ad esempio un numero) e un modo per raggiungere l'elemento successivo.

Quando dichiariamo la variabile Button b in pratica stiamo dicendo che b indicherà una zona di memoria in cui è descritto un oggetto di tipo Button.

Proviamo a vedere come possiamo dichiarare il Nodo nel caso di una lista che memorizzi delle stringhe:

public class Nodo {
    String dato;
    Nodo successivo;
}

Parafrasi: un Node è formato da un dato (in questo caso una stringa) e un modo per raggiungere l'elemento successivo. L'oggetto non contiene un altro nodo al suo interno perché, come dicevamo prima, successivo è soltanto un modo per indicare in memoria dove si trova un altro Nodo

Lista

Avendo il singolo blocchetto implementiamo la lista cercando di fare il meno possibile! Sarebbe a dire che implementeremo soltanto le funzionalità strettamente necessarie.

La lista di per se deve mantenere un riferimento al primo elemento della lista (che è tradizionalmente chiamato testa), e poi due metodi per inserire (accoda) ed estrarre (estrai) elementi dalla lista. Non importa un granche da che parte (inizio o fine) si inseriscono gli elementi: l'importante è che vengano estratti dalla parte opposta.

La nostra implementazione inserisce in coda e estrae in testa, per esercizio è possibile fare l'inverso.

public class Lista {
  private Nodo testa;
    
  public Lista(){
    testa = null;
  }
    
  public void accoda(String nuovoDato){
    Nodo nuovoElemento;
        
    // creo il nuovo elemento della lista
    nuovoElemento = new Nodo();
    nuovoElemento.dato = nuovoDato;
    nuovoElemento.successivo = null;
    // controllo se in lista c'è già qualcosa
    if(testa == null){
      // in lista non c'è nulla quindi la lista è costituita 
      // solamente dal nuovo elemento
      testa = nuovoElemento;
    }else{
      // esistono già elementi
      Nodo temp;  // lo uso per scorrere la lista
      temp = testa;
      // continua finché non sei arrivato in fondo
      while(temp.successivo!=null){
        // vai avanti
        temp = temp.successivo;
      }
      temp.successivo = nuovoElemento;
    }
  }
    
  public String estrai(){
    Nodo temp;
        
    // il primo elemento della lista
    temp = testa;   
    // visto che il primo elemento lo tolgo
    // la testa della lista deve puntare al successivo
    if(testa!=null) {
      testa = testa.successivo;
    }
    return temp.dato;
  }

}