According to an accepted answer at stackoverflow, with 38 up votes
http://stackoverflow.com/questions/10656471/performance-differences-between-arraylist-and-linkedlist
LinkedList has to traverse the list from the beginning to get to the n-th element.
If that is true, I would expect, for a LinkedList, list.get(position) to take longer to return a result if position is toward the end of the list.
More specifically, suppose I have a LinkedList with BIG_NUMBER*4 elements.
The 1st quarter of that list 'Q1' consists of elements 0 up to BIG_NUMBER-1.
The 2nd quarter 'Q2' consists of elements BIG_NUMBER to 2*BIG_NUMBER-1.
and so on.
I'd expect an element in Q1 to be located faster than one in Q2.
Here, I repeat such a
test NUMBER_OF_TESTS times, keeping a running total of the times taken to find elements for each quarter.
The results I get do not show the time increase Q1<Q2<Q3<Q4 that I was expecting.
even though roughly the same number number of elements were got from each quarter.
Could anyone comment on why that is?