Win a copy of Functional Reactive Programming this week in the Other Languages forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Iterator for ArrayList and LinkedList

 
Naresh Chaurasia
Ranch Hand
Posts: 361
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
While reading Generics and Collection, chapter7 from kathy sierra, I came across the following statement.

Keep in mind that a LinkedList may iterate more slowly than an ArrayList, but it's a good choice when you need fast insertion and deletion.

Does it mean that if i define an iterator on ArrayList and LinkedList and traverse the List using the iterator, then traversal will be faster in case of ArrayList. If "Yes", then why is it that ArrayList is faster compared to LinkedList.

Please advice
 
Rajkamal Pillai
Ranch Hand
Posts: 445
1
Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

LinkedList: Is stored in memory as a contiguous array. So the new elements added to the collection can be physically stored anywhere in memory with a pointer from the previous element in the data structure pointing to the next. This is why the iteration *could be* comparatively slower.

ArrayList: Is stored in memory as blocks. If there is no more free space available to ad another element then the whole of the collection gets copied to a new location. This is why insertion/deletion *could be* comparatively slower.

The faster/slower comparison, in IMHO, is relative to the operation being performed.

Cheers,
Raj.
 
Deepak Bala
Bartender
Posts: 6663
5
Firefox Browser Linux MyEclipse IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
LinkedList: Is stored in memory as a contiguous array


No its not. The elements are represented by an internal Entry class (very much like Map.Entry). Arrays are not involved.

ArrayList: Is stored in memory as blocks.


The internal data structure is an array, if that is what you meant.

Traversing through all the elements will always take O(N) time. Be it an ArrayList or a LinkedList.

Obtaining any particular element at a given index is another question. With an array backed ArrayList, it is as simple as returning array[index]. With the LinkedList, one has to traverse through the members using Entry.next until the element at the given index is reached. The worst case is O(N) for LinkedList, while for ArrayList the retrieval operation is always O(1).

As for insertion, LinkedList can grow its structure without copying over elements, while arrays do not have this luxury.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic