Why typical Array List implementations aren't double-ended?

Question

Why aren't ArrayLists generally implemented to be double-ended, which would support fast amortized insertion in the front as well as the back?

Is there ever a disadvantage to using the latter over the former?

(I'm not talking just about Java -- I haven't seen double-ended array lists being the default in any other language, but Java was just a good example here.)

---

*Edit: I originally called them "array deques" but that was a misunderstanding on my part; I wasn't talking about queues, but double-ended array lists.

Answer 1

An ArrayList is simple; entries start at 0, and you can add stuff at the end (which might lengthen the array), but entry #X in the list is always backing_array[X].

An ArrayDeque would be more complex; besides having to keep track of the start of the sequence (because it'd no longer be guaranteed to start at 0, unless you want O(N) shifts/unshifts), you'd also have to worry about the other end being "empty". That extra complexity comes at a cost; in the more common case (lists), the RTL would still have to do all the checks and index math necessary in a deque, slowing down the app for no real reason. Entry #X becomes backing_array[start+X], and bounds checks have extra math to them as well.

So unless you have a real need for deque functionality, it's simpler and more efficient to stick with a list, at least when you're messing with arrays.

Answer 2

A deque is used just when you want to access data in a FIFO or LIFO way, their common interface neither provide a way to obtain n-th element, you should do it by hand, and infact if you take a look at the Java Deque here, you understand that there is no n-th method provided. This should be enough to avoid its usage when you need to index any group of data.

Ok, you can implement as an array deque instead that a normal array but this adds features that should be considered just when you need them, not by default. Otherwise you could justify using a more complex data structure for simple problems just because you can.

IMHO it's also a matter of synergy between arrays nowadays and how they were implemented/managed when you wrote code nearer to the machine.