public class UmaListaCircular {
  /* Nesta implementacao de uma lista circular a variavel de referencia 
   * inicio contem o endereco (aponta para) a celula mais a direita da lista.
   * Esta implementacao *nao* usa cabeca-de-lista.
   */ 
   
  private UmaCelula inicio; 

  // O contrutor da classe.
  public UmaListaCircular () {
    inicio = null; // a lista inicialmente esta vazia
  }

  public boolean listaCircularVazia () {
    return inicio == null;
  }

  public void insereEsqListaCircular (UmaInfo info) throws MinhaExcecao {
    UmaCelula ptr;

    try {
      // ptr aponta para a nova celula que contem info
      ptr = new UmaCelula (info, null); 
    }
    catch (java.lang.OutOfMemoryError e) {
      throw new MinhaExcecao("Overflow: acabou a memoria");
    }
    
    if (listaCircularVazia()) {
      inicio = ptr ;
      ptr.mudaProx (inicio);
    }
    else {
      ptr.mudaProx (inicio.retorneProx());
      inicio.mudaProx (ptr);
    }
  }

  public void insereDirListaCircular (UmaInfo info) throws MinhaExcecao {
    insereEsqListaCircular (info);
    inicio = inicio.retorneProx (); 
  }

  public void removeEsqListaCircular () throws MinhaExcecao {
    UmaCelula ptr;

    if (listaCircularVazia()) // (inicio == null) 
      throw new MinhaExcecao("Underflow: removeEsqListaCircular");
    else { 
      ptr = inicio.retorneProx();
      if (inicio == ptr) // se a lista tem apenas uma celula?
	inicio = null; // entao a lista esta vazia agora
      else
	inicio.mudaProx (ptr.retorneProx());
    }
  }

  // Note que, com esta estrutura de dados, a operacao remove a direita 
  // e' ineficiente; tem  complexidade de tempo O(n), onde n e' o numero 
  // de celulas na lista.
  public void removeDirListaCircular () throws MinhaExcecao {
    UmaCelula ptr;

    if (listaCircularVazia()) // (inicio == null) 
      throw new MinhaExcecao("Underflow: removeDirListaCircular");
    else { 
      ptr = inicio.retorneProx();
      if (inicio == ptr) // se a lista tem apenas uma celula?
	inicio = null; // entao a lista esta vazia agora
      else {
	while (ptr.retorneProx() != inicio) 
	  ptr.mudaProx (ptr.retorneProx()) ;
	ptr.mudaProx (inicio.retorneProx());
        inicio = ptr;
      }
    }
  }
  
  public UmaInfo retorneEsqListaCircular () throws MinhaExcecao {
    if (listaCircularVazia())  
      throw new MinhaExcecao("Underflow: retorneEsqListaCircular");
    else
      return inicio.retorneProx().retorneInfo();
  }

  public UmaInfo retorneDirListaCircular () throws MinhaExcecao {
    if (listaCircularVazia())  
      throw new MinhaExcecao("Underflow: retorneDirListaCircular");
    else
      return inicio.retorneInfo();
  }
  
}