# Complexity of ArrayList and LinkedList

Alton Hernandez
Ranch Hand
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
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).

Alton Hernandez
Ranch Hand
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
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!