Estruturas de dados com classes genéricas

Aprenda a utilizar estrutura de dados em Java para facilitar o uso e aumentar a segurança de classes genéricas que implementam estruturas de dados.

Fique por dentro
Este artigo é útil por apresentar como utilizar classes genéricas, ou classes parametrizadas, para codificar uma estrutura de dados, de maneira que o compilador consiga realizar a checagem dos tipos que nela forem armazenados. Além disso, algumas características mais avançadas das classes genéricas, como as que fazem uso de conceitos como o relacionamento de herança entre classes, serão explicadas e demonstradas, de forma que, em um processo incremental, problemas como a inclusão inadvertida de elementos de tipos distintos na estrutura de dados; uso de hierarquias de classes para definir um conjunto de diferentes tipos de elementos que podem ser manipulados na estrutura; e também a especificação de um comportamento padronizado para os dados armazenados serão expostos e as suas soluções discutidas com base nos diferentes exemplos de código para cada uma destas situações. A partir desse conteúdo o leitor será capaz de desenvolver um código mais seguro e flexível, requisitos fundamentais para alcançar um código de qualidade.

No artigo “Programando com estruturas de dados e padrões de projeto”, publicado na Easy Java Magazine número 49, a estrutura de dados que utiliza uma sequência de nós auto ligados, conhecida como lista encadeada, foi descrita. No mesmo texto apresentou-se também o padrão Iterator, que permite a navegação, ou iteração, pela lista sem que seja necessário conhecer ou ter acesso aos detalhes da sua implementação, que pode ser, como no exemplo, por encadeamentos duplos, por encadeamentos simples ou mesmo utilizando vetores.

As listas são estruturas de dados muito flexíveis, permitindo que novos elementos sejam incluídos em qualquer posição, e também que sejam removidos de qualquer posição. Estas características já foram explicadas e demonstradas anteriormente, e o foco agora é em como melhorar a usabilidade da classe que as implementa.

Uma situação que pode ocorrer ao utilizar uma estrutura de dados como a que foi definia, e cuja estrutura está resumida na Listagem 1, é a inclusão, por acidente, de mais de um tipo de dado na mesma lista. Uma situação como esta é possível porque no código, para que seja viável armazenar referências a quaisquer objetos, os dados foram declarados como sendo do tipo Object. Como em Java todas as classes são estendidas direta ou indiretamente da classe Object, é possível referenciar qualquer objeto como sendo deste tipo, o que permite, também, que a classe de lista funcione adequadamente sem que seja necessário alterar seu código para cada tipo com o qual se desejar trabalhar. Isto porque a lista não necessita saber qual é o tipo que está armazenando, mas apenas de uma referência ao objeto para que possa responder às consultas realizadas.


public class ListaDupEncadeada {
 // A classe que representa os nós da lista utiliza a classe Object 
 para definir a referência ao dado associado à posição da lista que este nó representa.
 private class No{
       // Referência ao próximo elemento da lista
       No proximo;
       // Referência ao elemento anterior na lista
       No anterior;
       // Referência ao dado armazenado no nó atual da lista
       Object dado;

       // Constrói um nó para armazenar um objeto na lista
       No(Object obj) { ... }
       // Constrói um nó para armazenar um objeto na lista, indicando quais os
       // nós anterior e próximo
       No(Object obj, No prox, No ant) { ... }
 }
 // Implementação da interface Iterator, que define os métodos de navegação na lista
 private class IteratorLista implements Iterator {
       // Referência ao nó apontado pelo iterador da lista durante a navegação
       No noAtual;

       // Retorna o dado associado ao nó atual. Caso o iterador não seja válido
       // (noAtual é nulo), retorna um objeto nulo
       public Object dado() { ... }
       // Coloca o iterador no próximo elemento da lista e retorna o dado
       // associado ao nó atual. Caso o iterador não seja válido (noAtual é
       // nulo), retorna um objeto nulo
       public Object proximo() { ... }
       // Coloca o iterador no elemento anterior da lista e retorna o dado
       // associado ao nó atual. Caso o iterador não seja válido (noAtual é
       // nulo), retorna um objeto nulo
       public Object anterior() { ... }
       // Verifica se existe um nó após o nó atual
       public boolean temProximo() { ... }
       // Verifica se existe um nó antes do nó atual
       public boolean temAnterior() { ... }
       // Verifica se o nó atual existe e é válido
       public boolean eValido() { ... }
 }

 // Nó inicial (primeiro) da lista encadeada
 No     inicio;
 // Nó final (último) da lista encadeada
 No     fim;
 // Tamanho da lista encadeada (número de nós na lista)
 int    tamanho;

 // Construtor
 public ListaDupEncadeada() { ... }
 // Retorna uma instância de Iterator para o primeiro nó da lista
 public Iterator iteradorInicio() { ... }
 // Retorna uma instância de Iterator para o último nó da lista
 public Iterator iteradorFim() { ... }
 // Retorna o tamanho da lista
 public int getTamanho() { ... }
 // Insere um novo nó no início da lista
 public int insereInicio(Object obj { ... }
 // Insere um novo nó no final da lista
 public int insereFim(Object obj { ... }
 // Insere um novo nó na posição indicada
 public int insere(Object obj, int pos) { ... }
 // Remove o nó do início da lista - retira o primeiro elemento
 // Retorna o objeto armazenado no primeiro nó da lista - que foi removido.
 public Object removeInicio(){ ... }
 // Remove o nó do final da lista - retira o último elemento
 // Retorna o objeto do último nó da lista - que foi removido.
 public Object removeFim(){ ... }
 // Remove um nó do meio da lista - retira o elemento da posição indicada
 // Retorna o objeto armazenado na posição indicada - que foi removida.
 public Object remove(int pos) { ... }
 // Retorna o objeto armazenado na posição indicada, sem remover o mesmo da lista
 public Object consulta(int pos) { ... }
}
Listagem 1. Classe para a estrutura de dados lista duplamente encadeada

Como já exposto, esta característica, que permite e facilita a implementação, também é uma fonte de problemas, pois como qualquer tipo de objeto pode ser referenciado como um Object, é possível que inadvertidamente sejam incluídas na mesma lista referências a objetos de tipos diferentes, causando, assim, comportamentos estranhos ou mesmo falhas graves na execução do sistema.

Nas Listagens 2 e 3 é apresentado um exemplo de utilização desta classe de lista explicitando este problema e a sua correspondente saída, com a inclusão de três valores do tipo String e três valores do tipo int. No exemplo, não foram realizadas operações que geram exceções, mas na saída apresentada pelo teste é possível perceber a diferença entre os tipos de dados armazenados.

Uma falha grave ocorreria se, por exemplo, fosse necessário realizar alguma operação específica com os dados, como o cálculo da soma de todos os valores armazenados, assumindo que a lista deveria conter apenas valores inteiros.


public class TesteLista {
public static void main(String[] args)  {
   // Lista encadeada
   ListaDupEncadeada lista = new ListaDupEncadeada();
   int val;

   // Strings a serem inseridas na lista
   String a = "str teste 01";
   String c = "str teste 03";
   String e = "str teste 05";

   // Inteiros a serem inseridos na lista
   int b = 2;
   int d = 4;
   int f = 6;

   // Mostra o tamanho atual da lista
   System.out.println("Tamanho: " + lista.getTamanho());
   
   // Insere uma String no início da lista
   val = lista.insereInicio(a);
   // Mostra o conteúdo da primeira posição da lista
   System.out.println("Inserindo: \"" + lista.consulta(1) + "\" -> Tamanho: " + val);
   // Insere um inteiro no início da lista
   val = lista.insereInicio(b);
   System.out.println("Inserindo: \"" + lista.consulta(1) + "\" -> Tamanho: " + val);
   // Insere uma String no início da lista
   val = lista.insereInicio(c);
   System.out.println("Inserindo: \"" + lista.consulta(1) + "\" -> Tamanho: " + val);
   // Insere um inteiro no início da lista
   val = lista.insereInicio(d);
   System.out.println("Inserindo: \"" + lista.consulta(1) + "\" -> Tamanho: " + val);
   // Insere uma String no início da lista
   val = lista.insereInicio(e);
   System.out.println("Inserindo: \"" + lista.consulta(1) + "\" -> Tamanho: " + val);
   // Insere um inteiro no início da lista
   val = lista.insereInicio(f);
   System.out.println("Inserindo: \"" + lista.consulta(1) + "\" -> Tamanho: " + val);

   // Mostra o tamanho atual da lista
   System.out.println("\nTamanho: " + lista.getTamanho());

   System.out.println("");

   // Iterador utilizado para percorrer a lista encadeada
   Iterator iterador = lista.iteradorInicio();

   // Contador de posições
   int i = 1;
   // Laço para percorrer a lista utilizando o iterador
   while (iterador.eValido()) {
          // Mostra o valor armazenado em cada posição da lista
          System.out.println("Posição " + i++ + ": -> \t" + iterador.dado());
          iterador.proximo();
   }

   System.out.println("");
   // Laço para remover todos os elementos da lista
   while(lista.getTamanho() > 0) {
          System.out.println("Removido do início: \"" + lista.removeInicio() + "\" -> Tamanho: " + lista.getTamanho());
}      
}      
}"

[...] continue lendo...

Artigos relacionados