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

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 2

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

Answer 3

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 4

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.