Java 数组列表的时间复杂度

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.

To be pedantic, it's a List backed by an array. And yes, the time complexity for get() is O(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)

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.

在实践中，经过几次添加后，一切都是O（1），因为每次容量耗尽时，支持数组都会加倍。因此，如果阵列从16开始，变满，则重新分配到32，然后是64，128，依此类推。所以它可以正常扩展，但GC可能会在大的重新分配期间出现。

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)

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.