• 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

iterating over a LinkedList or ArrayList

 
Ranch Hand
Posts: 1392
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have just read that a LinkedList may iterate more slowly than an ArrayList.
Aren�t they both O(1)?
 
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
According to "a programmer's guide to java",
ArrayList and Vector are constant time performance, where LinkedList is linear time. But book also says, LinkedList works better if you frequently insert and delete elements in the list.
 
Marlene Miller
Ranch Hand
Posts: 1392
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I was thinking that for both arrays and linked lists, to get to the next element is one visit, whereas in a tree, to get to the next element, you might have to visit several intermediate elements.
 
mister krabs
Posts: 13974
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The performance testing I have done has shown that LinkedList actually performs better with an iterator than ArrayList does.
http://www.javaranch.com/newsletter/June2002/newsletterjune2002.jsp#collections
In order to get the next entry in an ArrayList it is simply a matter of grabbing the next entry in the backing array. To get the next entry in a LinkedList you need to get the next pointer, use that to locate the next node on the heap, and then extract the data portion of the node. This explains why you should never use the get(index) method to iterate over a sequential list. Using get(index) in a for loop is actually better than using an iterator for an ArrayList. It is, however, a performance disaster when used on a LinkedList.
[ May 28, 2003: Message edited by: Thomas Paul ]
 
Thomas Paul
mister krabs
Posts: 13974
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I just ran a test... using a for loop with a get to iterate over an ArrayList took 15 milliseconds for an ArrayList of 100,000 entries. it took 178 seconds for a LinkedList.
 
Marlene Miller
Ranch Hand
Posts: 1392
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you Kaz and Thomas.
 
Thomas Paul
mister krabs
Posts: 13974
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
OK, so why does the iterator of a LinkedList perform better than the iterator of an ArrayList? The LinkedList uses its own ListIterator when you run iterator(). Here is the next method:

The ArrayList uses the default iterator implementation of the AbstractList. Here is that iterator's next method:

The next() method is using the get(index) method so I will include that too:

RangeCheck is interesting because it violates the Java naming standard. Other than that it is simple enough:

It appears to me that the only real difference is that the ArrayList wraps its code in a try-catch and the LinkedList doesn't. I don't see any other reason that the LinkedList should be faster using an iterator.
 
Thomas Paul
mister krabs
Posts: 13974
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I wrote my own child of ArrayList and changed the iterator to not wrap the next() implementation with a try-catch. The only real difference is that my implementation throws a IndexOutOfBoundsException if you try to do a next() after the end of the iterator while the ArrayList throws a NoSuchElementException.
The result was a savings of 25% of the time required to iterate over the ArrayList. (Realizing that the actual numbers are very tiny i.e. less than 200 milliseconds for an ArrayList containing 3 million elements).
The TomList outperformed the iterator for both the ArrayList and the LinkedList.
[ May 29, 2003: Message edited by: Thomas Paul ]
 
Marlene Miller
Ranch Hand
Posts: 1392
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you Thomas.
I don�t see any difference in the normal execution path with or without the try-catch statement.
I wonder whether the extra time is caused by the next method of the ArrayList class making two method calls (get and RangeCheck).

Method void m1()
0 aload_0
1 invokevirtual #2 <Method java.lang.Object get()>
4 astore_1
5 goto 17
8 astore_1
9 new #4 <Class java.util.NoSuchElementException>
12 dup
13 invokespecial #5 <Method java.util.NoSuchElementException()>
16 athrow
17 return
Exception table:
from to target type
0 5 8 <Class java.lang.IndexOutOfBoundsException>
Method void m2()
0 aload_0
1 invokevirtual #2 <Method java.lang.Object get()>
4 astore_1
5 return
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic