java - java ArrayList 的时间复杂度

Question

ArrayList是java中的数组还是列表？ get操作的时间复杂度是多少，是O(n)还是O(1)？

Answer 1

Java 中的 ArrayList 是由 array 支持的 List。

get(index)方法是一个常数时间，O(1)，操作。

ArrayList.get(index)的Java库代码:

public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
}

基本上，它只是直接从后备数组中返回一个值。 (RangeCheck(index)) 也是常数时间)