• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Iterator for ArrayList and LinkedList

 
Ranch Hand
Posts: 361
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Ranch Hand
Posts: 479
1
IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Bartender
Posts: 6663
5
MyEclipse IDE Firefox Browser Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
reply
    Bookmark Topic Watch Topic
  • New Topic