estas 3 classes implementam uma lista…
mas n vejo grandes diferencas entre eles…
alguem pode me explicar?
[quote=hcbelias]estas 3 classes implementam uma lista…
mas n vejo grandes diferencas entre eles…
alguem pode me explicar?[/quote]
As diferenças são basicamente relativas a inserção/remoção e iteração.
A LinkedList é a mais rápida para inserção e iteração. Se vc precisa de uma lista que vc carrega e depois apenas itera ( sem remover ou alterar) Linked é melhor.
ArrayList é melhor se vc precisa de acesso com indice ( chamado acesso aleatorio) ou seja , quando vc usa o lista.get(i), por isso ela implementa tb a interface RandomAccess.
Quanto à iteração ArrayList é mais rápida ( em comparação com a LinkedList) se usar um inteiro como indice , mas mais lenta se usar o iterator(). Com o novo for-estendido é irrelevante uma vez que a JVM vai otimizar e escolher a melhor forma.
Vector é uma classe mais antiga que foi remodelada para ter a interface de List. todos os acesso de inserção e remoção são sincronizados e ela só deve ser usada em algoritmos que necessitem desse sincronismo.
Apartir dojava 1.5 existe a classe CopyOnWriteArrayList que é mais rápida que a LinkedList para o caso em que vc simplesmente carrega a classe e depois a itera. A vantagem desta nova lista é que vc pode adicionar um elemento enquanto está iterando a lista. Coisa que vc não pode fazer nas outras três. CopyOnWriteArrayList é ideal se o seu objeto precisa mantar um conjunto de listeners, por exemplo.
LinkedList tem uma vantagem suplementar, ela tb implementa a interface Queue. Isto basicamente significa que vc pode criar lógicas de LIFO, FIFO , FILO e LILO de forma simplificada. Mas, normalmente nesse contexto as outras listas nem sequer são uma opção.
[quote=hcbelias]estas 3 classes implementam uma lista…
mas n vejo grandes diferencas entre eles…
alguem pode me explicar?[/quote]
muitas o vector, os metodos sao sincronizados e isso afeta o desempenho qdo vc nao precisa de sincronização. Outro vc aqui pode escolhher aonde quer colocar o elemento
ArrayList - metodos nao sincronizados e vc pode escolher a posicao do elemento.
LinkedList - é uma lista porem ordenada pela ordem de inserção.
Agora sempre me confudo… tem um que o acesso é mais rapido… e a inserção mais lenta… e o outro é o inverso… so que sempre esqueço se eh o arraylist ou linkedList.
:?
Ela não deveria ser mais rápida que ArrayList para remoção? Para remover um elemento no meio, basta ajustar 2 ponteiros. O ArrayList precisa corrigir todos os índices daquela posição em diante.
Ou não tem nada a ver?
[quote=Schuenemann][quote=sergiotaborda]
As diferenças são basicamente relativas a inserção/remoção e iteração.
A LinkedList é a mais rápida para inserção e iteração. Se vc precisa de uma lista que vc carrega e depois apenas itera ( sem remover ou alterar) Linked é melhor.
[/quote]
Ela não deveria ser mais rápida que ArrayList para remoção? Para remover um elemento no meio, basta ajustar 2 ponteiros. O ArrayList precisa corrigir todos os índices daquela posição em diante.
Ou não tem nada a ver?[/quote]
É verdade que o ArrayList precisa corrigir todos os indices , mas o Linked precisa iterar todos os nodos para encontrar o elemento. Não basta ajustar 2 referencias , têm que saber primeiro que referencias ajustar 
É o mesmo quando vc usa lista.get(i) num LinkedList ele não sabe qual é o elemento i , ele tem que iterar todos até chegar no i. Por isso não se deve usar get(i) numa interface List e sempre o iterador. A menos que seja explicito na documentação esse contrato ou a lista implemente RandomAccess. (Na prática ninguém verifica isso , dai a vantagem do for-estendido)
Detalhe, linked é mais rápido para inserção e remoção nas extremidades da lista ( por isso tem métodos como removeFirst() e removeLast() ) , mas é mais lento para remoção de um elemento no interior.
Faz sentido… pensei apenas na remoção em si.
Valeu :mrgreen:
Acredito que essa afirmacão está errada. Quando vc remove um elemento do interior de uma lista, ArrayList vai requerer um SHIFT bastante custoso. Já no LinkedList essa operacao é bem rápida. É o oposto do que vc afirmou aí em cima.
[quote=saoj][quote]
Detalhe, linked é mais rápido para inserção e remoção nas extremidades da lista ( por isso tem métodos como removeFirst() e removeLast() ) , mas é mais lento para remoção de um elemento no interior.
[/quote]
Acredito que essa afirmacão está errada. Quando vc remove um elemento do interior de uma lista, ArrayList vai requerer um SHIFT bastante custoso. Já no LinkedList essa operacao é bem rápida. É o oposto do que vc afirmou aí em cima.
[/quote]
Acho que eu entendi agora a confusão. O problema não é a REMOCÃO em si. O problema é a LOCALIZACÃO do elemento no meio da linked list. Obviamente vc não vai poder usar indexacão. Mas quando se diz que REMOCAO numa LinkedList é mais rápida que uma REMOCAO num ArrayList, é claro que se está assumindo que o elemento a ser removido já está em mãos, daí basta fazer a atualizacao na sua double linked list.
Acho que se vc está falando de uma java.util.LinkedList, vc terá que sempre pagar o preco de encontrar o elemento a ser removido, então isso será um problema, não pela remocao em si, mas por ter que achar o elemento na lista.
Note que se estiver removendo elementos próximos do início, o custo de achá-los será baixo enquanto a remocao será bem rápida. Sendo a lista longa, teríamos um custo bastante alto de shift caso estivéssemos utilizando um ArrayList. 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, estava cacheado em algum lugar, não-interessa… De posse desse objeto eu não deveria ter que encontrá-lo novamente na lista para remove-lo, sendo essa lista uma (double) linked list.
Sendo a java.util.LinkedList uma lista de objetos genéricos, vc sempre cai no problema de ter que encontrá-los na lista. Por essa lado o errado aqui sou eu.
[quote=saoj][quote=saoj][quote]
Detalhe, linked é mais rápido para inserção e remoção nas extremidades da lista ( por isso tem métodos como removeFirst() e removeLast() ) , mas é mais lento para remoção de um elemento no interior.
[/quote]
Acredito que essa afirmacão está errada. Quando vc remove um elemento do interior de uma lista, ArrayList vai requerer um SHIFT bastante custoso. Já no LinkedList essa operacao é bem rápida. É o oposto do que vc afirmou aí em cima.
[/quote]
Acho que eu entendi agora a confusão. O problema não é a REMOCÃO em si. O problema é a LOCALIZACÃO do elemento no meio da linked list. Obviamente vc não vai poder usar indexacão. Mas quando se diz que REMOCAO numa LinkedList é mais rápida que uma REMOCAO num ArrayList, é claro que se está assumindo que o elemento a ser removido já está em mãos, daí basta fazer a atualizacao na sua double linked list.
Acho que se vc está falando de uma java.util.LinkedList, vc terá que sempre pagar o preco de encontrar o elemento a ser removido, então isso será um problema, não pela remocao em si, mas por ter que achar o elemento na lista.
Note que se estiver removendo elementos próximos do início, o custo de achá-los será baixo enquanto a remocao será bem rápida. Sendo a lista longa, teríamos um custo bastante alto de shift caso estivéssemos utilizando um ArrayList. 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, estava cacheado em algum lugar, não-interessa… De posse desse objeto eu não deveria ter que encontrá-lo novamente na lista para remove-lo, sendo essa lista uma (double) linked list.
Sendo a java.util.LinkedList uma lista de objetos genéricos, vc sempre cai no problema de ter que encontrá-los na lista. Por essa lado o errado aqui sou eu.
[/quote]
A solução para esse dilema não é criar uma entry e sim usar iterator.remove. Ao iterar já temos o objeto em mãos e por consequência a remoção em si é rápida. A iteração também é rápida.
Comparemos com usar remove(i). O remove(i) itera até i e remove. É a mesma coisa. Ambos são O(i)
Se estamos interessados em remover apenas um item remove(i) é melhor, não porque é mais rápido, mas porque é mais simples de usar.
Agora, se estamos interessados em remover vários elementos, ai sim ha uma diferença entre for de remove(i) e for com iterator.remove são diferentes
No primeiro a cada i temos que percorrer a lista novamente o que faz com que o algoritmo seja um for de for e seja O(ni) no segundo vamos iterando e removendo o algoritmo é apenas O(n) já que não é um for de for.
Com arrayList remove(i) ou iterator.remove sempre é um for de for, porque embora pegar e remove o item seja O(1) fazer o shift requer O(k) onde k = n - i
Acho que agora ficou claro.