Time complexity for java ArrayList

Question

Is ArrayList an array or a list in java? what is the time complexity for the get operation, is it O(n) or O(1)?

Answer 1

An ArrayList in Java is a List that is backed by an array.

The get(index) method is a constant time, O(1), operation.

The code straight out of the Java library for ArrayList.get(index):

public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
}

Basically, it just returns a value straight out of the backing array. (RangeCheck(index)) is also constant time)

Answer 2

It's implementation is done with an array and the get operation is O(1).

javadoc says:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

Answer 3

As everyone has already pointed out, read operations are constant time - O(1) but write operations have the potential to run out of space in the backing array, re-allocation, and a copy - so that runs in O(n) time, as the doc says:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

In practice everything is O(1) after a few adds, since the backing array is doubled each time it's capacity is exhausted. So if the array starts at 16, gets full, it's reallocated to 32, then 64, 128, etc. so it scales okay, but GC can hit up during a big realloc.

Answer 4

To be pedantic, it's a List backed by an array. And yes, the time complexity for get() is O(1).

Answer 5

Just a Note.

The get(index) method is a constant time, O(1)

But that's the case if we know the index. If we try to get the index using indexOf(something), that will cost O(n)

Answer 6

The arraylist is basically an implementation of array. so the time complexity of the CRUD operations on it would be :

get/read :  O(1) since you can seek the address directly from base

remove/delete : O(n) why ? Because once we delete the element at index, then we need to move the after values one by one to the left. 

add : O(1) becuase you always add the end of the array - next free address available.

update : O(1) since you are just changing the value but nothing value moving....across the array.