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.
Errado colega, nesse ponto:
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.
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.
[quote=saoj]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.
[/quote]
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.
Acho que vc não entendeu o IF/THEN/ELSE.
Claro. E foi por isso que eu disse:
Da onde vc tirou que o cara tem que usar LinkedList quando houver indexacao?
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?
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.
:roll:
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) ?
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.
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.
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 
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) ?
[/quote]
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.
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.
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.
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.
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…
[quote=saoj][quote=nel]
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()
[/quote]
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…
[/quote]
Leu o link que passei ?
[quote=nel][quote=saoj][quote=nel]
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()
[/quote]
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…
[/quote]
Leu o link que passei ?[/quote]
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.
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.
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).
Nesse caso aqui eu diria muito melhor porque vc nunca paga o preco do SHIFT do ArrayList. Era o meu ponto. Remocao numa LinkedList é mais rápida do que numa ArrayList.
O problema não é a remocao em si, mas ter que encontrar o objeto a ser removido dentro da lista, linearmente, via iteracao.
O fato de eu usar minha própria linkedlist onde os objetos que eu coloco dentro dela SÃO um entry dessa lista, me livra desse problema. Só que para uma java.util.LinkedList que precisa aceitar objetos quaisquer, não há como escapar desse custo de encontrá-los quand se quer removê-los. A não ser que como vc mencionou muito bem, vc já tenha que iterar sobre eles de qualquer jeito…
[quote=nel]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.[/quote]
Quando você fala que o LinkedList é mais lento em insersão e remoção porque tem que iterar todos os itens vc está falando de remoção e inserção por índice. É preciso que vc diga isto, porque nesse caso sim é mais lento, mas essa utilização não existe na prática.
É extremamente raro que alguém faça remove(i) em listas. Agora,se vc considerar o caso mais comum que é remover durante a iteração com iterator.remove() o linkedlist é mais rápido. Pq ? porque não tem que redimencional o array subjacente à lista porque não ha nenhum.
No mundo das listas ha duas formas de uso, por indice e por iterator. Fazer um for com i e percorrer de X a Y ok. Mas isso é muiiiiittttoooo raro. Normalmente vc quer iterar todos os elementos da lista. Então vc usa iterator ou for extendido.
Ora, usando com índice qualquer classe que implemente RandomAcess será melhor. Logo, ArrayList é melhor quando se usa get(i). Mas no caso padrão em que se usa iterator ambas têm o mesmo resultado. Isto se vc apenas iterar.
Se vc iterar e remover itens enquanto iterar usar ge(i) remove(i) é extremamente falho e usar iterator.remove é muito simples. Logo, vc usa iterator.remove. iterator.remove é mais rápido no linkedlist. E quando digo rápido me refiro a que é O(1) e não O(n).
Quando estamos falando de inserção linkedlist tb é melhor. Isto pq o arraylist tem um custo exponencial quando se incluem itens além do tamanho reservado.
Quando usar um ArrayList ? Apenas quando o tamanho é pre-conhecido , fixo e a iteração não irá invocar iterator.remove.
Quando usar LinkedList ? Quando o tamanho não é conhecido, não é fixo ou a iteração irá invocar iterator.remove.
Quando vc cria um ArrayList sempre passe no construtor o tamanho. Se vc não consegue saber qual o tamanho, então isso significa que 1) vc não leu o codigo com atenção ou 2) deveria usar um linkedlist.
Pense agora na situação em que vc tem uma lista A e quer produzir uma lista B só que alguns elementos de A não estarão em B. Vc cria um for em cima de A e copia para B apenas os elementos que passam no if do filtro.
Ok, mas que tipo de lista será B ?
Podemos dizer que sabemos o tamanho de B ? Não. Mas sabemos que será igual ou menor que o de A. Se criarmos um ArrayLsit nos arriscamos a ficar com um array de varias posições vazias. Então a solução é usar um linkedlist.
O linkedList é em geral mais lento que o arraylist quando se usa get(i), excepto quando i= 0 ou i= ultimo elemento.É que o linkedlist é na realidade duplamente linkado. Por causa disto, os metodos get/removeFist e get/removeLast existe no linkedList.
E com eles é possivel criar queues (filas). Arualmente LinkedList tb implement Queue e DeQueue. É a coleção mais versátil que existe.
Em programas reais é incomum que as pessoas usem LinkedList. isto porque elas não sabem usar. Então ArrayList é pau para toda a obra. Ora, de fato, a interface list não deveria ser usada em sistemas reais porque usar get(i) é horrivel.
Contudo em java List tem um significado semântico : elementos repetidos e em ordem. Por causa da semantica sofre o design.
O mais correto é sempre usar Collection (seguindo a regra de : use a interface mais abstrata possivel). Assim vc força todos a usar iterator que é o certo. A coleção pode ter repetidos e estar em uma ordem. Se não estiver use Set.
Desta forma vc elimina o uso de List e por consequência impede que se use get(i). Neste cenário é mais simples escolher as listas, mas ArrayList é normalmente usado porque normalmente a lista tem tamanho fixo e conhecido. Mas , por exemplo, quando vc lê de um ResultSet JDBC quando usar ? LinkedList ( porque mesmo o tamanho sendo fixo, vc não sabe qual é).
Para resolve o dilema várias bibliotecas de collections com o Apache Collections ou o Guava adotam o conceito de Bag. Bag é como uma lista, ou seja permite repetidos e uma certa ordem, mas não permite indexação. Se vc não gostar de usar apenas Collection e Set existe sempre a opção de criar a interface Bag e usá-la nos seus sistemas.
Outro problema que leva ao uso indevido de List são as tags core do jsp que só aceita list. Isto é muito limitativo e acaba forçando que seus business/services/daos retornam List.
A solução aqui é construir sua biblioteca de tags de forma a usar iterator e não get(i) como as tags jsp padrão.
Espero ter ajudado a esclarecer. A discussão toda foi porque uns estavam falando de velocidade de indexação e outros de velocidade em iteração. São coisas diferentes. Mas em sistemas reais a velocidade de indexação é práticamente irrelevante porque se usa muito pouco for com get(i) porque é um anti-pattern.
Acho que o problema aí é que mesmo que eu já tenha o objeto a ser removido, eu não tenho como removê-lo sem percorrer a lista inteira atrás dele. Concorda? Seja via remove(indice) ou via remove(object).
E numa linked list, que na verdade é uma double-linked list, tendo algum node da lista fica muito fácil remove-lo. Basta atualizar os ponteiros (node.prev and node.next). Mas no java.util.LinkedList, eu não tenho acesso ao objeto Node, logo tenho que loopar atrás dele.
Foi o que eu falei inicialmente: se vc não sabe quantos elementos vc vai ter que colocar na sua lista, só dá pra ir de LinkedList. Agora se vc sabe de antimão o tamanho (máximo) da sua lista (veja que tamanho != capacidade), então vc pode ir de ArrayList sem problemas. O que o cara pode fazer é pegar um tamanho máximo bem grande para nunca estourar o ArrayList, mas ir de LinkedList nesses casos me parece mais correto, a não ser que vc realmente precisa de indexação no resultado retornado. Quando vc precisa de indexação, só se pode ir de ArrayList.
Então repetindo a minha frase inicial: “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.”
Agora se vc precisa de REMOÇÃO de qualquer objeto aleatório da lista (não é o caso de quando vc está iterando), então nem o ArrayList e nem o LinkedList vão prestar. Eu implemento minha própria linked list e faço meus objetos extenderem Node (nao ideal mas funciona que é uma beleza). Fiquei agora curioso para saber qual é a solução padrão que o Java oferece nesse caso, ou seja, qual é a solucao padrão que o Java oferece para linked lists onde eu possa remover qualquer elemento de forma rápida via um list.remove(elemento).
Essas são questão que me afligem, na verdade.
Eu trabalho com JEE, pois meu foco são sistemas WEB. Isso envolve EJB e bla bla bla. Ok. Me expressei mal e acabei gerando discussão com o saoj sendo que percebo que ambos estavam discutindo pontos de vista um pouco diferentes. O meu problema nisso, é que grande parte das listas que crio são enviadas para a página, ou seja, existe uma tabela de objetos em que o usuário final pode simplesmente “brincar” nela. Pode remover a posição, 10, 10, 1000 ou qualquer uma. Por conhecer que o LinkedList é mais lento para remoções por índice (get(i)) procuro usar o ArrayList, todavia, em listas que não há a participação direta do usuário final, uso o LinkedList.
Se é um anti-pattern, qual seria a solução ideal? Ou a mais correta para uma situação como citei? Acredito que o iterator e um equals não seja, até porque, eu teria de sobrescrever o equals() no meu objeto (não estou dizendo que isso é um problema!) para que o mesmo faça a forma correta. Digo pois, 99% do casos, sei o índice que o usuário final selecionou lá na página web e o mesmo é enviado para lado do servidor, onde simplesmente, aplico o remove(i). Quando pode enviar uma lista para o lado servidor, bom, ai eu simplesmente itero sobre ele. Para finalizar e seria opinião de todos, o meu costume é foreach e não iterator, em tudo, incluindo remove (menos quando tenho de remover um objeto da própria lista, obviamente). Estou fazendo bobagem? Ou o iterator só terá uma diferença significativa em relação ao remove?
Abraços a todos.
[quote=nel]Essas são questão que me afligem, na verdade.
Eu trabalho com JEE, pois meu foco são sistemas WEB. Isso envolve EJB e bla bla bla. Ok. Me expressei mal e acabei gerando discussão com o saoj sendo que percebo que ambos estavam discutindo pontos de vista um pouco diferentes. O meu problema nisso, é que grande parte das listas que crio são enviadas para a página, ou seja, existe uma tabela de objetos em que o usuário final pode simplesmente “brincar” nela. Pode remover a posição, 10, 10, 1000 ou qualquer uma. Por conhecer que o LinkedList é mais lento para remoções por índice (get(i)) procuro usar o ArrayList, todavia, em listas que não há a participação direta do usuário final, uso o LinkedList.
[/quote]
Este mecanismo é um pouco estranho. Vc usa o numero da linha da tabela para corresponder com a lista do lado do servidor. Normalmente se requer que os objetos tenham alguma identidade que os distingua uns dos outros, como um id de banco. E é o id e não o indice que é passado ao servidor.
Veja que para a remoção de um único objeto não é certo qual é melhor. O linkedlist é O(i) e o arraylist é O(n-i) já que o primeiro tem que iterar i vezes , mas a remoção é O(1) e o segundo encontrar o item é O(1) , mas tem que fazer o shift que é O(n-i) (não tenho a certeza deste aqui por não sei exactamente qual é a performance do System.arraycopy)
É dificil dizer sem saber o que vc está fazendo, mas eu nunca tinha visto essa forma de trabalhar antes.
Normalmente se usa um mecanismo de filtro ( como o que vai ser incorporado no java 8 para todas as classes de coleção). A ideia é ter uma interface Filter com um método que retorna booleano.
Ai iteramos a lista, se o filtro acusa false, removemos o item com iterator.remove
Como o Filter é uma classe podemos implementar como quisermos. Normalmente se comparar o código ou se usa o equals. Mas nunca o index porque esta é uma tecnica genérica aplicável a qualquer Iterable cujo iterador permita remoção.
Se vc tem esse caso de uso que usa o index e realmente vc vê isso como a forma certa, então realmente usar remove(i) é a melhor opção , no seu caso.
Atualmente (java 5 em diante) foreach é a forma certa de iterar. Nada de while nem for com iterator. A única exceção, vc está certo, é quando vc quer usar o iterator.remove.
Respondendo ao saoj , eu não costumo usar remove nunca nos meus projetos. É muito raro. mas quando preciso normalmente está envolvido algum processo iterativo ( como copiar ou filtrar uma lista). E nesse caso sempre uso iterator.remove. Não tenho que implementar nenhum objeto novo.
Quando quero trabalhar como algoritmos mais complexo normalmente uso Map. Em que a chave do mapa é o objeto que irá servir para encontra o outro. E ai usar remove(key) é rápido no HashMap. Se o objeto é a sua ppr chave , uso Set. O set usa um map por detrás dos panos, então dá no mesmo. Por outro lado, se vc está interessado em remover algo, normalmente não trabalha com repetidos e o Set é mais eficiente.
Remove diretamente de listas, realmente não posso opinar muito porque não uso. E não vejo necessidade.