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) { ... } }
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 percor ...
