java - Java 的 ArrayList/Scala 的 ArrayBuffer 可能有改进吗？

Question

目前，“增长”算法发现支持 ArrayList/ArrayBuffer 的 Array 对于请求的操作来说太小，并进行复制将内容移动到更大数组的开头。

jsuereth在 this thread 的评论中解释得很好:

ArrayBuffer is great for append but not as good for prepend. Java's ArrayList will actually try to amortize costs to prepend as well, making it slightly better in my opinion. Yes ArrayBuffer is probably good enough if you're just appending on to a list and indexing elements.

假设该操作将来可能会被更频繁地调用，使旧内容的位置取决于最后一个操作，这不是一个很好的增强吗？

我。例如:

• 如果append需要更大的数组，请将现有内容复制到新数组的前面:

  [x|x|x|x|x|x] 
         |
         v
  [x|x|x|x|x|x| | | | | ]
  

• 如果prepend需要更大的数组，请将现有内容复制到新数组的后面:

  [x|x|x|x|x|x] 
         |
         v
  [ | | | | |x|x|x|x|x|x]
  

这会解决前置的性能问题，同时通常会使算法更适应使用模式吗？ (最坏的情况是附加/前置大的东西......)

是否有任何其他数据结构在增长底层结构时已经考虑了最后一个操作？

Answer 1

也许您需要的是 ArrayDeque。追加和前置的操作时间复杂度为 O(1)(除非容量发生更改)

它有一个数组，其中有一个指向 head 和 tail 的索引，允许它写入开始或结束位置，而不必向下洗牌所有条目/向上。