Listas (parte 1)

    Olá, galera!

    Nesta aula eu falo sobre listas simples e encadeadas, suas operações e o seu uso. Esta é a primeira de três aulas que exploram este assunto. Abraço!




Classe ListaSimples

package br.edu.ifms.aula;

/**
 * Encapsula uma lista simples de inteiros.
 * 
 * @author Prof.º Sidney
 * 
 */
public class ListaSimples {

	private int tamanho = 0;

	private Integer[] lista;

	/**
	 * Construtor da classe ListaSimples. Instancia a lista com o tamanho
	 * definido.
	 */
	public ListaSimples(int tamanho) {
		this.tamanho = tamanho;
		lista = new Integer[this.tamanho];
	}

	/**
	 * Adiciona um novo item na lista no índice desejado. Se já houver um item
	 * neste índice, ele será sobreposto.
	 * 
	 * @param novoItem
	 *            Item a ser adicionado.
	 * @param indiceDoItem
	 *            Índice do novo item.
	 * @return <b>true</b> caso o item tenha sido adicionado com sucesso;
	 *         <b>false</b> c.c.
	 */
	public boolean adicionarItem(Integer novoItem, int indiceDoItem) {
		if (indiceDoItem >= 0 && indiceDoItem < tamanho) {
			lista[indiceDoItem] = novoItem;
			return true;
		}
		return false;
	}

	/**
	 * Remove um item da lista.
	 * 
	 * @param indiceDoItem
	 *            Índice do item a ser removido.
	 * @return O valor do item. Retorna <b>null</b> caso a posição indicada
	 *         esteja vazia ou se o índice informado sejá inválido.
	 */
	public Integer removerItem(Integer indiceDoItem) {
		if (indiceDoItem >= 0 && indiceDoItem < tamanho
				&& lista[indiceDoItem] != null) {
			Integer itemRemovido = lista[indiceDoItem];
			lista[indiceDoItem] = null;
			return itemRemovido;
		}
		return null;
	}

	/**
	 * Retorna o item da lista situado no índice desejado.
	 * 
	 * @param indiceDoItem
	 *            Índice do item desejado.
	 * @return O item desejado. Retorna <b>null</b> caso a posição indicada
	 *         esteja vazia ou se o índice informado sejá inválido.
	 */
	public Integer pegarItem(Integer indiceDoItem) {
		if (indiceDoItem >= 0 && indiceDoItem < tamanho) {
			return lista[indiceDoItem];
		}
		return null;
	}

	public int tamanhoDaLista() {
		return tamanho;
	}

}

Classe No

package br.edu.ifms.aula;

/**
 * Nó da lista que armazena um valor inteiro.
 * 
 * @author Prof.º Sidney
 * 
 */
public class No {

	/**
	 * O valor do item armazenado.
	 */
	private Integer item;

	/**
	 * Ponteiro para o próximo item da lista.
	 */
	private No proximoItem;

	/**
	 * Construtor da classe No.
	 */
	public No() {
		proximoItem = null;
	}

	/**
	 * Getter para o atributo <b>item</b>.
	 * 
	 * @return O valor do atributo <b>item</b>.
	 */
	public Integer getItem() {
		return item;
	}

	/**
	 * Setter para o atributo <b>item</b>.
	 * 
	 * @param item
	 *            O novo valor para o atributo <b>item</b>.
	 */
	public void setItem(Integer item) {
		this.item = item;
	}

	/**
	 * Getter para o atributo <b>proximoItem</b>.
	 * 
	 * @return O valor do atributo <b>proximoItem</b>.
	 */
	public No getProximoItem() {
		return proximoItem;
	}

	/**
	 * Setter para o atributo <b>proximoItem</b>.
	 * 
	 * @param proximoItem
	 *            O novo valor para o atributo <b>proximoItem</b>.
	 */
	public void setProximoItem(No proximoItem) {
		this.proximoItem = proximoItem;
	}
}

Classe ListaEncadeada

package br.edu.ifms.aula;

/**
 * Encapsula uma lista encadeada de inteiros.
 * 
 * @author Prof.º Sidney
 * 
 */
public class ListaEncadeada {

	/**
	 * Tamanho da lista.
	 */
	private int tamanho;

	/**
	 * Primeiro item da lista.
	 */
	private No primeiroItem;

	/**
	 * Último item da lista.
	 */
	private No ultimoItem;

	/**
	 * Construtor para a classe {@link ListaEncadeada}. Inicializa os atributos
	 * da classe.
	 */
	public ListaEncadeada() {
		primeiroItem = null;
		ultimoItem = null;
		tamanho = 0;
	}

	/**
	 * Retorna o primeiro item da lista.
	 * 
	 * @return O primeiro item da lista.
	 */
	public No pegaPrimeiroItem() {
		return primeiroItem;
	}

	/**
	 * Retorna o último item da lista.
	 * 
	 * @return O último item da lista.
	 */
	public No pegarUltimoItem() {
		return ultimoItem;
	}

	/**
	 * Retorna o item situado na posição desejada.
	 * 
	 * @param posicao
	 *            Posição do item a ser recuperado.
	 * @return O item situado na posição desejada.
	 */
	public No pegarItem(int posicao) {
		if (tamanho > 0 && posicao >= 1 && posicao <= tamanho) {
			No item = primeiroItem;
			int contador = 1;
			while (posicao < contador) {
				item = item.getProximoItem();
				contador++;
			}
			return item;
		}
		return null;
	}

	/**
	 * Remove o elemento situado na posição desejada, caso esta posição exista
	 * na lista.
	 * 
	 * @param posicao
	 *            Posição do item a ser removido.
	 * @return <b>true</b> caso o item existia na lista e assim foi removido com
	 *         sucesso; <b>false</b> c.c.
	 */
	public boolean remover(int posicao) {
		if (tamanho > 0 && posicao >= 1 && posicao <= tamanho) {
			No item = primeiroItem;
			No anterior = null;
			int contador = 1;
			while (contador < posicao) {
				anterior = item;
				item = item.getProximoItem();
				contador++;
			}
			No proximo = item.getProximoItem();
			if (anterior != null) {
				anterior.setProximoItem(proximo);
			} else {
				primeiroItem = proximo;
			}
			tamanho--;
			if (tamanho <= 1) {
				primeiroItem = proximo;
				ultimoItem = primeiroItem;
			}
			return true;
		}
		return false;
	}

	/**
	 * Adiciona um novo item no início da lista.
	 * 
	 * @param novoItem
	 *            Novo item a ser adicionado.
	 */
	public void adicionarNoInicio(Integer novoItem) {
		if (tamanho == 0) {
			primeiroItem = new No();
			primeiroItem.setItem(novoItem);
			ultimoItem = primeiroItem;
		} else {
			No antigoPrimeiroItem = primeiroItem;
			primeiroItem = new No();
			primeiroItem.setItem(novoItem);
			primeiroItem.setProximoItem(antigoPrimeiroItem);
		}
		tamanho++;
	}

	/**
	 * Adiciona um novo item no final da lista.
	 * 
	 * @param novoItem
	 *            Novo item a ser adicionado.
	 */
	public void adicionarNoFinal(Integer novoItem) {
		if (tamanho == 0) {
			ultimoItem = new No();
			ultimoItem.setItem(novoItem);
			primeiroItem = ultimoItem;
		} else {
			No antigoUltimoItem = ultimoItem;
			ultimoItem = new No();
			ultimoItem.setItem(novoItem);
			antigoUltimoItem.setProximoItem(ultimoItem);
		}
		tamanho++;
	}

	/**
	 * Adiciona um novo item na posição desejada na lista
	 * 
	 * @param novoItem
	 *            Novo item a ser adicionado.
	 * @param posicao
	 *            Posição na qual o item deve ser adicionado. Caso o valor da
	 *            posição seja menor que 1 ou maior que o valor de
	 *            <b>tamanho</b> - 1, então o item não é adicionado.
	 * @return <b>true</b> caso o item tenha sido adicionado com sucesso;
	 *         <b>false</b> c.c.
	 */
	public boolean adicionarNaPosicao(Integer novoItem, int posicao) {
		if (posicao >= 1 && posicao <= tamanho + 1) {
			if (posicao == 1) {
				adicionarNoInicio(novoItem);
			} else if (posicao == tamanho + 1) {
				adicionarNoFinal(novoItem);
			} else {
				No novoNo = new No();
				novoNo.setItem(novoItem);
				int contador = 1;
				No itemAnteriorAoNovo = primeiroItem;
				while (contador < posicao - 1) {
					itemAnteriorAoNovo = itemAnteriorAoNovo.getProximoItem();
					contador++;
				}
				novoNo.setProximoItem(itemAnteriorAoNovo.getProximoItem());
				itemAnteriorAoNovo.setProximoItem(novoNo);
				tamanho++;
			}
			return true;
		}
		return false;
	}
}