java ArrayList 的时间复杂度 [英] Time complexity for java ArrayList

问题描述

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

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

推荐答案

Java 中的 ArrayList 是由 arrayList>.

An ArrayList in Java is a List that is backed by an array.

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

The get(index) method is a constant time, O(1), operation.

ArrayList.get(index) 的直接出自 Java 库的代码:

The code straight out of the Java library for ArrayList.get(index):

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

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

Basically, it just returns a value straight out of the backing array. (RangeCheck(index)) is also constant time)

这篇关于java ArrayList 的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！