Why typical Array List implementations aren't

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

In Java ArrayDeque does not implement List. I'm not sure why it doesn't.

Answer 3

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.

Answer 4

The normal ArrayList implementation is the normal go-to collection type for code which needs simply needs something it can repeatedly add items to and then read items out from. The type offers some more abilities than that, and omitting some of those might enhance the type's functionality in the primary usage case, but the total amount of extra CPU time that would have to be spent throughout the universe if ArrayList operations were even 1% slower would be significant.

Further, it's unclear exactly how indexed accesses to a double-ended array list should behave, since there are two sensible models of behavior: it could either specify that adding or removing items from the low-numbered end should change the numbering of all existing items, or it could specify that the index of an item inserted before item 0 will be -1 (all existing indices will stay put). Adding more than 2^32 items before item 0 (while removing enough items from the other end to avoid running out of memory) will add item MIN_INT, followed by item MAX_INT, then MAX_INT-1, etc. Such an interface might be awkward in some ways, but could be very nice in others (e.g. an implementation could allow simultaneous indexed access by a writer thread and a reader thread which operate on opposite ends, since a writer who wants to manipulate element 547 wouldn't have to worry that by the time it does so the element of interest would have moved to slot #548).

There are certainly uses for various double-ended collection types, but that doesn't imply that adding double-ended features would add any value for the common usage cases.