public class Lista {
  
 //membro privato: puntatore al Nodo "corrente"
  private Nodo pointerNode;
  /* flag per effettuare il rewind() automatico al primo
     utilizzo di getNextElem()
  */
  boolean first = true;
  
  private Nodo head;
    
  //costruttore
  public Lista() {
    head = null;
  }
  
  //metodi pubblici per la gestione della lista
  public void InsertHead(int val) {
    /* Inserimento in testa:
       Creo un nuovo nodo che sarà la nuova testa,
       e lo collego al nodo che ERA la vecchia testa. */
    head = new Nodo(val, head);
  }
  
  //Controlla che la lista contenga almeno un nodo
  public boolean IsEmpty() {return (head == null);}
  
  public void InsertTail(int val) {
    /* Inserimento in coda:
       prende un puntatore ai nodi (aux) e lo fa
       scorrere per tutta la lista (notare che il ciclo si ferma
       al nodo precedente xkè il controllo è su aux.getNext(), ma
       FUORI dal ciclo la variabile aux punta all'oggetto di coda),
       poi crea un nuovo nodo come successivo all'ultimo (aux.setNext)*/
    if (IsEmpty())
      InsertHead(val);  //se lista vuota aggiunge in testa
    else {
      Nodo aux = head;
      for (; aux.getNext() != null; aux = aux.getNext());
      aux.setNext(new Nodo(val));
    }
  }
  
  public void InsertOrdered(int val) {
    /* Inserimento ordinato:
       Se la lista è vuota inserisce un nodo nella head;
       se il primo elemento della lista è più grande
       di quello da inserire, inserisci nuovo elemento in testa;
       altrimenti scorri i nodi della lista finchè trovi quello
       che contiene il valore >= a quello da inserire. Fuori
    */
    if (IsEmpty())
      InsertHead(val);  //se lista vuota aggiunge in testa
    else
      if (head.getInfo() > val)
        head = new Nodo(val, head);
      else {
        Nodo aux = head;
        for  (; (aux.getNext() != null) &&
              (aux.getNext().getInfo() < val);
              aux = aux.getNext());
        aux.setNext(new Nodo(val, aux.getNext()));
      }
  }
  
  
  public Nodo SearchOrd(int key) {
    /* Ricerca ordinata:
       Il ciclo scorre i nodi sul puntatore aux mentre il valore presente
       nei nodi è minore di quello cercato (e finchè ci sono nodi).
       All'uscita dal ciclo possono verificarsi due condizioni:
       il valore nel nodo corrente è >= a quello cercato, oppure
       si è giunti in coda; l'if successivo al ciclo farà restituire
       al metodo il nodo cercato solo se il valore in esso contenuto    
       corrisponde al valore cercato. */
    Nodo aux = head;
    for (; aux != null && aux.getInfo() < key; aux = aux.getNext());
    if (aux != null && aux.getInfo() == key)
      return aux;
    return null;
  }
  
  public Nodo Search(int key) {
    Nodo aux = head;
    for (; aux != null && aux.getInfo() != key; aux = aux.getNext());
    if (aux != null && aux.getInfo() == key)
      return aux;
    return null;
  }
 
  public int DeleteHead() {
    /* Cancellazione in testa:
       aux punta al nodo di testa
       (per far restituire al metodo il valore del nodo eliminato),
       poi head diventa il nodo successivo alla testa [head=head.getNext()]
    */
    if (IsEmpty())
      throw new EmptyListException();
    else {
      Nodo aux = head;
      head = head.getNext();
      return aux.getInfo();
    }
  }
  
  public int DeleteTail() {
    /* Cancellazione in coda (Tail):
       Si fa scorrere la lista dei nodi come al solito (con aux)
       ma si tiene anche il riferimento al nodo precedente,
       in modo che quando si esce dal ciclo si verifica che:
       aux = ultimo nodo della lista (che deve essere eliminato)
       prev = penultimo nodo (da far diventare ultimo)
       A questo punto se prev = null vuol dire che esisteva solo
       UN NODO (cioè head), quindi è sufficiente impostare
       head = null, adesso la lista sarà vuota!!
       Altrimenti si imposta il setNext() del penultimo nodo
       a null e l'ultimo rimarrà "sganciato" dalla lista
       (verrà eliminato dalla Garbage collection di Java)
       Il metodo restituisce il valore info del nodo eliminato.*/
    if (IsEmpty())
      throw new EmptyListException();
    else {
      Nodo aux = head;
      Nodo prev = null;
      for (; aux.getNext() != null;
             prev = aux, aux = aux.getNext());
      if (prev == null)
        head = null;
      else
        prev.setNext(null);
      return aux.getInfo();
    }
  }
  
  /* Cancellazione di un nodo contenente un valore:
     Scorrimento della lista dei nodi con il riferimento
     al nodo precedente (come DeleteTail) ma si esce dal ciclo
     quando si trova il nodo contenente il valore cercato, oppure
     se si è giunti al termine della lista.
     A questo punto se aux != null (cioè non siamo a fine lista)
     si controlla il nodo precedente: se è null vuol dire che il
     nodo trovato è propio il primo (head), quindi si fa puntare head
     a quello successivo [head = head.getNext()]. Altrimenti si imposta
     il prossimo collegamento del nodo precedente a quello successivo al
     nodo trovato, questo "sgancerà" propio il nodo trovato dalla lista dei nodi.
     */
  public Nodo DeleteKey(int key) {
    if (IsEmpty())
      throw new EmptyListException();
    else {
      Nodo aux = head;
      Nodo prev = null;
      for (; aux != null && aux.getInfo() != key;
             prev = aux, aux = aux.getNext());
      if (aux != null)
        if (prev == null)
          head = head.getNext();
        else
          prev.setNext(aux.getNext());
      return aux;
    }
  }
  
  //Metodi aggiunti alla superclasse Lista  
  public void rewind() {
    pointerNode = head;
  }
  
  public int getNextElem() {
    if (IsEmpty())
      throw new EmptyListException();
    else {
      //se è la prima chiamata esegui il rewind()
      if (first) {
        rewind();
        first = false;
      }
      if (pointerNode != null) {
        int info = pointerNode.getInfo();
        pointerNode = pointerNode.getNext();
        return info;
      }
      else
        throw new BottomOfListException();
    }
  }
 }
  
//Classe Nodo
 class Nodo {
  private int info;
  private Nodo next;
  //costruttori
  public Nodo(int val) {this(val, null);}
  public Nodo(int val, Nodo n) {
    info = val;
    next = n;
  }
  //metodi pubblici
  public void setInfo(int val) {info = val;}
  public int getInfo() {return info;}
  
  public void setNext(Nodo n) {next = n;}
  public Nodo getNext() {return next;}
  
}

//Classe di eccezione personalizzata per la lista vuota.
class EmptyListException extends RuntimeException {
  public EmptyListException() {
    super("Lista vuota!");
  }
  
  public EmptyListException(String msg) {
    super(msg);
  }

}

//Classe di eccezione personalizzata per il fine lista.
class BottomOfListException extends RuntimeException {
  public BottomOfListException() {
    super("Fine della lista");
  }
  
  public BottomOfListException(String msg) {
    super(msg);
  }

}