This week's book giveaway is in the iOS forum.We're giving away four copies of Classic Computer Science Problems in Swift and have David Kopec on-line!See this thread for details.
Win a copy of Classic Computer Science Problems in Swift this week in the iOS forum!
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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

Ranch Hand
Posts: 205
13

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: 8758
162
• 1
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: 205
13

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: 205
13
Incidentally... I can't see where the button is to flag this thread as resolved.
Thought there used to be one.

author
Sheriff
Posts: 23484
138

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