4

我相信 LinkedLists 和 ArrayLists 之间是有区别的。ArrayLists 只不过是动态数组。所以我假设 ArrayLists 存储在连续位置的堆中（这就是它们具有 O(1) get 方法的原因）。问题是，如果堆中存储的另一个对象会阻止 ArrayList 增长怎么办？在这种情况下如何实施？如果 ArrayList 的剩余部分存储在堆的其他非 conrigous 区域中，则 get 方法不会是 O(1)。

例如，假设在内存位置 10 中有一个对象。之后，在内存位置 5 处创建一个 ArrayList。为简单起见，假设数组列表中的每个元素只有一个字节。这意味着 ArrayList 只能增长到 5 个元素。

4

5 回答 5

4

ArrayList可以通过丢弃其旧数组、分配一个全新的数组并将值从旧数组复制到新数组来增长到受可用内存限制的任何大小。O(n)对于任何给定的插入，此操作都可以进行，摊销成本为O(1)。

于 2012-09-17T17:10:25.597 回答
2

所以我假设 ArrayLists 存储在连续位置的堆中

通常是这种情况，但没有什么能阻止 JVM 做一些不同的事情（JVM 规范中没有规定数组必须存储在连续的块中）。

另请参阅此相关帖子。

如果堆中存储的另一个对象会阻止 ArrayList 增长怎么办？

arraylist 对象将要求 JVM 给它更多空间，JVM 将根据需要分配这些空间（如果不能，则抛出 OutOfMemoryException）。

于 2012-09-17T17:08:43.173 回答
1

查看源代码（感谢@GilbertoGaxiola），初始 ArrayList 创建了一个大小为 10 的 object[]。由于它需要更多空间，它将大小加倍并将旧数组的内容复制到新数组中。在这个数组变大之前不需要很多次填充，这使得它成为一个很好的实现。

于 2012-09-17T17:14:17.090 回答
1

所以我假设 ArrayLists 存储在连续位置的堆中（这就是它们具有 O(1) get 方法的原因）。

所有其他答案都是正确的，但我想解决您在这里所做的错误假设：

ArrayList.get()是 O(1) 不是因为数组如何存储在内存中，而是因为元素访问的成本是恒定的，并且与 ArrayList 中的元素数量不成比例。

这里的 O(1) 并不意味着可以在单个操作中完成查找 - 这意味着复杂度相对于后备数组的大小是恒定的。

当您调用ArrayList.get(i)JVM 时，仍然需要将数组索引转换为虚拟内存地址，这涉及到您的操作系统将地址转换为真实地址 - 但它是 O(1)，因为如果数组有 1 个元素或 5000 个元素，复杂性是相同的.

相比之下，LinkedList.get(i)不是 O(1)，因为 LinkedList 类需要遍历每个节点，直到找到节点i- 复杂度与列表的整体大小和 的大小成正比i。

数组存储在连续位置的假设也是不正确的。

于 2012-09-17T17:24:03.413 回答
0

最后的解释是绝对正确的。操作系统必须最终将索引转换为真实地址。因此，所有索引的翻译时间都是恒定的。关于存储，最后一个解释是正确的，如果您必须存储更多元素，则大小只会翻倍。

于 2014-02-08T07:07:35.390 回答