GeeCON Prague 2014*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Complexity of ArrayList and LinkedList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Complexity of ArrayList and LinkedList" Watch "Complexity of ArrayList and LinkedList" New topic
Author

Complexity of ArrayList and LinkedList

Alton Hernandez
Ranch Hand

Joined: May 30, 2003
Posts: 443
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

Joined: May 05, 2000
Posts: 13974
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).


Associate Instructor - Hofstra University
Amazon Top 750 reviewer - Blog - Unresolved References - Book Review Blog
Alton Hernandez
Ranch Hand

Joined: May 30, 2003
Posts: 443
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

Joined: May 05, 2000
Posts: 13974
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!
 
GeeCON Prague 2014
 
subject: Complexity of ArrayList and LinkedList