[quote=Alexandre Gazola]Em resumo, ArrayList é a opção indicada para 99% dos casos.
[/quote]
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.
[quote=bombbr]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…
[/quote]
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).
[quote=ViniGodoy][quote=bombbr]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…
[/quote]
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).[/quote]
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.
[quote=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. [/quote]
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:
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?
[quote=ViniGodoy][quote=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. [/quote]
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.[/quote]
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.
