Dúvidas em List [Resolvido]

This message was edited 2 times. Last update was at 02/09/2010 15:32:40

Galera,
Li vários post aqui no guj, materiais na web e claro os livros para certificação, sei que Collections cai em muitas questões do exame, até mesmo quando é cobrado outro tópico.

Gostaria de tirar uma dúvida em relação a diferença de ArrayList e LinkedList, li sobre as desvantagens e vantagens de cada uma se tratando de inserção, exclusão e iteração.

Fiquei confuso em relação a essas vantagens

a principio(bem resumidamente) seria isso:

ArrayList: melhor para iterar
LinkedList: melhor para inserir e excluir

Acompanhei alguns post do pessoal falando, sobre diferença de performance usando iterator, for simples etc...

Enfim... fiz esse "pequeno" trecho de código para testar a performance das listas:

//imports aqui
public class Main2 {
	public static void main(String[] args) {
		List al = new ArrayList();
		List ll = new LinkedList();
			
		preencheLista(al);
		preencheLista(ll);
		
		obtemLista(al);
		//obtemLista(ll); aqui o pc até trava   EDITEI AQUI, A VARIAVEL ESTAVA ERRADA (mesmo assim trava)
		
		obtemListaIterator(al);
		obtemListaIterator(ll);
		
	}
	
	public static void preencheLista(List l) {
		long inicio = System.currentTimeMillis();
		for(int i=0;i<900000;i++) {
			l.add(i);
		}
		System.out.println("Tempo para inserir: " + (System.currentTimeMillis() - inicio));
	}
	
	public static void obtemLista(List l) {
		long inicio = System.currentTimeMillis();
		for(int i=0;i<l.size();i++) {
			l.get(i);
		}
		System.out.println("Tempo para obter usando for simples: " + (System.currentTimeMillis() - inicio));
	} 
	
	public static void obtemListaIterator(List l) {
		long inicio = System.currentTimeMillis();
		Iterator it = l.iterator();
		while(it.hasNext()) {
			it.next();
		}
		System.out.println("Tempo para obter usando Iterator: " + (System.currentTimeMillis() - inicio));
	}	
}

Conforme vocês podem notar, o código não está bem limpinho e padroes bean hehheh, mas o foco aqui é para exiber os resultados.

Por que quando eu adiciono na lista LinkedList demora mais do que no ArrayList? o certo não é inserir com mais velocidade em LinkedList?
O que fiz de errado para fazer o teste? ou o resultado seria esse mesmo?!

Aproveitando...
Quem tiver algum outro material de collections para poder compartilhar ficarei agradecido, pois estou tentano aprimorar nesse tópico, uma vez que usamos estrutura de dados o tempo todo em programas. Já li no livro da Kathy e outros livros, materias da web etc... mas que tiver algo a mais será bem vindo...

valeu.

Experimente alterar seu código para inserir e remover itens do meio da lista.
E use listas grandes.

This message was edited 1 time. Last update was at 02/09/2010 11:10:49

Vini,
Fiz os testes aqui, é impressionante a diferença da performance de ambos para executar a mesma operação.

segue o código alterado:

package Colecoes;

import java.util.*;

public class Main2 {
		
	public static void main(String[] args) {
		List al = new ArrayList();
		List ll = new LinkedList();
			
		preencheLista(al);
		preencheLista(ll);
		
		obtemLista(al);
		//obtemLista(b); aqui o pc até trava
		
		obtemListaIterator(al);
		obtemListaIterator(ll);
		
		removeItemInicioLista(al);
		removeItemInicioLista(ll);
		
		removeItemMeioLista(al);
		removeItemMeioLista(ll);
		
		preencheMeioLista(al);
		preencheMeioLista(ll);
		
	}
	
	public static void preencheLista(List l) {
		long inicio = System.currentTimeMillis();
		for(int i=0;i<900000;i++) {
			l.add(i);
		}
		System.out.println("Tempo para inserir: " + (System.currentTimeMillis() - inicio));
	}
	
	public static void preencheMeioLista(List l) {
		long inicio = System.currentTimeMillis();
		for(int i=10000;i<14000;i++) {
			l.add(i,i);
		}
		System.out.println("Tempo para inserir itens no \"meio da lista: \" " + (System.currentTimeMillis() - inicio));
	}
	
	public static void removeItemInicioLista(List l) {
		long inicio = System.currentTimeMillis();
		for(int i=0;i<4000;i++) {
			l.remove(i);
		}
		System.out.println("Tempo para remover itens do \"inicio da lista:\" " + (System.currentTimeMillis() - inicio));
	}	
	
	public static void removeItemMeioLista(List l) {
		long inicio = System.currentTimeMillis();
		for(int i=10000;i<14000;i++) {
			l.remove(i);
		}
		System.out.println("Tempo para remover itens do \"meio da lista:\" " + (System.currentTimeMillis() - inicio));
	}
	
	public static void obtemLista(List l) {
		long inicio = System.currentTimeMillis();
		for(int i=0;i<l.size();i++) {
			l.get(i);
		}
		System.out.println("Tempo para obter usando for simples: " + (System.currentTimeMillis() - inicio));
	} 
	
	public static void obtemListaIterator(List l) {
		long inicio = System.currentTimeMillis();
		Iterator it = l.iterator();
		while(it.hasNext()) {
			it.next();
		}
		System.out.println("Tempo para obter usando Iterator: " + (System.currentTimeMillis() - inicio));
	}

}

Segue minha saida:

fiz sempre na orderm: ArrayList - LinkedList

Quando digo que remove do "meio da lista" eu fui em algum lugar, que não é o meio por sinal, e comecei a remover, mas acho que já deu para notar a diferença

Tempo para inserir: 329
Tempo para inserir: 734
Tempo para obter usando for simples: 16
Tempo para obter usando Iterator: 62
Tempo para obter usando Iterator: 31
Tempo para remover itens do "inicio da lista:" 9750
Tempo para remover itens do "inicio da lista:" 78
Tempo para remover itens do "meio da lista:" 9782
Tempo para remover itens do "meio da lista:" 906
Tempo para inserir itens no "meio da lista: " 9734
Tempo para inserir itens no "meio da lista: " 532

Então posso realmente concluir isso:

ArrayList:
- mais rápido para:
--- inserir no inicio da lista
--- iterar com for simples
- mais lento para:
--- iterar usando iterator
--- remover do inicio da lista
--- remover do meio da lista
--- inserir no meio da lista

LinkedList:
O contrário de ArrayList

uma observação: usando a mesma quantidade de itens, o for simples até trava usando linkedlist?? é bem menos eficaz mesmo?

Depois vou melhorar esse código hehehhe, sei que tem algumas coisas bagunçadas ai...hheh

valeu.

desculpe mais um edit
EDIT: só reforçar que não inclui o mesmo tanto de intens no inicio e meio da lista. mas as comparações entre lista são com números iguais de itens.

This message was edited 1 time. Last update was at 02/09/2010 11:46:16

O get(i) do LinkedList é extremamente ineficiente.

O linked list é uma lista encadeada. Então não existe acesso direto a índice. Quando você faz um get(30), ele vai até a cabeça da lista, e salta elemento a elemento, até chegar no trigésimo.

Por isso o ideal é usar o iterator ou o for each, caso você vá percorrer uma lista dessas. E ela é pouquíssimo indicada se você for fazer muito acesso direto.

Existe também uma diferença em relação a memória. O LinkedList tem um overhead de 4 bytes para cada item inserido na lista. Contra apenas 4 bytes para a lista toda, do ArrayList.

This message was edited 1 time. Last update was at 02/09/2010 11:53:19

A iteração com iterator também será mais rápida no ArrayList. A diferença que você obteve foi muito pequena, provavelmente deve-se a alguma distorção externa.

Isso pq o ArrayList tem os elementos colocados sequencialmente na memória, enquanto o LinkedList os tem espalhados. Mas, de acordo com a ergonomia da JVM, e pelo fato de objetos sempre estarem no heap, a diferença é muito pequena para que seja significativa, daí os 30ms a mais no ArrayList.

Então você pode considerar o resultado igual para as duas listas.

This message was edited 2 times. Last update was at 02/09/2010 11:55:46

O arrayList é uma lista sequencial, baseada num vetor.

Para inserir ou remover elementos do meio de um vetor, ele é obrigado a copiar todos os elementos posteriores ao removido para um índice a menos.

Exemplo, se você tem o vetor
a = {1,2,3,4,5};

E vai remover o elemento 2, você deve copiar o 3 para a posição do 2, o 4 para a do 3 e assim por diante, até ter um array assim:

a = {1,3,4,5,5};

E então guardar em algum lugar que o tamanho da sua lista agora é 4 (embora ainda hajam 5 posições de memória reservadas para essa lista).

Valeu Vini.
Essa é uma questão bem importante no desenvolvimento de um software, quase sempre usamos estruturas de dados e saber qual escolher em determinados casos é fundamental.

Explicação nota 10! Agora deu para clarear a mente em relação ao assunto, me fez lembrar algoritmos 2

(disciplina do curso de CSI) hehhhehe.

Valeu mesmo.

Agora é só estudar o CopyOnWriteArrayList, o TreeSet, o HashSet, o CopyOnWriteArraySet, o TreeMap, o HashMap, o ConcurrentHashMap, a ConcurrentLinkedQueue, a DelayQueue, a SynchronousQueue, a PriorityBlockingQueue, a ArrayBlockingQueue, a LinkedBlockinQueue, o EnumSet e o EnumMap para terminar o estudo das collections concretas padrão.

GUJ Master Membro desde: 23/08/2009 13:14:01 Mensagens: 1924 Offline

ViniGodoy wrote:Agora é só estudar o CopyOnWriteArrayList, o TreeSet, o HashSet, o CopyOnWriteArraySet, o TreeMap, o HashMap, o ConcurrentHashMap, a ConcurrentLinkedQueue, a DelayQueue, a SynchronousQueue, a PriorityBlockingQueue, a ArrayBlockingQueue, a LinkedBlockinQueue, o EnumSet e o EnumMap para terminar o estudo das collections concretas padrão.

kkkkkk

Agora é só estudar o CopyOnWriteArrayList, o TreeSet, o HashSet, o CopyOnWriteArraySet, o TreeMap, o HashMap, o ConcurrentHashMap, a ConcurrentLinkedQueue, a DelayQueue, a SynchronousQueue, a PriorityBlockingQueue, a ArrayBlockingQueue, a LinkedBlockinQueue, o EnumSet e o EnumMap para terminar o estudo das collections concretas padrão.

huahuuahuuahua... nem sabia da existência de algumas dessas.... rsrsrsrsrs.
afff......

Notícias, artigos e o maior fórum brasileiro sobre Java