arraylist - ArrayList の取得操作が一定時間である理由

Question

この回答に基づいてここ

なぜ ArrayList get(n) が O(1) なのか理解できませんでしたか? ArrayList の最後の要素が必要な場合は、リストを最初から最後までトラバースする必要があります。これは、リストのサイズ、つまり O(n) に比例します。

どこが間違っていますか？

Answer 1

いいえ。必要な要素がわかっている場合は、ルックアップで取得できます

int a[] = new int[100];
int i = a[100]; // Will be as fast as
int j = a[0];

そして、ArrayList は配列によって支えられています。

配列は、メモリに順番に格納された一連の要素であり、配列はメモリ内の既知のポイントから始まります。特定の要素を取得するには、開始アドレスに必要な位置を追加するだけです。

a-arrayの開始アドレスが の場合n、最初の要素は にn+0あり、100 番目の要素は アドレス にありますn+100。探している要素まで要素を反復処理する必要はありません。

C では、これは次のことを意味します。

int a[] = {1,5,7,2};
int *p = a;

if (a[2] == *(p+2)) {
    // a lookup is a simple addition of the address
}