Classe de coleção para navegação

http://java.sun.com/j2se/1.4.2/docs/api/java/util/LinkedList.html

Se for iterar pela lista, faça um favor para sua ram utilizando Iterators, e não um for … size().

LIPE:

Se for iterar pela lista, faça um favor para sua ram utilizando Iterators, e não um for … size().

Há algum artigo que me prove isso?

*não estou duvidando, apenas por aprendizado.
**eu uso for .size() :lol:

valeu! até mais…

Bem, aprendi a razão disso na palestra do Guilherme Silveira :thumbup:

Basicamente cada List provê uma implementação diferente sobre a maneira em que os objetos são guardados.

Por exemplo o ArrayList guarda os objetos dentro de um array comum de objetos. Portanto é muito simples fazer um list.get( 13 ), pois internamente ela fará return array[ 13 ]. Mas se fosse necessário inserir um objeto na posição 0 do array, internamente seria necessário realocar todas as instâncias para numa nova posição.

No caso da LinkedList, a implementação é diferente, fazendo com que seja muito simples inserir um objeto no topo ou no fim, porém, para pegar um objeto numa posição específica é bem mais lento.

Por esse motivo que todas as Collections implementam Iterator. Ao pedir este objeto para a coleção, ela retornara um objeto que sabe a melhor maneira possível para iterar sobre todos os objetos nela contidos.
Para o usuário do Iterator, tanto faz como ele funciona internamente, mas utilizá-lo ao inver do for … size() pode ser crítico ao mudar a implementação da Collection.

Um exemplo:

public void itera( List list )
{
    for( int i = 0; i < list.size(); i++ )
        System.out,.println( list.get( i ) );
}

public void test()
{
    List list = new ArrayList();

    for( int i = 0; i < 500000; i++ )
        list.add( new Object() );

    itera( list );
}

Esse processo ocorreria com uma certa tranquilidade. Mas caso o método test fizesse isto:

public void test()
{
    List list = new LinkedList();

    for( int i = 0; i < 500000; i++ )
        list.add( new Object() );

    itera( list );
}

Seu pc iria explodir

Você pode baixar os arquivos da palestra (cujos exemplos acima be baseei completamente) aqui:
http://www.guj.com.br/posts/list/20765.java

unnhh … massa mesmo essas dicas!!!..
estava estudando justamente isso aqui hoje …
Na verdade o LinkedList utiliza o algoritmo de ListaDuplamenteEncadeada,
e só vai ser util caso vc precise acessar , incluir , remover , elementos das pontas , inicio e fim da lista …

Vou dar uma olhada nesse material da palestra!!!

valeu mesmo cara pela dica… estava procurando um material desse…
isso que faz a diferenca em grandes aplicacoes !!! rsrsrs!!!
Essa galera do GUJ bota pra la!!!

rodei ate aqui um exemplo…

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Class1  {
  public Class1() {
  }
  
  public static void main(String[] args) {
    ArrayList c1 = new ArrayList();
    LinkedList c2 = new LinkedList();
    
    
    for (int i=0; i<1000; i++){
      c1.add(new Integer(i));
      c2.add(new Integer(i));
    }
    
    

    double l1 = System.currentTimeMillis();
    for(int i=0;i<60000;i++){
       c1.add(0, new Integer(i)) ;      
      
    }
    double l2 = System.currentTimeMillis() - l1;
    double tempo = l2/1000;
    System.out.println("tempo do ArrayList: " + tempo + " s");

    l1 = System.currentTimeMillis();
    for(int i=0;i<60000;i++){
       c2.add(0, new Integer(i)) ;      
    }
    l2 = System.currentTimeMillis() - l1;
    tempo = l2/1000;
    System.out.println("tempo do LinkedList: " + tempo + " s");
  }
  
}

Saida:

tempo do ArrayList: 7.11 s
tempo do LinkedList: 0.21 s

Eu andei lendo uns artigos no OnJava sobre coleções e os testes feitos mostram que em muito poucos casos a LinkedList é melhor que um ArrayList, inclusive nos casos em a melhora seria esperada. Na dúvida acabei rodando uns testes por conta própria (na 1.4, preciso refazer na 1.5) e confirmei que o desempenho da LinkedList é mesmo inferior ao do ArrayList e mesmo quando é superior a diferença não é significativa.

ahh … de uma pesquisada sobre ListIterator … vc pode navegar pra frente e pra tras…

ArrayList e LinkedList nao sao iguais. Possuem tempos diferentes e algoritmos diferentes.

Exemplo:

Tente adicionar 50000 objetos na posicao zero de uma arraylist. Cronometre o tempo
Faca o mesmo com linkedlist.
Resultado: linked list ganha

Tente fazer um for(int i=0;i<10000;i++) e chamar get(i) em uma linkedlist
Faca o mesmo para uma arraylist
Resultado: array list ganha

Resultado final:
Dependendo do que voce vai fazer a escolha de ArrayList ou LinkedList faz o seu programa funcionar o nao. Como o proprio Lipe comentou, voces podem encontrar o ppt da apresentacao com exemplos muito legais e explicacoes teorias: nao se iludam, a escolha do algoritmo nao eh facil e FAZ TODA A DIFERENCA

Fcmartis, se voce se preocupa com pilha, fila etc, a discussao de arraylist cai como uma luva pois eh quando linkedlist pode ser MILHOES de vezes mais rapido (sem exagero).

Att

Guilherme

gui:

LIPE:

Se for iterar pela lista, faça um favor para sua ram utilizando Iterators, e não um for … size().

Há algum artigo que me prove isso?

*não estou duvidando, apenas por aprendizado.
**eu uso for .size() :lol:

valeu! até mais… :D

Qualquer livro que ensine lista ligada e arrays, ou curso de analise de algoritmos em faculdade mostra que o tempo esperado de iteracao em:
lista ligada: O(N*N)
arraylist: O(N)

Tem o site do www.ime.usp.br/~pf com informacoes na area

Att

Guilherme Silveira

Nota importante a todos: se você tem um método que roda esporadicamente, fora de um loop, em que você precisa criar uma List e adicionar um punhado de itens, use a primeira implementação que vier à sua cabeça :mrgreen:

Parece brincadeira, mas não é. Não vai fazer como o povo que cria String com StringBuffer (e agora StringBuilder) pra concatenar duas Strings. Legibilidade sempre que possível.

Tudo isso que foi comentado aqui é realmente importante para quando você precisar de performance. Nos outros casos, seja consistente e use sempre a mesma forma de fazer as coisas, até para que alguém no futuro não pare para ler seu código e ache que tem algo relevante naquele método porque usa LinkedList ao invés de ArrayList…

boa Michael,

tentando concatenar com a sua ideia:
Se voce por algum motivo precisa escolher uma implementacao nao comum (como o caso de algoritmos especificos) por causa de performance em um caso especifico, COMENTE ou DOCUMENTE porque voce fez tal escolha…

Abraco

Guilherme

ps: tambem odeio o caso do stringbuffer em metodo bobo