Possible improvements to Java's ArrayList/Scala's ArrayBuffer?

Currently, the "growing" algorithm figures out that the Array backing the ArrayList/ArrayBuffer is too small for the requested operation and copies the contents to the beginning of a larger array.

jsuereth explains it very well in the comments of this thread:

ArrayBuffer is great for append but not as good for prepe开发者_如何学编程nd. 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.

Wouldn't it be a good enhancement to make the location of the old contents depend on the last operation, based on the assumption that this operation might be called more often in the future?

I. e.:

• if append needs a larger array, copy the existing contents to the front of the new array:

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

• if prepend needs a larger array, copy the existing contents to the back of the new array:

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

Will this solve the performance problems for prepend, while generally making the algorithm a bit more adaptive to usage patterns? (Worst case would be alternatively appending/prepending large stuff ...)

Are there any other data structures which already take the last operation into account when growing the underlying structure?

---

Perhaps what you need is ArrayDeque. This has an O(1) operation for append and prepend (unless the capacity is changed)

This has an array where it has a index to the head and tail which allows it to write the start or end position without having to shuffle all the entries down/up.

---

In the general sense, MOST pre-defined structures and algorithms are based on some assumption of the most common use-cases. As it's impossible to create a "general" implementation that covers every possible scenario, there will always be some outside cases where the approach is less than optimal.

If your particular use-case is performance-critical enough that this is a problem, my suggestion is to create your own Array implementation, tailored to your usage. Beware the sub-optimization devil though. Rarely it's actually worth the increased cost of maintenance to save those few odd CPU cycles or bytes of memory.

---

You can use ArrayDeque for an array-backed data structure with fast prepend.

---

If you're not going to do a lot of lookups, and just be doing linear traversals, then go for the UnrolledBuffer - an unrolled linked list implementation. Otherwise, a Vector and its +: should be an efficient choice.