public class LLOrdenada
{
  static Celula [] Lista;
  static int       Comeco;
  static int       Livre;
  static final int max = 100;
  static final int nil = -1;
  

  public LLOrdenada()
    {
      Lista  = new Celula[max];
      for (int i = 0; i < max; i++)
	Lista[i] = new Celula();      
      Comeco = nil;
      for (int i = 0; i < max - 1; i++) 
	Lista[i].mudaProx(i+1);
      Livre = 0;
      Lista[max-1].mudaProx(nil);
    }
  public int Procura(int x)
    {
      int atual = Comeco;
      while (atual != nil && x > Lista[atual].leInfo()) 
	atual = Lista[atual].leProx();
      if( atual == nil || x > Lista[atual].leInfo())
	return(nil);
      return(atual);
    }
  public static void Imprime()
    {
      if( Comeco == nil) System.out.println("Lista vazia");
      else{
	int no = Comeco;
	while(no != nil) {
	  System.out.print(" "+Lista[no].leInfo());
	  no = Lista[no].leProx();
	}
	System.out.println();
      }
    }
  public static int ExtraiNo()
    {
      int no = Livre;
      if ( Livre == nil) 
	System.out.println("Não há espaço");
      else
	Livre  = Lista[Livre].leProx();
      return(no);
    }
  public static void DevolveNo (int no)
    {
      Lista[no].mudaProx(Livre);
      Livre = no;
    }
  public static void Insere (int x)
    {
      int anterior = nil;
      int atual = Comeco;
      int novo  = ExtraiNo();
      boolean inseriu = false;
      
      Lista[novo].mudaInfo(x);
      while( atual != nil && !inseriu)
	if (x > Lista[atual].leInfo()){
	  anterior = atual;
	  atual    = Lista[atual].leProx();
	}
	else if( x == Lista[atual].leInfo()){
	  System.out.println(x+" já está na lista");
	  return;
	}
	else{  // achei o lugar para inserir o nó novo
	  if( anterior == nil) {
	    // muda o começo 
	    Lista[novo].mudaProx(Comeco);
	    Comeco = novo;
	  }
	  else{
	    Lista[anterior].mudaProx(novo);
	    Lista[novo].mudaProx(atual);
	  }
	  inseriu = true;
	}
      if (! inseriu) {
	// insere no final da lista
	if (anterior != nil){ // lista não está vazia
	  Lista[anterior].mudaProx(novo);
	  Lista[novo].mudaProx(nil);
	}
	else{
	  Lista[novo].mudaProx (nil);
	  Comeco = novo;
	}
      }
    }
  static void Remove (int x)
    {
      int anterior = nil;
      int atual = Comeco;
      boolean achou = false;
      

      while (atual != nil && ! achou) 
	if( x > Lista[atual].leInfo()){
	  anterior = atual;
	  atual = Lista[atual].leProx();
	}
        else if (x < Lista[atual].leInfo()){
	  System.out.println(" Elemento não está na lista");
	  return;
	}
	else{
	  // achei o elemento a ser removido
	  if( anterior == nil)
	    // primeiro da lista
	    Comeco = Lista[atual].leProx();
	  else
	    Lista[anterior].mudaProx(Lista[atual].leProx());
	  DevolveNo(atual);
	  achou = true;
	}
      if(!achou)  
	System.out.println(" Elemento não está na lista");
    }
}