ArrayList e LinkedList

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.

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

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.

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.

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?

clone_zealot:

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.

Da onde vc tirou essa informação que o ArrayList TEM que redimensionar?

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.

@Vini: por isso que perguntei só sobre a parte do redimensionar ;D

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…

ViniGodoy:

clone_zealot:

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.

Da onde vc tirou essa informação que o ArrayList TEM que redimensionar?

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.

Claro que existe redimencionamento no ArrayList…ou você acha que um ArrayList já inicia com [telefone removido] de posições…
O que quiz dizer é que o array interno do ArrayList “cresce” conforme são adicionados elementos…

Alexandre Gazola:

Em resumo, ArrayList é a opção indicada para 99% dos casos.

Não diria 99% dos casos… mas na dúvida use ArrayList…

Filas e Pilhas são caso típicos do uso do LinkedList que por sinal implementa a interface Queue.

Bem… eu dediquei 8 anos da minha vida ao desenvolvimento de sistemas de tempo real. Posso dizer para você que sei um bocado sobre estruturas de dados, e como elas trabalham.

Se você acha que acessar espaços diferentes de memória tem a mesma performance de uma área contínua e sequencial, sugiro que estude:

• Como o mapeamento de memória é feito;
• O que são páginas de memória;
• O que é perda de cache;

Depois conversamos.

Não se trata apenas da estrutura de dados, e sim de como a memória é organizada.

bombbr:

Claro que existe redimencionamento no ArrayList…ou você acha que um ArrayList já inicia com [telefone removido] de posições…
O que quiz dizer é que o array interno do ArrayList “cresce” conforme são adicionados elementos…

Ele estava falando em redimensionar sempre. O ArrayList não trabalha assim. Ele controla o tamanho da lista, e sempre que ela excedida, o list cresce numa taxa pré-definida, maior do que apenas 1 único elemento.

Isso evita que memória seja criada e destruída o tempo todo, o que é uma operação bastante cara (da qual o linked list não foge).

ViniGodoy:

bombbr:

Claro que existe redimencionamento no ArrayList…ou você acha que um ArrayList já inicia com [telefone removido] de posições…
O que quiz dizer é que o array interno do ArrayList “cresce” conforme são adicionados elementos…

Ele estava falando em redimensionar sempre. O ArrayList não trabalha assim. Ele controla o tamanho da lista, e sempre que ela excedida, o list cresce numa taxa pré-definida, maior do que apenas 1 único elemento.

Isso evita que memória seja criada e destruída o tempo todo, o que é uma operação bastante cara (da qual o linked list não foge).

Não existe redimensionamento quando a estrutura de dados é um arranjo.

Quando usamos um ArrayList, a estrutura de dados usada é um arranjo de tamanho inicial 10. Ao tentar inserir o 11º elemento, é alocado um arranjo de tamanho 20. Os elementos do arranjo antigo são copiados para o arranjo novo. Após, a referência do antigo é passada para o novo. Com isso, o arranjo de tamanho 10 pode ser limpo pelo coletor de lixo. Como último passo, o 11º elemento é colocado no arranjo de 20 posições.

Assim, o novo arranjo criado sempre terá tamanho 2n, com n sendo o tamanho do arranjo que ocasionou a criação dele.

ECO2004:

Não existe redimensionamento quando a estrutura de dados é um arranjo.

Quando usamos um ArrayList, a estrutura de dados usada é um arranjo de tamanho inicial 10. Ao tentar inserir o 11º elemento, é alocado um arranjo de tamanho 20. Os elementos do arranjo antigo são copiados para o arranjo novo. Após, a referência do antigo é passada para o novo. Com isso, o arranjo de tamanho 10 pode ser limpo pelo coletor de lixo. Como último passo, o 11º elemento é colocado no arranjo de 20 posições.

Assim, o novo arranjo criado sempre terá tamanho 2n, com n sendo o tamanho do arranjo que ocasionou a criação dele.

Quanto a dizer que o ArrayList dobra de tamanho. Isso não é verdade a documentação deixa claro que o tamanho da taxa de crescimento não é especificado:

Quanto a “redimensionar” o array interno, eu estava falando do ponto de vista de funcionalidade. Na prática, evidentemente um novo array é criado e os dados são copiados.
Em algumas linguagens, como o C++, é possível redimensionar endereços de memória com o comando realloc. O SO só irá copiar dados caso efetivamente não haja memória disponível na vizinhança - mas essa não é a forma que o ArrayList trabalha, no caso do Java, creio que ele copie sempre (com uma chamada otimizada a System.arrayCopy, mas não deixa de ser cópia).

PS: Acho muito estranho você chamar array de “arranjo”. Arranjo em português é normalmente a tradução de “enumeration”, da análise combinatória. A título de curiosidade, onde você viu essa tradução?

ViniGodoy:

ECO2004:

Não existe redimensionamento quando a estrutura de dados é um arranjo.

Quando usamos um ArrayList, a estrutura de dados usada é um arranjo de tamanho inicial 10. Ao tentar inserir o 11º elemento, é alocado um arranjo de tamanho 20. Os elementos do arranjo antigo são copiados para o arranjo novo. Após, a referência do antigo é passada para o novo. Com isso, o arranjo de tamanho 10 pode ser limpo pelo coletor de lixo. Como último passo, o 11º elemento é colocado no arranjo de 20 posições.

Assim, o novo arranjo criado sempre terá tamanho 2n, com n sendo o tamanho do arranjo que ocasionou a criação dele.

E você voltou depois de 3 anos no tópico para dizer exatamente o que eu disse no post anterior ao seu por que…?

Quanto a dizer que o ArrayList dobra de tamanho. Isso não é verdade a documentação deixa claro que o tamanho da taxa de crescimento não é especificado:

PS: Acho muito estranho você chamar array de “arranjo”. Arranjo em português é normalmente a tradução de “enumeration”, da análise combinatória. A título de curiosidade, onde você viu essa tradução?

Quanto a redimensionar o array interno, eu estava falando do ponto de vista de funcionalidade. Na prática, evidentemente um novo array é criado e os dados são copiados.

Eu procurei um tópico que falasse no assunto. Depois de estudar um livro, vi que o que vocês disseram não estava de acordo. Vocês usaram redimensionar. Quis corrigir. Com relação ao número de espaços de memória alocados, faça um teste debugando. Verá que são alocados 10 posições iniciais.

Com relação ao uso de arranjo. Tanto faz. Só traduzi o nome.

Finalmente, com relação a ressuscitar o tópico. Que que tem?

Veja que no início do tópico falo em realocar. Só mudou pq vi que o pessoal estava falando “redimensionar” para essa operação.
Mas você tem razão em sua observação. Arrays nunca são redimensionados. O processo de redimensionar envolve nova alocação de memória e cópia.

Testes assim não são confiáveis:

• Nada garante que o java irá mudar essa implementação no futuro;
• Nada garante que outras implementações (como a da Oracle, Apple ou da Google) sigam essa política;
• Nada garante que em todas as alocações será assim.

Você deve sempre respeitar o que o contrato (a documentação) diz. Jamais programe por experimentação, pois empresas não tem que dar suporte ao que elas não prometeram.

Ah, pensei que vc tivesse lido isso em algum lugar.

Essa tradução é bastante estranha, e não é usada na área.
Array é comumente traduzido como vetor.

Nada, mas geralmente ressuscitamos quanto é algo essencial, para resolve-lo. Até pq, muita gente pode responder a usuários que nem mais frequentam ao fórum, sem perceber que se trata de um tópico antigo. Por isso, só recomendo ressuscitar tópicos sem solução, quando você encontrar a solução e ainda assim, quando for algo que aparentemente será muito procurado.

Na verdade, vi a tradução no livro Estruturas de dados e Algoritmos em Java - 4º edição. Quando li pela primeira vez, também não tinha entendido. Somente entendi quando peguei o livro em inglês.

Eu tava com uma dúvida sobre o assunto. Procurei no site e achei. Depois, achei no livro explicando mais detalhadamente. Acredito que esses tipos de correções são válidas, mesmo em tópicos antigos. Quem for ler vai saber o conceito correto.

Pelo que o site diz, fecha-se um tópico quando colocamos “resolvido” em sua frente. Para mim, ele continua aberto, porém, esquecido.