This week's book giveaway is in the Performance forum.
We're giving away four copies of The Java Performance Companion and have Charlie Hunt, Monica Beckwith, Poonam Parhar, & Bengt Rutisson on-line!
See this thread for details.
Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Complexity of ArrayList and LinkedList

 
Alton Hernandez
Ranch Hand
Posts: 443
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
Why is it that the complexity of getting an element at a some location for ArrayList is O(1), while for a LinkedList it's O(i)? The get method of these 2 classes uses an index to locate an element. So I expect that they will traverse the list in the same way. Is ArrayList doing something different from LinkedList when getting an element?
Thanks.
Al
 
Thomas Paul
mister krabs
Ranch Hand
Posts: 13974
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
An ArrayList is built in consecutive memory. Since each slot has the same length, the position of a particular slot can be calculated by multiplying the size of a slot by the position in the ArrayList you are looking for.
You can't do this with a LinkedList because items in a LinkedList are not in consecutive memory. The address of the next slot is held in the current slot. In order to find the third item you must physically go to the first item to get the address of the second item and then go to that item to get the address of the third item.
That is why performance of a get in an ArrayList is O(1) while performance of a get in a LinkedList is O(n).
 
Alton Hernandez
Ranch Hand
Posts: 443
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Thomas
I guess the key word here is consecutive memory. This is probably why the ArrayList has to shift its elements up or down whenever there is an addition or deletion of element in order to keep them in consecutive location.
 
Thomas Paul
mister krabs
Ranch Hand
Posts: 13974
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Alton Hernandez:
This is probably why the ArrayList has to shift its elements up or down whenever there is an addition or deletion of element in order to keep them in consecutive location.
Exactly!
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic