Alguem ai sabe a diferença entre ArrayList e LinkedList?
gostaria de saber também se eles tem diferença no que quis respeito a performace.
Abraços
ArrayList é mais rápida para inserir e retirar e o linkedlist é mais rápida para percorrer!
linkedlist mantem a ordem de inserção.
ArrayList também, só as que herdam de Set que não possuem essa característica!
LinkedList não é mais rápida para percorrer (de onde você tirou essa conclusão?), mas é mais rápida para você poder fazer inserções em alguma posição arbitrária na lista, ou então para fazer remoções.
É o contrário, LinkedList é mais rápido para inserir e retirar e sua iteração é mais lenta.
LinkedList é bom pra implementar stack ou queue.
Pelo próprio algoritmo de uma LinkedList você vê que ela é mais lenta pra percorrer, imagina você tá no meio da lista e quer ir pro inicio ou fim.
Já o ArrayList é mais rápido para iteração e acesso randomico.
Você fornece o index e já tem acesso ao valor.
Mas para adicionar um item ou remover, só a manipulação de memória já deixa mais lento, etc.
PS.: um Vector é igual um ArrayList, só que é sincronizado para uso com threads.
bezier curve, como disse o enovais, eu inverti as características das implementações, e a propósito eu não tirei a conclusão eu li
http://java.sun.com/docs/books/tutorial/collections/implementations/index.html
Leiam essa maravilhosa discussão sobre o assunto:
http://www.guj.com.br/posts/list/133646.java
E a diferença fundamental entre ArrayList e LinkedList é a forma com que os objetos são armazenados internamente.
No caso do ArrayList, ele utiliza um vetor(Object[]) e no caso do LinkedList, ele usa uma lista encadeada.
Só um detalhe… a menos que você tenha uma lista muito grande (e o tamanho varia de máquina para máquina), geralmente o ArrayList será mais rápido que o LinkedList, em todas as situações, incluindo remover e inserir dados.
Também é bom lembrar a diferença do ponto de vista de memória. O ArrayList tem consideravelmente menos overhead do que o LinkedList. No caso do ArrayList, existirá um único inteiro para a lista toda. Enquanto no LinkedList, pelo menos duas referências para cada elemento, e uma adicional para o primeiro e último elementos.
[quote=belitos]Alguem ai sabe a diferença entre ArrayList e LinkedList?
gostaria de saber também se eles tem diferença no que quis respeito a performace.
Abraços[/quote]
Isto não é verdade quando estamos inserindo e removendo no fim da lista.
:arrow: ArrayList é uma lista (List) onde sua implementação é uma tabela indexada em memória (um array)
:arrow: LinkedList é uma lista (List) onde sua implementação é uma lista duplamente encadeada onde cada elemento aponta para o próximo elemento e para o elemento anterior.
:arrow: A performance de iterações de ambas as implementações (ArrayList e LinkedList) são iguais. Percorrer elementos de forma sequencial em ambas as implementações tem o mesmo custo ou uma diferença insignificante.
List<String>linkedList = new LinkedList<String>();
//Adiciona itens
for(String valor: linkedList) {
}
List<String>arrayList = new ArrayList<String>();
//Adiciona itens
for(String valor: arrayList) {
}:arrow: Acesso aleatório por indice o ArrayList tem performance superior na maioria dos casos.
//Acesso imediato
String valor1000 = arrayList.get(1000);
//Tempo de acesso pode variar de acordo com o tamanho da lista, caso a lista tenha 10000 itens para acessar o item 1000 o LinkedList irá percorrer todos os itens até o item 1000.
String valor1000 = linkedList.get(1000);
//Acesso imediato pois é o primeiro item
String valor1000 = linkedList.get(0);
//Acesso imediato pois é o último item
String valorX = linkedList.get( linkedList.size() );:arrow: Inclusão e remoção de itens no inicio e fim da lista tem performance superior no LinkedList. Remoção durante iterações (Iterator) tbém tem performance superior no LinkedList.
Isto ocorre pois o ArrayList tem que reindexar e redimencionar a lista nestas operações, ou seja, ArrayList tem mais overhead de processamente nestas operações.
:arrow: Inclusão e remoção de itens por indice temos quase que a mesma situação que temos com o acesso aleatório por indice.
Meio polemico o assunto
hahaa
obrigado a todos!
Não é polêmico cada um tem suas vantagens e desvantagens… qual o melhor? Depende como você irá manipular…
De onde você tirou isso? Nunca que uma estrutura que possui objetos encontrados sequencialmente em memória terá performance semelhante a outra em que os elementos estão completamente espalhados. A cada elemento percorrido num LinkedList, ocorrem buscas na memória, perdas do cache, e coisas do tipo. Percorrer um LinkedList é significativa mais lento que um ArrayList.
Aliás, é por isso que para listas pequenas, essa diferença chega a ser superior ao tempo de remoção de um item no ArrayList. Não lembro onde li um artigo que explicava em detalhes isso, inclusive com benchmarks, assim que eu achar, posto aqui.
Agora, para aplicações comerciais comuns, na maior parte dos casos, a diferença de tempo de todas as operações será pouco significativa.
[quote=bombbr] Inclusão e remoção de itens no inicio e fim da lista tem performance superior no LinkedList. Remoção durante iterações (Iterator) tbém tem performance superior no LinkedList.
Isto ocorre pois o ArrayList tem que reindexar e redimencionar a lista nestas operações, ou seja, ArrayList tem mais overhead de processamente nestas operações.
:arrow: Inclusão e remoção de itens por indice temos quase que a mesma situação que temos com o acesso aleatório por indice.[/quote]
Novamente, isso só é válido para listas onde esse overhead do ArrayList é superior ao overhead que o LinkedList tem ao percorrer a lista. Mas isso pode sim ser usado como regra prática, e você só vai ter diferença mesmo, caso sua aplicação faça um uso muito intensivo das listas.
Agora, geralmente, você não terá problemas de performance, seja lá qual for a lista que estiver usando. Caso tenha, ainda recomendo que se use um profiler, pois geralmente o list poderá ser trocado por outra coleção (e, tipicamente, será um set, não um outro tipo de lista).
No fim da lista, a remoção e a inclusão é mais rápida, geralmente, no ArrayList. No caso do ArrayList, obtém-se instantaneamente a posição do fim da lista (como no LinkedList), e já haverá espaço de memória alocado, do contrário do LinkedList, que terá que alocar a memória na hora. A performance só é amortizada pois muitas vezes a lista terá de ser realocada, mas geralmente essa realocação não chega a ter impacto de performance muito significativo, pois tende a se estabilizar após um certo período de tempo.
Remover do último elemento, num arraylist, envolve apenas a atualização de uma variável contadora. O elemento nem sequer precisa ser encontrado. No caso do LinkedList, ir até o último elemento, navegar até o anterior, e atualizar lá um índice. Claro que nesse caso, a diferença de performance dos dois é irrisória.
Da onde vc tirou essa informação que o ArrayList TEM que redimensionar?
[quote=clone_zealot][quote=bombbr]
:arrow: Inclusão e remoção de itens no inicio e fim da lista tem performance superior no LinkedList. Remoção durante iterações (Iterator) tbém tem performance superior no LinkedList.
Isto ocorre pois o ArrayList tem que reindexar e redimencionar a lista nestas operações, ou seja, ArrayList tem mais overhead de processamente nestas operações.
[/quote]
Da onde vc tirou essa informação que o ArrayList TEM que redimensionar?[/quote]
Redimensionar, não, mas reindexar sim. Para remover um elemento num arraylist, copia-se todos os elementos posteriores a ele, a uma posição anterior.
Essa cópia é extremamente rápida, pois é feita de uma única vez, com funções específicas, e não há necessidade de reservar novos espaços de memória.
Eu imaginei.
Em resumo, ArrayList é a opção indicada para 99% dos casos.
Complementando o que disse operações de inclusão em ArrayList exite redimencionamento do array interno, o que provoca um overhead de processamento.
Operação de remoção de um elemento em uma posição aleatória ocorre o que eu chamo de “reindexar”, pois ocorre uma reorganização dos elementos no array, isto ocorre através de cópias de array.
Amigo, vá estudar estruturas de dados… listas encadeadas são tão rápidas quanto acesso sequencial em memória (array), por isso disse “Percorrer elementos de forma sequencial em ambas as implementações tem o mesmo custo ou uma diferença insignificante.”
Ninguém esta falando de listas pequenas… para listas pequenas use qualquer coisa…
Concordamos em algo…
Na dúvida use ArrayList e pronto…
[quote=ViniGodoy][quote=clone_zealot][quote=bombbr]
:arrow: Inclusão e remoção de itens no inicio e fim da lista tem performance superior no LinkedList. Remoção durante iterações (Iterator) tbém tem performance superior no LinkedList.
Isto ocorre pois o ArrayList tem que reindexar e redimencionar a lista nestas operações, ou seja, ArrayList tem mais overhead de processamente nestas operações.
[/quote]
Da onde vc tirou essa informação que o ArrayList TEM que redimensionar?[/quote]
Redimensionar, não, mas reindexar sim. Para remover um elemento num arraylist, copia-se todos os elementos posteriores a ele, a uma posição anterior.
Essa cópia é extremamente rápida, pois é feita de uma única vez, com funções específicas, e não há necessidade de reservar novos espaços de memória.[/quote]
Claro que existe redimencionamento no ArrayList…ou você acha que um ArrayList já inicia com 1000000000 de posições…
O que quiz dizer é que o array interno do ArrayList “cresce” conforme são adicionados elementos…