• Post Reply Bookmark Topic Watch Topic
  • New Topic

LinkedList access speed  RSS feed

 
Richard Hayward
Ranch Hand
Posts: 182
11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?



 
Stephan van Hulst
Saloon Keeper
Posts: 7932
143
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
LinkedList is actually a doubly linked list. That means that it can do lookups starting at both ends of the list, meaning it takes longer to find elements in the middle.
 
Richard Hayward
Ranch Hand
Posts: 182
11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:LinkedList is actually a doubly linked list. That means that it can do lookups starting at both ends of the list, meaning it takes longer to find elements in the middle.


Ah, thanks Stephan.

I've adjusted my code a bit to divide the list into 5 equal parts.
As you say,  finding elements in the middle of the list clearly takes longest.




 
Richard Hayward
Ranch Hand
Posts: 182
11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Incidentally... I can't see where the button is to flag this thread as resolved.
Thought there used to be one.
 
Henry Wong
author
Sheriff
Posts: 23291
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Richard Hayward wrote:Incidentally... I can't see where the button is to flag this thread as resolved.
Thought there used to be one.


This topic has already been marked as resolved.

Also, thanks for providing the code, along with the results. You definitely earned a cow.

Henry
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!