Collection

JavaEvangelist Membro desde: 06/11/2006 01:11:23 Mensagens: 305 Offline

Eu tenho uma dúvida com relação às classes que implementam a inteface List.

Um ArrayList é redimensionável, como fala na documentação.

Quando eu uso um LinkedList, por exemplo, eu posso adicionar e remover elementos quando eu quiser. Isso não o torna redimensionável também?

Caso eu esteja errado, o que significa redimensionável?

Bom dia ECO2004, as coleções tem de ser redimensionáveis, crescerem à medida do necessário pois possuem algoritmos bem consolidados e testados para fazê-lo, caso contrário usaríamos array's comuns não é mesmo?, a questão é que as coleções diferem uma das outras em suas construções e destinadas à diferentes situações, onde um ArrayList é baseado na indexação de seus elementos, mais rápidos no acesso e na iteração, já um LinkedList é baseado no conceito de pilhas e filas e os elementos possuem um encadeamento entre si, sendo mais lenta na iteração, porém mais rápidos na inserção e remoção dos elementos, tendo a possibilidade de inserir nas extremidades, ....., enfim todas são redimensionáveis, porém cada uma para um propósito que nos cabe escolher qual a melhor maneira e para qual situação usar.

JWizard Membro desde: 01/10/2009 13:51:10 Mensagens: 2364 Offline

ironmarq wrote:Bom dia ECO2004, as coleções tem de ser redimensionáveis, crescerem à medida do necessário pois possuem algoritmos bem consolidados e testados para fazê-lo, caso contrário usaríamos array's comuns não é mesmo?, a questão é que as coleções diferem uma das outras em suas construções e destinadas à diferentes situações, onde um ArrayList é baseado na indexação de seus elementos, mais rápidos no acesso e na iteração, já um LinkedList é baseado no conceito de pilhas e filas e os elementos possuem um encadeamento entre si, sendo mais lenta na iteração, porém mais rápidos na inserção e remoção dos elementos, tendo a possibilidade de inserir nas extremidades, ....., enfim todas são redimensionáveis, porém cada uma para um propósito que nos cabe escolher qual a melhor maneira e para qual situação usar.

Errado colega, nesse ponto:

ironmarq wrote:já um LinkedList é baseado no conceito de pilhas e filas e os elementos possuem um encadeamento entre si, sendo mais lenta na iteração, porém mais rápidos na inserção e remoção dos elementos, tendo a possibilidade de inserir nas extremidades

Depende da sua aplicação, a diferença de tempo de remoção de um item em uma LinkedList e um ArrayList pode ser consideravelmente alto. Isso a favor do ArrayList. Citou certo, os itens do LinkedList são encadeados e por isso mais lento em sua remoção. Se tiver uma lista com 1 milhão de registros e quiser remover o da posição 900 mil, ele vai percorrer item a item para executar essa remoção, todavia, um ArrayList pode ir diretamente para a posição 900 mil, sem que itere sobre ela.

O LinkedList mantém o estado em que são inseridos os objetos e aloca para os locais livres. Como é posicionado a cada "próximo" item, ele é mais rápido para inserção. É importante conhecer a API Collection, pois ela pode se tornar um grande diferencial, principalmente em sistemas que exigem alto processamento e resposta rápida.

This message was edited 3 times. Last update was at 06/02/2012 03:39:59

Como regra eu só uso ArrayList quando preciso de INDEXAÇÃO ( list.get(3) ) ou QUANDO O TAMANHO DA MINHA LISTA É CONHECIDO NA HORA DA CRIAÇÃO.

Acho que tirando esses dois casos aí em cima eu quase sempre vou de LinkedList.

Alguém discorda? Posso estar esquecendo algum outro caso, mas esses são o que vem a minha cabeça de forma automática e acredito ser a regra básica que todos deveriam utilizar.

JWizard Membro desde: 01/10/2009 13:51:10 Mensagens: 2364 Offline

saoj wrote:Como regra eu só uso ArrayList quando preciso de INDEXAÇÃO ( list.get(3) ) ou QUANDO O TAMANHO DA MINHA LISTA É CONHECIDO NA HORA DA CRIAÇÃO.

Acho que tirando esses dois casos aí em cima eu quase sempre vou de LinkedList.

Alguém discorda? Posso estar esquecendo algum outro caso, mas esses são o que vem a minha cabeça de forma automática e acredito ser a regra básica que todos deveriam utilizar.

Discordo. O caso de indexação é a mesma questão do remove. Por se tratar de uma lista encadeada, fica necessário que ela percorra item á item, até chegar ao item escolhido. A questão de conhecer o tamanho da lista, acho desnecessário. Por default, um ArrayList é criado com 10 posições. Tratando-se de JPA, tu não sabe quantos registros serão retornados do seu banco, pode ser 1 ou 1 milhão. Se houver necessidade de manipulação na lista, como remoções, um LinkedList pode vir a lhe dar dor de cabeça e nesse caso eu aconselho ArrayList. Mas a API Collection é bem ampla e dispõe de inúmeros implementações, portanto, um bom estudo sobre ela é ideal para saber escolher a API mais adequada para a sua necessidade.

This message was edited 5 times. Last update was at 06/02/2012 11:10:54

Acho que vc não entendeu o IF/THEN/ELSE.

nel wrote:
Por se tratar de uma lista encadeada, fica necessário que ela percorra item á item, até chegar ao item escolhido

Claro. E foi por isso que eu disse:

saoj wrote:
Como regra eu só uso ArrayList quando preciso de INDEXAÇÃO

Da onde vc tirou que o cara tem que usar LinkedList quando houver indexacao?

nel wrote:
Se houver necessidade de manipulação na lista, como remoções, um LinkedList pode vir a lhe dar dor de cabeça e nesse caso eu aconselho ArrayList.

Vc está errado aqui. Remocão é sempre melhor com LinkedList pois não requer shift, a não ser que vc esteja removendo o último elemento. Da onde vc tirou que é melhor usar ArrayList?

nel wrote:
A questão de conhecer o tamanho da lista, acho desnecessário. Por default, um ArrayList é criado com 10 posições.

Vc não entendeu. A última coisa que vc quer é ter que redimensionar um ArrayList. Quando vc tem certeza do tamanho do array, esse problema desaparece.

nel wrote:
Mas a API Collection é bem ampla e dispõe de inúmeros implementações, portanto, um bom estudo sobre ela é ideal para saber escolher a API mais adequada para a sua necessidade.

JWizard Membro desde: 01/10/2009 13:51:10 Mensagens: 2364 Offline

saoj wrote:Da onde vc tirou que o cara tem que usar LinkedList quando houver indexacao?

Ué, foi você mesmo que disse isso, eu não falei isso. A indexação que você se refere foi um get(3). Se for um get(900000) ?

saoj wrote:Vc está errado aqui. Remocão é sempre melhor com LinkedList pois não requer shift, a não ser que vc esteja removendo o último elemento. Da onde vc tirou que é melhor usar ArrayList?

Sempre é uma palavra forte, eu diria em 99% das coisas que ela é incluída. Se é sempre, você está me dizendo que usar uma LinkedList para manipular listas que ultrapassam a casa dos 100 mil objetos, é tranquilo, é isso ? Você pode remover qualquer posição colega, não necessariamente a última. Discordo plenamente da sua afirmação que LinkedList é melhor para remoção de objetos.

saoj wrote:Vc não entendeu. A última coisa que vc quer é ter que redimensionar um ArrayList. Quando vc tem certeza do tamanho do array, esse problema desaparece.

Ninguém quer redimensionar um Array, todavia, 99% das ações que tomo não tenho conhecimento do tamanho de array que estarei manipulando. Quando eu sei, a história é outra.

saoj wrote:Mas a API Collection é bem ampla e dispõe de inúmeros implementações, portanto, um bom estudo sobre ela é ideal para saber escolher a API mais adequada para a sua necessidade.

Isso não foi um recado para você, caso tenha entendido dessa forma. Foi um recado para todos, me incluo nisso. Eu não sei usar uma Queue, BlockingDeque entre outras que fazem parte da API Collection

This message was edited 4 times. Last update was at 06/02/2012 12:06:23

nel wrote:

saoj wrote:Da onde vc tirou que o cara tem que usar LinkedList quando houver indexacao?

Ué, foi você mesmo que disse isso, eu não falei isso. A indexação que você se refere foi um get(3). Se for um get(900000) ?

Tá bem claro na primeira linha do meu post que INDEXACÃO => ArrayList, nunca LinkedList. Eu não sei da onde vc tirou essa idéia de que eu falei que LinkedList é bom para indexacão. Isso é o básico do básico.

nel wrote:
Sempre é uma palavra forte, eu diria em 99% das coisas que ela é incluída. Se é sempre, você está me dizendo que usar uma LinkedList para manipular listas que ultrapassam a casa dos 100 mil objetos, é tranquilo, é isso ? Você pode remover qualquer posição colega, não necessariamente a última. Discordo plenamente da sua afirmação que LinkedList é melhor para remoção de objetos.

Acho que vc deveria rever os seus conceitos sobre remocao. LinkedList NUNCA requer shift na hora remover. ArrayList SEMPRE requer, com excecão do caso especial quando vc está removendo o último elemento. Conclusão: LinkedList é preferível para remocões. Não sei da onde vc tirou que ArrayList é melhor para remocão. E isso não muda tendo a sua lista 10 ou 10 milhões de objetos.

nel wrote:
Ninguém quer redimensionar um Array, todavia, 99% das ações que tomo não tenho conhecimento do tamanho de array que estarei manipulando. Quando eu sei, a história é outra.

Então vai de LinkedList se não precisar de indexacão. Geralmente é esse o caso quando vc não sabe o tamanho da sua lista, ou seja, vc não vai precisar de indexacao e vai usar iterators.

Repetindo o meu IF/THEN/ELSE que acredito trata a grande maioria dos casos:

Como regra eu só uso ArrayList quando preciso de INDEXAÇÃO ( list.get(3) ) ou QUANDO O TAMANHO DA MINHA LISTA É CONHECIDO NA HORA DA CRIAÇÃO.

if (precisa de indexacao OR a lista possui um número de elementos fixo que vc conhece de antimão) then ArrayList else LinkedList.

JWizard Membro desde: 01/10/2009 13:51:10 Mensagens: 2364 Offline

Dá uma lida aqui, faz o favor: http://www.guj.com.br/java/71065-qual-a-diferenca-entre-linkedlist-arraylist-e-vector

Não sou eu quem precisa rever os conceitos nesse caso. O LinkedList só é muito bom para remover o primeiro e último item da lista, não os seus "interiores", porque tem métodos como o removeLast()

Dá uma lida no link que lhe passei e por favor, pesquisa na net e veja a opinião da maioria se eles usam LinkedList quando querem remover objetos do array.
Edit: não só remover mas como manipular um objeto do interior da lista.

nel wrote:
O LinkedList só é muito bom para remover o primeiro e último item da lista, não os seus "interiores", porque tem métodos como o removeLast()

Na boa, não sei de tudo e estou sempre aprendendo, mas nesse caso acima vc está falando uma besteira sem tamanho. Vc sabe o que é shift? Acho que não...

JWizard Membro desde: 01/10/2009 13:51:10 Mensagens: 2364 Offline

saoj wrote:

nel wrote:
O LinkedList só é muito bom para remover o primeiro e último item da lista, não os seus "interiores", porque tem métodos como o removeLast()

Na boa, não sei de tudo e estou sempre aprendendo, mas nesse caso acima vc está falando uma besteira sem tamanho. Vc sabe o que é shift? Acho que não...

Leu o link que passei ?

nel wrote:

saoj wrote:

nel wrote:
O LinkedList só é muito bom para remover o primeiro e último item da lista, não os seus "interiores", porque tem métodos como o removeLast()

Na boa, não sei de tudo e estou sempre aprendendo, mas nesse caso acima vc está falando uma besteira sem tamanho. Vc sabe o que é shift? Acho que não...

Leu o link que passei ?

Li e coloquei a minha observacao lá. Vc confiou cegamente no meu chará. Recomendo não acreditar em ninguém, nem em mim. Faca vc mesmo suas pesquisas e tire vc mesmo suas conclusões. Qualquer um pode falar besteira.

Errar é humano. Insistir no erro sem aprender e sem fazer suas proprias pesquisas é que é o problema.

JWizard Membro desde: 01/10/2009 13:51:10 Mensagens: 2364 Offline

http://www.flaviojmendes.com/blog/2010/05/13/comparacao-linkedlist-e-arraylist/

Achei interessante essa afirmação. Quando quero remover ou buscar (get(i)) um elemento na lista, normalmente uso o ArrayList.
Mas ao que vi em afirmações, o remove é satisfatório mas o get(i) não, na LinkedList.

Vou aguardar mais pessoas virem com essa afirmação e as respectivas explicações. Entenda algo saoj, o melhor das discussões é a evolução de cada um e o conhecimento que podemos tirar dela, não para mostrar quem entende mais. Em nenhum momento foi minha intenção, mas já li muitos links com a mesma afirmação que fiz aqui. A noite, com mais tempo, pesquiso e posto qualquer coisa que julgar útil.

ECO2004, todas as listas são passiveis de alteração em seu tamanho.

Abraços.

This message was edited 1 time. Last update was at 06/02/2012 12:51:11

Acho que eu é que estava errado aqui.

O problema é simples. Apesar de em teoria remocao numa linked list ser sempre mais rápida que remocão num array, o problema está no fato de que o java.util.LinkedList não lhe dá acesso ao objeto LinkedList.Entry, ou seja, de posse do objeto a ser removido, vc não tem como fazer essa remocão no LinkedList sem antes pagar o preco de encontrá-lo, *mesmo que vc já o tenha*.

Então por causa disso o outro Sergio falou que remocao no LinkedList é custoso. Não é a remocao em si, mas sim o preco que vc precisa pagar para encontrar o objeto a ser removido.

O que vai acontecer é que o LinkedList vai ser mais rápido se o objeto a ser removido estiver no início da lista e o ArrayList vai ser mais rápido se o objeto a ser removido estiver no final da lista. (Assumindo uma lista relativamente grande)

O ideal é vc ter a sua própria implementacão de LinkedList onde o objeto que vc coloca na sua lista extende ou implementa um Entry dessa lista. Daí de posse do objeto vc pode rapidamente remove-lo sem qualquer custo de encontrá-lo. Mas como vc encontrou o objeto primeiro de tudo? Provavelmente veio de um map...

A remoção durante a iteração também costuma a ser mais rápida no LinkedList.

Na verdade, o ideal é mesmo fazer um comparativo de performance, com um profiler. Em muitos casos, o ArrayList pode superar a performance do LinkedList, mesmo com elementos sendo removidos do meio da lista. Isso porque o ArrayList é um bloco de memória contínuo e, portanto, passível de otimizações (como caches e operações de cópia de memória eficientes, como o memcpy).

Também deve ser considerado o overhead de memória. O LinkedList irá consumir 2 referências para cada elemento da lista. Ou seja, para uma lista de um tipo de dado pequeno (como um int), você pode ter um gasto de memória quase 3x maior do que o ArrayList. O ArrayList consome um contador para a quantidade de elementos, um contador para o tamanho do buffer, e um int para cada espaço não usado no buffer. Esse último valor é o mais crítico, mas gira em torno de 20% da quantidade de elementos da lista (ou seja, numa lista com 50 elementos, teríamos 48 bytes de overhead, contra 408 do LinkedList).

Notícias, artigos e o maior fórum brasileiro sobre Java