class NodoLista {
  public String info;
  public NodoLista next;
}


public class Liste {

  public static void stampa(NodoLista p) {
    while(p!=null) {
      System.out.print(p.info + " ");
      p = p.next;
    }
    System.out.println();
  }
  
  public static int lunghezza(NodoLista p) {
    int cont = 0;
    while(p!=null) {
      cont++;
      p = p.next;
    }
    return cont;
  }

  public static boolean cerca(NodoLista p, String s) {
    while (p!=null) {      
      if (p.info.equals(s)) return true;
      p = p.next;
    }
    return false;
  }

  //inserimento elemento in testa
  public static NodoLista inTesta(NodoLista p, String s) {
    NodoLista q = new NodoLista();
    q.info = s;
    q.next = p;
    p = q;
    return p;
  }

  //eliminazione elemento in testa
  public static NodoLista outTesta(NodoLista p) {
    p = p.next;
    return p;
  }

  /*
  //inserimento nuovo elemento prima di un dato elemento
  public static NodoLista inserisciPrima(NodoLista p, String nuova, String cercata){
    if (p == null) return p;
    
    if (p.info.equals(cercata)) {
      NodoLista q = new NodoLista();  //inserimento nuovo elemento
      q.info = nuova;                 //in prima posizione
      q.next = p;
      p = q;
      return p;
    }

    NodoLista pp = p;
    while (pp.next != null) {
      if (pp.next.info.equals(cercata)) {
        NodoLista q = new NodoLista(); //inserimento nuovo elemento
        q.info = nuova;                //in posizioni interne
        q.next = pp.next;
        pp.next = q;
        break;
      }
      pp = pp.next;
    }
    return p;
  }    
  */

  //inserimento nuovo elemento prima di un dato elemento
  //con nodo generatore
  public static NodoLista inserisciPrima(NodoLista p, String nuova, String cercata){
    NodoLista pp = new NodoLista(); // creazione nodo generatore
    pp.next = p;
    p = pp;
    
    while (pp.next != null) {       //ora ogni nodo ha un predecessore
      if (pp.next.info.equals(cercata)) {
        NodoLista q = new NodoLista();    //inserimento nuovo elemento
        q.info = nuova;                   //in posizione interna
        q.next = pp.next;
        pp.next = q;
        break;
      }
      pp = pp.next;
    }

    p = p.next;                     //eliminazione del nodo generatore
    return p;
  }    

  /*
  //eliminazione elemento prima di un dato elemento
  public static NodoLista elimina(NodoLista p, String cercata){
    if (p == null) return p;
    
    if (p.info.equals(cercata)) {
      p = p.next;                   //eliminazione elemento cercato
      return p;                     //in prima posizione
    }

    NodoLista pp = p;
    while (pp.next != null) {
      if (pp.next.info.equals(cercata)) {
        pp.next = pp.next.next;     //eliminazione elemento cercato
        break;                      //in posizione interna
      }
      pp = pp.next;
    }
    return p;
  }    
  */

  //eliminazione elemento prima di un dato elemento
  //con nodo generatore
  public static NodoLista elimina(NodoLista p, String cercata){
    NodoLista pp = new NodoLista(); // creazione nodo generatore
    pp.next = p;
    p = pp;
    
    while (pp.next != null) {       //ora ogni nodo ha un predecessore
      if (pp.next.info.equals(cercata)) {
        pp.next = pp.next.next;     // eliminazione elemento cercato
        break;                      //in posizione interna
      }
      pp = pp.next;
    }

    p = p.next;                     //eliminazione del nodo generatore
    return p;
  }
       


  //inserimento nuovo elemento dopo di un dato elemento
  public static NodoLista inserisciDopo(NodoLista p, String nuova, 
                                        String cercata){
    if (p == null) return p;

    NodoLista pp = p;
    while (pp != null) {
      if (pp.info.equals(cercata)) {
        NodoLista q = new NodoLista(); 
        q.info = nuova;
        q.next = pp.next;
        pp.next = q;
        break;
      }
      pp = pp.next;
    }
    return p;
  }    


  public static NodoLista copia(NodoLista p) {
    if (p == null) return null;
    
    NodoLista cp = new NodoLista();  //nota cp.next == null
    NodoLista cpp = cp;
    cpp.info = p.info;
    while (p.next != null) {
      cpp.next = new NodoLista();    //nota cpp.next.next == null
      cpp.next.info = p.next.info;
      cpp = cpp.next;
      p = p.next;  
    }
    return cp;
  }

  /* oppure usando il nodo generatore
  public static NodoLista copia(NodoLista p) {
    NodoLista cp = new NodoLista();  // nodo generatore
    NodoLista cpp = cp;
    while (p != null) {
      cpp.next = new NodoLista();    //nota cpp.next.next == null
      cpp.next.info = p.info;
      cpp = cpp.next;
      p = p.next;  
    }
    return cp.next;  // elimino nodo generatore
  }
  */
      

  public static NodoLista inverti(NodoLista p){
    // p riferimento alla lista ancora da invertire
    // ris riferimento alla lista invertita
    NodoLista ris = null;
    while (p != null) {
      NodoLista q = p.next;
      p.next = ris;
      ris = p;
      p = q;
    }
    return ris;
  }



  /*
  //inserimento nuovo elemento in ultima posizione
  public static NodoLista inserisciCoda(NodoLista p, String s){
    if (p == null) {
      p = new NodoLista();
      p.info = s;
      return p;
    } 
    else {  
      NodoLista pp = p;
      while (pp.next != null) 
        pp = pp.next;
      pp.next = new NodoLista();
      pp.next.info = s;
      return p;
    }    
  }
  */

  //inserimento nuovo elemento in ultima posizione
  public static NodoLista inserisciCoda(NodoLista p, String s){
    NodoLista pp = new NodoLista();  // crea nodo generatore
    pp.next = p;
    p = pp;
    while (pp.next != null) 
      pp = pp.next;
    pp.next = new NodoLista();
    pp.next.info = s;
    return p.next; // elimina nodo generatore
  }


  public static NodoLista crea3NodiABC() {
    NodoLista a = new NodoLista();
    NodoLista b = new NodoLista();
    NodoLista c = new NodoLista();
    a.info = "A";
    a.next = b;
    b.info = "B";
    b.next = c;
    c.info = "C";
    c.next = null;
    return a;
  }



  public static void main(String[] args){
    NodoLista a = crea3NodiABC();
    boolean b = cerca(a,"C"); 
    System.out.println(b);
    System.out.println(lunghezza(a));
    stampa(a);
    
    a = inTesta(a,"X");
    stampa(a);
    a = outTesta(a);
    stampa(a);
    
    a = inserisciPrima(a,"X","C");
    stampa(a);
    a = inserisciPrima(a,"X","A");
    stampa(a);
    
    a = elimina(a,"X");
    stampa(a);
    a = elimina(a,"X");
    stampa(a);
    
    a = inserisciDopo(a,"X", "B");
    stampa(a);
    a = inserisciDopo(a,"X", "C");
    stampa(a);

    a = elimina(a,"X");
    stampa(a);
    a = elimina(a,"X");
    stampa(a);
    
    NodoLista ca = copia(a);
    stampa(ca);
    ca = inserisciPrima(ca,"X","C");
    stampa(ca);
    stampa(a);
    ca = inverti(ca);
    stampa(ca);

    ca = inserisciCoda(ca, "Z");
    stampa(ca);
    
  }

}