Time complexity for java ArrayList

java arraylist time-complexity
Hidayat picture Hidayat · Feb 2, 2010 · Viewed 88.7k times · Source

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

jjnguy picture jjnguy · Feb 2, 2010

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)

Related questions

Time complexity of contains(Object o), in an ArrayList of Objects

As the title says, I was wondering what the time complexity of the contains() method of an ArrayList is.

Read More
Initialization of an ArrayList in one line

I wanted to create a list of options for testing purposes. At first, I did this: ArrayList<String> places = new ArrayList<String>(); places.add("Buenos Aires"); places.add("Córdoba"); places.add("La Plata"); Then, I …

Read More
Convert ArrayList<String> to String[] array

I'm working in the android environment and have tried the following code, but it doesn't seem to be working. String [] stockArr = (String[]) stock_list.toArray(); If I define as follows: String [] stockArr = {"hello", "world"}; it works. Is there something that …

Read More