• 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

LinkedList access speed

 
Ranch Hand
Posts: 209
13
VI Editor
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?



 
Saloon Keeper
Posts: 15485
363
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 209
13
VI Editor
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 209
13
VI Editor
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic