Listas (parte 2 de 3)

    Olá, galera!

    Esta é a segunda e penúltima aula sobre listas que veremos na disciplina Estruturas de Dados. O conteúdo dela é bem interessante, pois ensina a criar uma lista encadeada genérica e também mostra o uso da interface List do pacote java.util. Abraço!




Classe NoGenerico

package br.edu.ifms.aula;

/**
 * Nó da lista genérica.
 * 
 * @author Prof.º Sidney
 * 
 */
public class NoGenerico<T> {

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

 /**
  * Ponteiro para o próximo item da lista.
  */
 private NoGenerico<T> proximoItem;

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

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

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

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

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

Classe ListaEncadeadaGenerica

package br.edu.ifms.aula;

/**
 * Encapsula uma lista encadeada de inteiros.
 * 
 * @author Prof.º Sidney
 * 
 */
public class ListaEncadeadaGenerica<T> {

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

 /**
  * Primeiro item da lista.
  */
 private NoGenerico<T> primeiroItem;

 /**
  * Último item da lista.
  */
 private NoGenerico<T> ultimoItem;

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

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

 /**
  * Retorna o último item da lista.
  * 
  * @return O último item da lista.
  */
 public NoGenerico<T> 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 NoGenerico<T> pegarItem(int posicao) {
  if (tamanho > 0 && posicao >= 1 && posicao <= tamanho) {
   NoGenerico<T> 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) {
   NoGenerico<T> item = primeiroItem;
   NoGenerico<T> anterior = null;
   int contador = 1;
   while (contador < posicao) {
    anterior = item;
    item = item.getProximoItem();
    contador++;
   }
   NoGenerico<T> 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(T novoItem) {
  if (tamanho == 0) {
   primeiroItem = new NoGenerico<T>();
   primeiroItem.setItem(novoItem);
   ultimoItem = primeiroItem;
  } else {
   NoGenerico<T> antigoPrimeiroItem = primeiroItem;
   primeiroItem = new NoGenerico<T>();
   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(T novoItem) {
  if (tamanho == 0) {
   ultimoItem = new NoGenerico<T>();
   ultimoItem.setItem(novoItem);
   primeiroItem = ultimoItem;
  } else {
   NoGenerico<T> antigoUltimoItem = ultimoItem;
   ultimoItem = new NoGenerico<T>();
   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(T novoItem, int posicao) {
  if (posicao >= 1 && posicao <= tamanho + 1) {
   if (posicao == 1) {
    adicionarNoInicio(novoItem);
   } else if (posicao == tamanho + 1) {
    adicionarNoFinal(novoItem);
   } else {
    NoGenerico<T> novoNo = new NoGenerico<T>();
    novoNo.setItem(novoItem);
    int contador = 1;
    NoGenerico<T> itemAnteriorAoNovo = primeiroItem;
    while (contador < posicao - 1) {
     itemAnteriorAoNovo = itemAnteriorAoNovo.getProximoItem();
     contador++;
    }
    novoNo.setProximoItem(itemAnteriorAoNovo.getProximoItem());
    itemAnteriorAoNovo.setProximoItem(novoNo);
    tamanho++;
   }
   return true;
  }
  return false;
 }
}

Classe ExemploList

package br.edu.ifms.aula;

import java.util.ArrayList;
import java.util.List;

public class ExemploList {

 public static void main(String[] args) {
  List<Integer> lista = new ArrayList<Integer>();
  // Se quiser, troque a linha acima pela linha abaixo
  // List<Integer> lista = new LinkedList<Integer>();
  // Lembre-se de importar a classe LinkedList:
  // import java.util.LinkedList;

  // Inserindo ítens no final da lista
  lista.add(12);
  lista.add(-38);
  lista.add(827);

  // Inserindo ítens no início da lista
  lista.add(0, 125);
  lista.add(0, -387);
  lista.add(0, 82735);

  List<Integer> listaExtra = new ArrayList<Integer>();
  listaExtra.add(11);
  listaExtra.add(22);
  listaExtra.add(33);
  // Adiciona todos os ítens da lista extra no final da primeira lista
  lista.addAll(listaExtra);

  listaExtra.add(44);
  listaExtra.add(55);
  listaExtra.add(66);
  /**
   * Adiciona todos os ítens da lista extra na posição desejada da
   * primeira lista
   */
  lista.addAll(3, listaExtra);

  /**
   * Removendo ítens da lista pelo índice. Na interface List, os elementos
   * são indexados na forma [0..tamanho da lista - 1]
   */
  lista.remove(0);
  lista.remove(4);

  /**
   * Removendo um item da lista caso ele exista. O cast para Object é
   * necessário para que o compilador diferencie a chamada ao método de
   * remoção por ocorrência do método de remoção por índice. Retorna true
   * caso o item exista; false c.c.
   */
  lista.remove((Object) 77); // Retorna false

  // Verifica se um item está contido na lista
  if (lista.contains(12)) {
   System.out.println("A lista contém o item 12.");
  }

  // Imprime o índice da primeira ocorrência do item de valor 125
  System.out.println(lista.indexOf((Object) 125));

  // Verifica se a lista contém uma sublista
  if (lista.containsAll(listaExtra)) {
   System.out.println("A primeira lista contém a lista extra!");
  }

  // Substituindo o elemento da terceira posição da lista
  lista.set(3, 42);

  // Verifica se a lista está vazia
  if (lista.isEmpty()) {
   System.out.println("A lista está vazia.");
  } else {
   System.out.println("A lista contém " + lista.size()
     + " elemento(s).");
  }

  // Verifica a última ocorrência de um determinado valor na lista
  System.out.println("A última ocorrência de 55 se dá na posição "
    + lista.lastIndexOf(55));

  // Imprime o tamanho da lista
  System.out.println("Tamanho atual da lista: " + lista.size());

  /**
   * Pega uma parte da lista. O primeiro índice é inclusivo; o segundo é
   * exclusivo.
   */
  List<Integer> outraLista = lista.subList(2, 4);

  // Converte a lista de inteiros em um vetor de objetos
  Object[] vetor = lista.toArray();
  // Converte a lista de inteiros em um vetor de inteiros
  Integer[] vetorInteiros = new Integer[lista.size()];
  lista.toArray(vetorInteiros);
  for (Integer elemento : vetorInteiros) {
   System.out.println("Elemento: " + elemento);
  }

  /**
   * Listas do tipo List podem ser iteradas em laços for each.
   * 
   */
  for (Integer item : lista) {
   System.out.print(item + " ");
  }

  System.out.println();

  // Percorrendo a lista com um laço for comum
  for (int i = 0; i < lista.size(); i++) {
   System.out.print(lista.get(i) + " ");
  }

  System.out.println();

  // Remove todos os ítens da lista
  lista.clear();

  System.out.println("Tamanho atual da lista: " + lista.size());
 }
}