arraylist - 为什么 ArrayList get 操作是常数时间

Question

基于这个答案here

我不明白为什么 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，那么第一个元素将是 atn+0并且第 10 个元素将驻留在 address 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
}