javaのArrayListの時間計算量

質問

質問 ArrayList は配列ですか、それともリストですか？ get操作の時間的複雑さはどの程度ですか？ O(n) それとも O(1) ?

どのように解決するのですか？

以下の通りです。 ArrayList は、Javaでは List であり、そのバックには array .

は get(index) メソッドは一定時間 O(1) の、操作です。

のための Java ライブラリから直接出力されるコードは ArrayList.get(index) :

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

基本的には、バックアレーからそのままの値を返すだけです。( RangeCheck(index) ) も定数時間)