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.

user541686
  • 205,094
  • 128
  • 528
  • 886
  • Java doesn't have random access in its `ArrayDeque` class. – Gabe May 27 '11 at 03: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. – sverre May 27 '11 at 04:00
  • @sverre: A single `if` isn't really a perf hit, is it? That's not too convincing for me. :\ – user541686 May 27 '11 at 04: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. – ditkin May 27 '11 at 04: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? – Gyan aka Gary Buyn May 27 '11 at 04:36
  • @Gary: There's nothing more complex about it. In fact, I don't imagine that the interface of `ArrayList` would change at all, just the time complexities. It wouldn't break a single piece of code or put any more burden on any programmer, not even the slightest bit. – user541686 May 27 '11 at 04:44
  • You're right, if you only held references to `List` then you could switch in and out any implementation easily and there would be no impact for the programmer. I was meaning the internal complexities. In most cases those internal complexities are most likely of no concern to you and using one implementation or the other has little or no real impact on performance. The are, however, some cases (like I mentioned in my previous comment) where the performance disadvantage is noticeable so to answer your question: Yes, there is sometimes a disadvantage to using the latter over the former. – Gyan aka Gary Buyn May 27 '11 at 05:08
  • @Gary: Why `List`? It wouldn't even change if you had a concrete `ArrayList`, right? As for the performance issue: It's not too convincing but I guess it's a potential reason. – user541686 May 27 '11 at 05:10
  • It really depends on what you're writing, if you're writing something like a computer game you'll probably want to optimize as much as possible but if you're writing something that isn't intensive it doesn't really matter. As for `List`, if you were referencing `ArrayList` everywhere and then you decided to change to `LinkedList`, you would have to change all those references. If you create an instance of `ArrayList` but always referenced it using a `List` pointer, all you would have to do is change the line where it is instantiated. – Gyan aka Gary Buyn May 27 '11 at 05:18
  • @Gary: Wait, I'm a little confused -- I wasn't talking about `LinkedList` at all. I was just saying that, if they changed the default implementation of `ArrayList` to be double-ended, it would not affect any existing code in any way whatsoever. Not sure why you brought up `LinkedList` though. – user541686 May 28 '11 at 01:15
  • `LinkedList` is a double ended list. I was just using it as an example to say you could switch between any implementation of `List` though. – Gyan aka Gary Buyn May 28 '11 at 01:33
  • @Gary: I wasn't talking about *any* double-ended list, but a double-ended array list. :P – user541686 May 28 '11 at 01:37

4 Answers4

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.

cHao
  • 84,970
  • 20
  • 145
  • 172
  • Is that single load + addition operation *really* an even measurable performance hit? – user541686 May 27 '11 at 04:09
  • 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? – cHao May 27 '11 at 04:15
  • I haven't done any benchmarks, but it just seemed to me that there would be other bottlenecks (e.g. nonlocal loads/stores) that would beat this by quite a lot. I'll probably accept this if I don't hear something more convincing though, thanks. – user541686 May 27 '11 at 04:18
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.

Jack
  • 131,802
  • 30
  • 241
  • 343
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.

supercat
  • 77,689
  • 9
  • 166
  • 211
  • There's nothing unclear about indexing, it would behave exactly the same way as a C++ deque, which has exactly the same functionality except implemented in a much more heavyweight fashion. (All indices would be nonnegative.) – user541686 Dec 24 '13 at 21:15
0

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

ditkin
  • 6,774
  • 1
  • 35
  • 37