Qual a diferenca entre linkedlist arraylist e vector?

da uma olhada ae

http://www.javafaq.nu/java-article1111.html

hcbelias:

estas 3 classes implementam uma lista…
mas n vejo grandes diferencas entre eles…
alguem pode me explicar?

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.

hcbelias:

estas 3 classes implementam uma lista…
mas n vejo grandes diferencas entre eles…
alguem pode me explicar?

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?

Schuenemann:

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.

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?

É 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.

saoj:

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.

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.

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.

saoj:

saoj:

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.

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.

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.

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.