bom dia pessoal sei que uma lista encadeada tem uma referencia ao proxximo item… e uma duplamente tem ao proxximo e ao anterior …
sei que sao mais rapidas na iteraçao do que uma lista normal…
mais nao achei explicaçao sobre o que eu gostaria de enteder que no caso é como essas referencias influem na velocidade… o porque as encadeadas iterao mais rapido que as nao encadeadas… se as duas tem verificar se existe o proxximo registro pois se a encadeada nao o fizesse estaria a merce de um null pointer…
Se for no Java, isso não procede usando as classes da jre. List é uma interface, e LinkedList é uma classe, se faz estranha a comparação de performance entre elas. :roll:
M
maquiavelbona
Caso a preocupação seja entre ArrayList e LinkedList, é a implementação, como visto na documentação:
LinkedList:
Linked list implementation of the List interface. Implements all optional list operations, and permits all elements (including null). In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue.
The class implements the Deque interface, providing first-in-first-out queue operations for add, poll, along with other stack and deque operations.
All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.
ArrayList:
Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.
An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.
Até!
F
FernandoCartaxo
em termos de peformance, a LinkedList é mais lento que o ArrayList
M
maquiavelbona
E existe um motivo bem claro ( para quem tem preguiça de ler o texto acima). LinkedList é realmente um objeto apontando para o outro, todos os métodos de busca e remoção gastam no mínimo O(N), inserção é O(1). ArrayList na verdade é um array de tamanho X(que você desconhece) que caso ele precise de mais espaço, ele fica do tamanho X+K(que você também desconhece) e ele encobre todos os métodos para parecer uma lista. Qual a vantagem de um em relação ao outro? LinkedList garante a ordem de inserção dos elementos (já que ele implementa Deque, a ordem é importante) coisa que a ArrayList não se preocupa em fazer. ArrayList é mais rápida na maior parte das operações pois na verdade é um array escondido.
Até!
D
Diabo_Loiro
mais array list tambem mantem a ordem de inserçao… questao era que a linkedlist seria uma implementaçao de lista encadeada… e qual era a vantagem sobre array list.
no se tu colocar 1,2,3 no arraylist ele vai estar nessa ordem…
me disserao que a iteraçao do linkedlist era mais rapida do que a do arraylist
mais pela sua explicaçao maqui… acho que deu para ter uma ideia…
M
maquiavelbona
Relendo a documentação e alguns artigos, sim a ArrayList preserva a ordem (sempre insere no final). A LinkedList tem como vantagem também você poder inserir tanto no começo quanto no final.
Até!
D
Diabo_Loiro
cara e o medodo add(obj,index)
adiciona na posiçao que tu quiser inclusive na 0 que é o começo
entao ainda fica a duvida?
B
BoogieMan
As principais diferenças entre ArrayList e LinkedList, no uso prático, são:
A iteração e acesso aleatório a elementos são mais rápidos em ArrayLists;
A inserção e remoção de elementos em posições aleatórias são mais rápidas em LinkedLists.
Além disso, LinkedList implementa a interface Queue (e Deque), então você pode usar um LinkedList como uma Fila.
M
maquiavelbona
BoogieMan:
…
A iteração e acesso aleatório a elementos são mais rápidos em ArrayLists;
Não faz sentido a afirmação que a iteração da ArrayList é mais rápida do que a da LinkedList se você não dizer que a ArrayList também devolve o ListIterator, que é o mesmo tipo de Iterator da LinkedList. Mas sim, a implementação da ArrayList para Iterator é mais direta, trabalhando simplesmente com um contador da posição atual do iterador.
BoogieMan:
…
A inserção e remoção de elementos em posições aleatórias são mais rápidas em LinkedLists.
[/quote]
Outra afirmação que não faz sentido, dado as implementações. Numa LinkedList para inserir ele precisa chegar na posição (que pode demorar O(N), na verdade demora no máximo O(N/2)) e depois O(1) para colocar o objeto. No caso da ArrayList para se inserir numa posição aleatória, a busca é O(1) e o redimensionamento é O(N-índice). No caso médio, a implementação da ArrayList é mais lenta ( por causa do System.arraycopy ), mas não é caso geral.
BoogieMan:
…
Além disso, LinkedList implementa a interface Queue (e Deque), então você pode usar um LinkedList como uma Fila.
Isso é muito útil, mas poucos fazem uso disso.
Até!
B
BoogieMan
Olá maquiavelbona, tudo bem? Aproveitando que estamos neste assunto, estou estudando para a SCJP pelo livro da Kathy Sierra, e na parte de Collections diz que estas implementações de listas (ArrayList e LinkedList) diferem basicamente por estes aspectos que citei anteriormente. Ainda conheço não tenho pleno conhecimento de como funcionam estas estruturas de dados, e da notação Big O (estou aprendendo na faculdade).
Deixe-me ver se entendi direito:
Na inserção e remoção, em um ArrayList a busca pela posição é geralmente mais rápida (por ser constante), mas a velocidade do redimensionamento do array vai depender da posição (quanto mais no começo do array, mais lento)?
Na LinkedList, a busca pela posição deverá ser geralmente mais lenta (e não constante), e a inserção e remoção devem ser mais rápidas (por serem constantes)?
E no caso da iteração, a iteração em um ArrayList é mais rápida por causa da implementação de seu iterador?
Se você puder me esclarecer agradeço!
M
maquiavelbona
BoogieMan:
…
Na inserção e remoção, em um ArrayList a busca pela posição é geralmente mais rápida (por ser constante), mas a velocidade do redimensionamento do array vai depender da posição (quanto mais no começo do array, mais lento)?
Na LinkedList, a busca pela posição deverá ser geralmente mais lenta (e não constante), e a inserção e remoção devem ser mais rápidas (por serem constantes)?
Exatamente. Para fazer a busca pela posição numa ArrayList, ele simplesmente acessa o elemento do array implementado internamente(portanto gasta um tempo constante), enquanto LinkedList percorre andando do começo ou do final até o X-ésimo elemento, o que for mais rápido. Agora para inserir ou remover, a ArrayList precisa necessáriamente copiar o trecho do X-ésimo elemento até o final quando inserido ou removido na posição X, na LinkedList é só modificado o tamanho e as referencias.
BoogieMan:
…
E no caso da iteração, a iteração em um ArrayList é mais rápida por causa da implementação de seu iterador?
Se você puder me esclarecer agradeço!
A implementação de Iterator da ArrayList é bem simples, enquanto contador < tamanho do ArrayList, pegue o próximo e adicione 1 ao contador. Simples rápido e direto. Já na LinkedList é retornado um ListIterator, que é uma lista unidirecional e para isso é preciso construir a lista e a ArrayList tem essa mesma implementação, mas não é padrão receber esse iterador.
