Hidayat Hidayat - 4 months ago 45
Java Question

Time complexity for java ArrayList

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

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)