6

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.

Improve this question
12
  • Java doesn't have random access in its ArrayDeque class. Commented May 27, 2011 at 3:54
  • If you implement arrays as deques you have to either allocate extra space on both ends (costs memory), or implement a circular buffer and need to check for wraparound when accessing elements (costs performance). Since using it as a deque is not what it's for I guess they considered it not worth the price. Commented May 27, 2011 at 4:00
  • @sverre: A single if isn't really a perf hit, is it? That's not too convincing for me. :\ Commented May 27, 2011 at 4:02
  • @sverre: I'm not sure I agree with the performance on access of elements. But the code to increase capacity would be slightly more complex and the ArrayDeque may take multiple arraycopy operations. An ArrayList would only need a single arraycopy operation. Still not much difference I would think. Commented May 27, 2011 at 4:22
  • I agree with @sverre. It might not seem like much of a performance hit when you look at the operations in isolation but you'll notice it if you try to run a complex algorithm on a large dataset. @Mehrdad Try not to think of ArrayList as the 'default'. By providing multiple List implementations they give you the choice to use something more suited to your purpose. If you don't require more functionality than the ArrayList provides why would you want to use a more complex data structure? Commented May 27, 2011 at 4:36

4 Answers 4

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Is that single load + addition operation really an even measurable performance hit?
Not if you're doing it once. In a tight loop, though, it could add up. (BTW this is just some mythical way i'd do a deque; it's not necessarily how the Java people would do it.) And if you don't have to do it, why do it at all? Why add complexity when most people will never need it?
1

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.

Improve this answer

Comments

0

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

Improve this answer

1 Comment

Because it is not intended for random access ( get(int) ).
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.