public class ListaDinamica {
	
	private Celula primeira;
	private Celula ultima;
	private int total;         // total de elementos
	
	// construtor sem argumentos
	public ListaDinamica(){
		primeira = null;
		ultima = null;
		total = 0;
	}
	
	// adiciona no final da lista
	public boolean adiciona(Object elemento){
		Celula nova = new Celula(elemento);
		
		// é 1o elemento a ser adicionado na lista
		if (total == 0) {
			primeira = nova;
			ultima = nova;
		// já tem pelo menos um elemento na lista
		} else {
			ultima.setProxima(nova);
			nova.setAnterior(ultima);
			ultima = nova;
		}
		
		total++;
		return true;
	}
	
	// adiciona em qualquer posicao existente
	public boolean adiciona(int posicao, Object elemento){
		
		Celula nova = new Celula(elemento);
		Celula celula = obtemCelula(posicao);
		
		if (celula == null)  // posição inválida
			return false;
			
		// inicio da lista (antes do primeiro elemento)
		if (posicao == 0) {
			nova.setProxima(primeira);
			primeira.setAnterior(nova);
			
		// outra posição (antes de celula)
		} else if (posicao == total - 1) {
			Celula anterior = celula.getAnterior();
			anterior.setProxima(nova);
			nova.setAnterior(anterior);
			nova.setProxima(celula);
			celula.setAnterior(nova);
		}
		
		total++;
		return true;
	}
	
	
	
	// retorna o elemento, dada a posição
	public Object obtem(int posicao){
		
		Celula celula = obtemCelula(posicao);
		if (celula != null)
			return celula.getElemento();
		else
			return null;
	}
	
	
	// retorna uma celula, dada a posição
	private Celula obtemCelula(int posicao){
		
		Celula celula = primeira;
		
		if (posicaoNaoExiste(posicao))
			return null;
		
		for(int i=0; i<=posicao; i++) {
			if (i == posicao)
				return celula;
			else
				celula = celula.getProxima();
			
		}
		
		return null;
	}
	
	
	// retorna o índice do elemento ou -1 se inexistente
	public int indice(Object elemento){
		Celula celula = primeira;
		int i = 0;

		while (celula != null) {
			
			if (celula.getElemento().equals(elemento)){
				return i;
			}
		
			celula = celula.getProxima();
			i++;
			
		}
		
		return -1;
	}
	
	
	// remove o elemento, dada a posição
	public boolean remove(int posicao){
		
		Celula celula, proxima, anterior;
		
		if (posicaoNaoExiste(posicao))
			return false;
		
		// primeiro elemento
		if (posicao == 0){
			primeira = primeira.getProxima();
			if (primeira == null)
				ultima = null;
			else
				primeira.setAnterior(null);
			
		// último elemento
		} else if(posicao == total - 1){
			ultima = ultima.getAnterior();
			ultima.setProxima(null);
			
		// posição intermediária (tem um mínimo de 3 elementos)
		} else {
			celula = obtemCelula(posicao);
			anterior = celula.getAnterior();
			proxima = celula.getProxima();
			anterior.setProxima(proxima);
			proxima.setAnterior(anterior);
		}
		
		total--;
		
		return true;
	}
	
	
	// retorna true se o elemento exitir na lista
	public boolean contem(Object elemento){
		
		Celula celula = primeira;
		while (celula != null){
			if (celula.getElemento().equals(elemento))
				return true;
				
			celula = celula.getProxima();
		}
		
		return false;
	}
	
	
	// converte a lista dinâmica em array
	public Object[] toArray(){
			Object[] array = new Object[total];
			Celula celula = primeira;
			for(int i=0; i<total; i++){
				array[i] = celula.getElemento();
				celula = celula.getProxima();
			}
			return array;
	}

	public void imprime(){
		for(Object objeto : toArray()){
			System.out.println(objeto);
		}
	}
	
	
	private boolean posicaoNaoExiste(int posicao){
		return (posicao < 0 || posicao >= total) ? true : false; 
	}
	
	
	public boolean remove(Object elemento){
		return  remove(indice(elemento));
	}
	
	
	public int tamanho(){
		return total;
	}
}