java - ArrayList 数据结构如何同时进行索引和动态处理？它是如何实现的？

Question

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

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

Answer 1

ArrayList 可以增长到受可用内存限制的任意大小，方法是丢弃其旧数组，分配一个全新的数组，并将旧数组中的值复制到新数组中。对于任何给定的插入，此操作可以采用 O(n)，amortized cost is O(1) .