Saa*_*adH 2 java arraylist time-complexity
对于特定类型的ArrayList,我们可以在ArrayList中找到对象(特定类型的)的大小,并直接在O(1)中的任何索引处访问该对象.这是因为对象引用存储在ArrayList中的连续内存块中,因此通过跳过object_size * index内存位置,我们访问所需对象的引用所在的内存位置.
然而,在LinkedList中,我们必须遍历每个对象,直到我们到达所需的对象.
对于包含不同类型对象(具有不同大小)的通用ArrayList,是get(index i)在O(1)中完成的吗？如果是这样,怎么样？
你是在误解下工作的.对象不存储在数组中,只有对象的引用(即指针)存储在数组中.对象本身就在堆上.因此,在ArrayList索引中查找特定对象将始终O(1)与其包含的内容无关,并且a LinkedList将是O(n).
| 归档时间： |
|
| 查看次数： |
67 次 |
| 最近记录： |