• 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

Complexity of ArrayList and LinkedList

 
Ranch Hand
Posts: 443
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
mister krabs
Posts: 13974
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 13974
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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!
reply
    Bookmark Topic Watch Topic
  • New Topic