Why a ArrayList get operation is constant time

Question

Based on this answer here

I could not understand why ArrayList get(n) is O(1)? If I want the last element of an ArrayList, I need to traverse the list from beginning to end which is proportional to the size of list i.e. O(n).

Where am I going wrong?

Answer 1

No. If you know what element you want, you can get it by lookup

int a[] = new int[100];
int i = a[100]; // Will be as fast as
int j = a[0];

And the ArrayList is backed by an array.

The array is a series of elements stored in sequence in the memory, and the array starts at a known point int he memory. Getting a certain element is a simple matter of adding the position you need to the start address.

If the start address for the a-array is n, then the first element will be at n+0 and the hundreth element will reside at address n+100. There is no need for iterating through the elements up to the one you are looking for.

In C this means that if

int a[] = {1,5,7,2};
int *p = a;

if (a[2] == *(p+2)) {
    // a lookup is a simple addition of the address
}