Explorando o Padrão de Projeto Iterator em Listas Ligadas

Se você já explorou o fascinante mundo das listas ligadas ou está apenas começando a desbravá-lo, recomendo dar uma olhada no meu artigo sobre o poder das listas ligadas em Java. Lá, você encontrará informações detalhadas sobre implementações e exemplos práticos: Desvendando o Poder das Listas Ligadas – Implementação em Java e Exemplos Práticos

Agora, vamos mergulhar em um padrão de design essencial ao lidar com coleções de objetos, especialmente em ambientes onde a sequencialidade é crucial: o Padrão de Projeto Iterator.

O Padrão Iterator: Navegando pela Coleção de Forma Eficiente

O Iterator é um padrão de design que oferece uma maneira elegante de percorrer os elementos de uma coleção de objetos sem expor os detalhes internos dessa coleção. Ao usar o Iterator, você pode acessar os elementos de maneira sequencial, sem precisar conhecer a estrutura subjacente da lista ligada ou de qualquer outra coleção.

O Iterator fornece métodos como next(), que avança para o próximo elemento da lista, e hasNext(), que verifica se ainda existem elementos a serem percorridos.

public class IteratorListaLigada {
    private Elemento elemento;

    public IteratorListaLigada(Elemento primeiro) {
        this.elemento = primeiro;
    }

    public boolean temProximo() {
        return elemento.getProximo() != null;
    }

    public Elemento getProximo() {
        elemento = elemento.getProximo();
        return elemento;
    }

    public Elemento getElemento() {
        return this.elemento;
    }
}

Para consolidar a implementação do padrão Iterator em nossa Lista Ligada, incorporaremos um método especializado responsável por instanciar um novo Iterator. Essa adição não apenas tornará nosso código mais modular, mas também garantirá uma coesão eficaz entre a coleção e o iterador, seguindo os princípios de design de software.

Vejamos como esse método é implementado na classe ListaLigada:

public class ListaLigada {
    // ...

    public IteratorListaLigada getIterator() {
        return new IteratorListaLigada(this.primeiro);
    }
}

Ao chamar getIterator() em uma instância da Lista Ligada, estamos criando e obtendo um novo Iterator pronto para percorrer os elementos da lista. Isso facilita a iteração ao fornecer uma interface clara e encapsular a lógica de navegação pela lista ligada.

Testando o Iterator: Comparando Desempenho entre Vetor e Lista Ligada

Vamos testar o desempenho do Iterator em uma Lista Ligada comparado com um vetor. Para isso, utilizaremos um simples algoritmo que compara o tempo de execução ao adicionar e ler elementos em ambas as estruturas de dados.

public static void main(String[] args) {
    ListaLigada lista = new ListaLigada();
    ArrayList vetor = new ArrayList();

    // Adicionar elementos
    int limite = 100000;
    long tempoInicial = System.currentTimeMillis();
    
    // Adicionando elementos ao vetor
    for (int i = 0; i < limite; i++) {
        vetor.add(i);
    }
    tempoFinal = System.currentTimeMillis();
    System.out.println("Adicionou " + limite + " elementos no vetor");
    System.out.println(tempoFinal - tempoInicial);

    // Adicionando elementos à lista ligada
    tempoInicial = System.currentTimeMillis();
    for (int i = 0; i < limite; i++) {
        lista.adicionar("a." + i);
    }
    tempoFinal = System.currentTimeMillis();
    System.out.println("\n\nAdicionou " + limite + " elementos na lista");
    System.out.println(tempoFinal - tempoInicial);

    // Ler valores
    tempoInicial = System.currentTimeMillis();
    
    // Lendo elementos do vetor
    for (int i = 0; i < vetor.size(); i++) {
        vetor.get(i);
    }
    tempoFinal = System.currentTimeMillis();
    System.out.println("\n\nTempo de leitura do vetor");
    System.out.println(tempoFinal - tempoInicial);

    // Lendo elementos da lista ligada com Iterator
    tempoInicial = System.currentTimeMillis();
    IteratorListaLigada iterator = lista.getIterator();
    while (iterator.temProximo()) {
        iterator.getProximo();
        iterator.getElemento();
    }
    tempoFinal = System.currentTimeMillis();
    System.out.println("\n\nTempo de leitura da lista com Iterator");
    System.out.println(tempoFinal - tempoInicial);
}

Ganho de Desempenho com Iterator

A implementação do Iterator parece simples, mas seu impacto é significativo, especialmente ao lidar com grandes conjuntos de dados. Comparado com a abordagem padrão de iteração em uma lista, onde percorremos do primeiro até o último elemento e depois novamente do primeiro até a posição desejada, o Iterator proporciona uma alternativa eficiente para esse problema.

// Implementação padrão
tempoInicial = System.currentTimeMillis();
for (int i = 0; i < lista.getTamanho(); i++) {
    lista.get(i);
}

// Implementação com o Iterator
IteratorListaLigada iterator = lista.getIterator();
while (iterator.temProximo()) {
    iterator.getProximo();
    iterator.getElemento();
}

Conclusão:

Essas poucas mudanças na abordagem de iteração podem resultar em ganhos significativos de desempenho, especialmente quando lidamos com volumes massivos de dados. O Iterator é, portanto, uma ferramenta valiosa a ser utilizada em seu arsenal de padrões de design ao enfrentar desafios de eficiência e sequencialidade em suas aplicações.