CODEWITHSUNDEEP
javaarraylisttime-complexity
Hidayat
Hidayat

Reputation: 1005

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)?

Upvotes: 77

Views: 117664

Answers (6)

Balaji Boggaram Ramanarayan
Balaji Boggaram Ramanarayan

Reputation: 8288

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.

Upvotes: 0

prime
prime

Reputation: 15564

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)

Upvotes: 1

Kristopher Ives
Kristopher Ives

Reputation: 6025

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.

Upvotes: 12

tangens
tangens

Reputation: 39733

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.

Upvotes: 25

jjnguy
jjnguy

Reputation: 138864

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)

Upvotes: 127

Carl Smotricz
Carl Smotricz

Reputation: 67750

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

Upvotes: 5

Related Questions