Estou desenvolvendo um projeto e me foi solicitado a implementação de uma lista encadeada própria, isto é, não posso usar LinkedList que já vem na Collection. Além disso, para utilizar essa lista, preciso também usar um iterador. Sei que essa ferramenta é utilizada para percorrer a lista, permitir que nós sejam removidos nesse processo e torna tudo isso mais rentável em termos de memória e velocidade. A minha dúvida é: não consegui entender como o iterator vai proporcionar isso. Digamos que, por exemplo, eu precise remover da minha lista encadeada o nó que possui um determinado objeto com determinado valor do atributo x, eu não precisaria ainda percorrer a lista do início e realizar comparações diversas, mesmo por meio do iterator?
O iterator permite encapsular a forma de percorrer e remover elementos da sua estrutura de dados.
Assim, o código para percorrer uma lista comum ou uma lista encadeada ficará sempre igual:
Iterator<Elemento> it = lista.iterator();
while (it.hasNext()) {
Elemento elem = it.next();
if (elem == elementoAExcluir) {
it.remove();
}
}
No caso da remoção, esse código não apresenta vantagem.
Agora, imagine o que aconteceria com a lista encadeada, se o código (sem iterator) fosse implementado assim:
for (int i = 0; i < lista.size(); i++) {
Elemento elem = lista.get(i);
if (elem == elementoAExcluir) {
it.remove();
}
}
Observe que essa é uma maneira muito intuitiva de percorrer a lista, uma vez que usar um for é perfeitamente aceitável para uma lista não encadeada.
Esse código tem diversos problemas:
a) O método get() iria percorrer a lista encadeada a partir do início a cada passo do for.
b) Depois de removido, a lista muda de tamanho e o número dos índices após esse elemento muda. Nesse caso, um elemento seria pulado.
Finalmente, é bom ressaltar que no Java 5 ou superior, se você implementar a interface Iterable em sua coleção, caso não haja necessidade de remoção, é possível iterar sobre a lista assim:
for (Elemento elem : lista) {
//Usa o elem
}
Finalmente, note que você também poderia fazer iterators para estruturas de dados bem mais complexas, como árvores.
Obrigado pela resposta, ViniGodoy. Consegui compreender melhor.
Fazendo uma analogia com C, os iterators funcionam, por exemplo, como os ponteiros, correto?
[quote=ViniciusAlmeida]Obrigado pela resposta, ViniGodoy. Consegui compreender melhor.
Fazendo uma analogia com C, os iterators funcionam, por exemplo, como os ponteiros, correto?[/quote]
Numa analogia beeeem remota, sim. Estariam mais relacionados aos ponteiros de função, como se você apontasse para uma função “avança” que mudasse dependendo do tipo da estrutura de dados.
[quote=ViniGodoy][quote=ViniciusAlmeida]Obrigado pela resposta, ViniGodoy. Consegui compreender melhor.
Fazendo uma analogia com C, os iterators funcionam, por exemplo, como os ponteiros, correto?[/quote]
Numa analogia beeeem remota, sim. Estariam mais relacionados aos ponteiros de função, como se você apontasse para uma função “avança” que mudasse dependendo do tipo da estrutura de dados.[/quote]
Ok.
Uma última dúvida, se eu quiser, por exemplo, acessar o primeiro elemento da lista por meio do iterator isso não é possível, correto? Porque o método next nunca vai me retornar o primeiro. Eu deveria ter um atributo com referência para o primeiro da lista no iterator então?
É possível, o iterator começa na posição BOF (Before First). O método next(), ao rodar a primeira vez, retorna o primeiro elemento.
Então preciso inicializar o meu iterator com uma referência para o primeiro elemento nó da lista? Eu tava criando ele a partir do primeiro nó diretamente, ou seja, passando a referência para o primeiro nó da lista no momento de instanciar.