Realizzazione di code con liste concatenate
In questa realizzazione di Coda<E>, gli elementi sono memorizzati in una lista concatenata, cioè una sequenza di nodi ognuno dei quali contiene un elemento della lista (un oggetto di tipo E) e un puntatore al prossimo nodo.

Una coda contenente gli elementi <A1, A2, ..., An> viene rappresentata con una lista concatenata, dove

  • il primo elemento è puntato dalla variabile front e contiene l'elemento inserito meno recentemente
  • l'ultimo elemento è puntato dalla variabile back contiene l'elemento inserito più recentemente

      •  
       
       

Scelte progettuali
Per la classe CodaList<E> abbiamo fatto le seguenti scelte:
  • Gli elementi della coda vengono memorizzati in una lista concatenata: gli elementi vengono inseriti in fondo ed estratti in testa.

    •  
  • Una coda ha due variabili d'istanza, chiamate front e back , di tipo ListNode<E>. Concettualmente, front è un puntatore alla testa della lista, back è un puntatore alla coda della lista.

    •  
  • Una coda è vuota se e solo se front vale null.

    •  
  • Quando si inserisce un elemento nella coda lo si mette in un nuovo nodo, che diventa l'ultimo della lista.

    •  
  • Quando si toglie un elemento, si cambia front in modo da puntare all'elemento successivo.

    •  
  • Tutte le operazioni hanno complessità costante nel caso pessimo, O(1). 

La classe CodaList<E>
Il codice completo della classe CodaList<E> è mostrato sotto. La realizzazione si appoggia ovviamente sulla classe ListNode<E>.
  
import java.util.*;

/**
 * Classe CodaList<E>:
 *
 * Realizzazione della coda mediante Liste Concatenate
 */
public class CodaList<E> implements Coda<E> {
    ListNode<E> front, back;

    /**
     * Costruttore della coda.
     */
    public CodaList() {
        front = back = null;
    }

    /**
     * Verifica che la coda sia logicamente vuota.
     * @return  <code>true</code> se la coda &egrave; vuota;
     *          <code>false</code> altrimenti.
     */
    public boolean isEmpty() {
        return front == null;
    }

    /**
     *  Svuota la Coda. 
     */
    public void clear() {
        front = back = null;
    }

    /**
     * Restituisce l'oggetto in testa alla coda senza estrarlo.
     * @return   l'oggetto in teata.
     * @exception NoSuchElementException con coda vuota.
     */
    public E  peek() {
        if (isEmpty()) throw new NoSuchElementException();
        return front.element;
    }

    /**
     * Inserisce un oggetto in fondo alla coda.
     * @param x  l'oggetto da inserire.
     * @return   l'oggetto inserito.
     */
    public E enqueue(E x) {
        if(isEmpty()) front = back = new ListNode<E>(x, null);
        else {
          back.next = new ListNode<E>(x, null);
          back=back.next;
        }
        return x;
    }

    /**
     * Rimuove e restituisce l'oggetto in testa alla coda.
     * @return   l'oggetto in testa.
     * @exception NoSuchElementException con Coda vuota.
     */
    public E dequeue() {
        if (isEmpty() throw new NoSuchElementException();
        E x = front.element;
        front = front.next;
        if(isEmpty())back=null;
        return x;
    }
    
    /**
     * Conversione in array
     * @return un array di Object con gli elementi della struttura
     */
    public Object[] toArray(){
                                // da realizzare
    }
}
 

Esercizi
1)Si consideri la seguente interfaccia
  
public interface RevCoda<E> extends Coda<E> {

    /**
     * Rovescia il contenuto della coda
     */
    void reverse();
}

Si scriva la classe RevCodaList che estende CodaList e implementa l'interfaccia RevCoda in modo tale che il metodo reverse() rovesci la coda su cui viene chiamato.

SOLUZIONE