• 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

Q about ArrayList/LinkedList

 
Ranch Hand
Posts: 443
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Is this statement correct?


Iteration over a LinkedList is faster than an ArrayList


One of the mock exam said that it is, but I doubt it. In an array, you are just traversing consecutive memory location. In a LinkedList, you have to first determine the address of the next or previous element, and then go to that location, which may not be close to your current element.
 
mister krabs
Posts: 13974
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, iterating over a LinkedList is faster than iterating over an ArrayList. My article on List classes has a comparison:
http://www.javaranch.com/newsletter/June2002/newsletterjune2002.jsp#collections
 
Alton Hernandez
Ranch Hand
Posts: 443
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Thomas
Actually, I had read your article before. But I don't find any explanation as to why LinkedList is faster than ArrayList when it comes to iteration.
Comparing the two methods get() of ArrayList and next() of LinkedList, it seems that get() is faster and simplier.
 
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
But the iterator for LinkedList doesn't use the get() method. The iterator next() method is actually fairly simple for both LinkedList and ArrayList. The only difference is that the LinkedList has the address of the next entry while the ArrayList has an offset from an address. That makes the LinkedList slightly faster.
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Comparing the two methods get() of ArrayList and next() of LinkedList, it seems that get() is faster and simplier.
Adding to Thomas's answer: here's a typical ranking of the speeds of these methods:
  • ArrayList's get()
  • LinkedList's Iterator's hasNext() + next()
  • ArrayList's Iterator's hasNext() + next()
  • LinkedList's get()

  • The thing to realize here is that the relative differences between the first three just aren't that big most of the time, and the time required is roughly proprtional to the size of the collection - as you'd expect, you can't really get better than O(n) performance for looping though an entire collection.
    By contrast, LinkedList's get() can be much, MUCH worse than Tom's statistics show, as it's ultimately an O(n^2) to loop through the whole list. Here are some results I got for various collection sizes:

    Note that my results are a bit different from Tom's. The difference between iterating a LinkedList and doing get() on an ArrayList doesn't really show a clear winner - maybe the ArrayList get() is faster on average, but not by much, and not always. And the ArrayList iteration is only a little slower. It's the LinkedList get() that stands out. ("********" means "Jim got tired of waiting".) It doesn't really matter much which of the other three you use, as long as you never use LinkedList's get() on any sizable collection.
    Looking at Tom's results, I'm not sure why there isn't a bigger difference shown for LinkedList's get(). My guess is that when he says 50000 repetitions, the collection size is much much smaller - he just repeats the test 50000 times to (hopefully) eliminate JIT startup effects and other sources of error. In contrast, where I say size = 40000, that's a collection with 40000 elements, which I iterate through exactly once. My results were obtained using J2SDK 1.4.2 on a 500 MHz P3 with way to much memory for a processor from the previous milennium. Here's the code (just change which lines are commented out):

    Note that the sum variable is just there to ensure that the JIT can't optimize all the calls out of existence (since otherwise they don't really do anything). Though you can comment it out with relatively little effect it seems. It adds a bit to the total time for each of this methods, but does little to the relative standings, as each test has that same overhead...
    [ August 17, 2003: Message edited by: Jim Yingst ]
     
    Alton Hernandez
    Ranch Hand
    Posts: 443
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hi all,


    Originally posted by Jim Yingst:

    Adding to Thomas's answer: here's a typical ranking of the speeds of these methods:
    1. ArrayList's get()
    2. LinkedList's Iterator's hasNext() + next()
    3. ArrayList's Iterator's hasNext() + next()
    4. LinkedList's get()


    Looking closely at the codes, I noticed that the iterator of the ArrayList is inherited from the AbstractList. The iterator() method in the AbstractList returns an inner class called Itr. Inside this inner class, the methods hasNext() and next() are defined.
    What the next() method in this inner class does is simply call the get() method of the ArrayList.

    Now compare that with LinkedList's next() method:

    So if the ArrayList's get() is faster than LinkedList's hasNext()+next(), then ArrayList's hasNext()+next() should be faster than LinkedList's as well.
    Is it possible that the try/catch clause in the AbstractList is causing the ArrayList next() method to be slower? Or is it because the next() method of the ArrayList has to invoked another method (which is the get() method)?
    [ August 17, 2003: Message edited by: Alton Hernandez ]
     
    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 recall having this discussion in the Performance forum (which is where it really belongs) and the answer was that the try-catch overhead was the major cause of the performance hit.
    reply
      Bookmark Topic Watch Topic
    • New Topic