implementazioneListe

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 a vedere...

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

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 code

In pratica la coda viene realizzata come un insieme di blocchi concatenati tra loro chiamati nodi.

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 coda che memorizzi delle stringhe:

public class Nodo {
    String dato;
    Nodo successivo;
}

Parafrasi: un Nodo è 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

Coda

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

La coda di per se deve mantenere un riferimento al suo primo elemento (che è tradizionalmente chiamato testa), e poi due metodi per inserire (accoda) ed estrarre (estrai) elementi dalla coda stessa. 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 Coda {
  private Nodo testa;
    
  public Coda(){
    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;
  }

}

Implementazione della pila

La pila non è poi molto diversa dalla coda, in realtà è molto semplicemente implementabile come una coda in cui si inserisce e si estrae dalla stessa parte. Sebbene teoricamente sia possibile lavorare sia in coda che in testa l'implementazione più semplice (quella riportata qui) inserisce/estrae dalla testa della pila.

Per evitare confusione chiamiamo ElementoPila quello che prima abbiamo chiamato Nodo, ma come è facile vedere sono praticamente uguali.

ElementoPila

public class ElementoPila {
    public String dato;
    public ElementoPila precedente;
}

Pila

package lezioni.strutturedati;

/****************************************************************************
 * Una pila con le operazioni fondamentali
 ***************************************************************************/
public class Pila {
    private ElementoPila testa;
    
    public Pila(){
        testa = null;
    }
    
    /************************************************************************
     * @param nuovoDato l'elemento da inserire sulla pila
     ***********************************************************************/
    public void push(String nuovoDato){
        ElementoPila nuovoElemento;
        
        // creo il nuovo elemento della pila
        nuovoElemento = new ElementoPila();
        nuovoElemento.dato = nuovoDato;
        nuovoElemento.precedente = 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
            nuovoElemento.precedente = testa;
            testa = nuovoElemento;
        }
    }
    
    /************************************************************************
     * @return il primo elemento della pila (e lo toglie dalla pila)
     ***********************************************************************/
    public String pop(){
        ElementoPila temp;
        
        // il primo elemento della lista
        temp = testa;   
        // scorri avanti
        testa = testa.precedente;
        return temp.dato;
    }
    
    /************************************************************************
     * @return true se la lista è vuota
     ***********************************************************************/
    public boolean vuota(){
        return testa == null;
    }
}