wood burning stoves 2.0*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Q about ArrayList/LinkedList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Q about ArrayList/LinkedList" Watch "Q about ArrayList/LinkedList" New topic
Author

Q about ArrayList/LinkedList

Alton Hernandez
Ranch Hand

Joined: May 30, 2003
Posts: 443
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.
Thomas Paul
mister krabs
Ranch Hand

Joined: May 05, 2000
Posts: 13974
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


Associate Instructor - Hofstra University
Amazon Top 750 reviewer - Blog - Unresolved References - Book Review Blog
Alton Hernandez
Ranch Hand

Joined: May 30, 2003
Posts: 443
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
Ranch Hand

Joined: May 05, 2000
Posts: 13974
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.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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 ]

    "I'm not back." - Bill Harding, Twister
    Alton Hernandez
    Ranch Hand

    Joined: May 30, 2003
    Posts: 443
    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
    Ranch Hand

    Joined: May 05, 2000
    Posts: 13974
    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.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Q about ArrayList/LinkedList