当您在列表的开头或中间插入 ArrayList 时，您始终会获得 O(n) 的性能，但在末尾插入能够保持 O(1)，因为您只是将其添加到列表的末尾。
我对如何在开头 O(1) 处进行插入以及如何在 O(n) 处平均插入 O(n/2) 有一个高层次的想法，但我不确定底层数组结构是否可行。
我的想法
既然 ArrayList 实际上只是一个更大的数组，当它达到阈值时，它会“调整”自身的大小，为什么它不能在列表的前面和末尾都调整自己的大小，而不是只在末尾调整自己的大小？这将允许开头的插入为 O(1)，同时还允许您重写中间的插入以采用最短路线插入自身。 (例如，如果您在索引 1 处插入，则将 0 移过来比将 2 移至 n 更容易)。
我认为 Sun 最初不这样做的原因是因为 Arrays.copyOf 和扩展 System.arrayCopy 的写入方式。两者都从列表的开头开始并复制到更大的数组中。我已经查看了这两种方法的 Sun 源代码，但它对我的 Java 技能水平来说有点高级。
问题
在我看来，这是否有效有两个主要问题:
1) 首先，是否可以重写/重载 Arrays.copyOf 或 System.arrayCopy 以将子数组插入到较大数组的中间？
2)这样做会产生什么 Big O 后果？
那么这是一个好主意，还是我错过了一些明显的东西，导致这无法实现？
提前致谢!
最佳答案
您的想法完全可行，并且对于双端队列实现来说很有意义，其中常见的情况是在两端添加和删除元素。对于 ArrayList 来说没有多大意义，因为它 99% 的用例都只会添加到末尾。
至于您对System.arraycopy本质的疑问，我不确定我是否完全理解您
a) 是的，您可以使用arraycopy用另一个数组的内容覆盖一个数组的中间，并且
b) arraycopy 不会插入到数组中，因为该操作对 Java 的固定大小数组没有意义。
最接近“插入数组”的想法是创建一个全新的、更大的数组，并从两个输入数组中arraycopy适当的范围。由此产生的性能是您可以获得的最佳性能。
关于java - 构建更好的 ArrayList，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19893570/