9

I know that ArrayDeque is fast when adding and removing simple lists. I tested it, it was quicker to add and delete than LinkedList. Because I know that it is implemented as an Array, so why not Random Access?

I read the ArrayDeque.java file in the Java src. But I do not understand it well with my English level. I've seen a lot of articles from Google and Stack Overflow, but I did not get the answers I wanted.

In conclusion, what I'm looking for is:

  1. Why is ArrayDeque not Random Access? (I am most curious)
  2. In what situations is ArrayDeque used?
  3. Is ArrayDeque not implemented as an Array? (Did I misunderstand this?)

Thank you very much for your reply!

White_King
  • 748
  • 7
  • 21
Taylous
  • 260
  • 4
  • 15
  • 1
    There were plans to retrofit `ArrayDeque` to implement the `List` interface (or just to implement some `List`-related methods), but I'm not sure if it's being discussed actively: https://markmail.org/message/tdp2hjhsuknfthrf?q=net.java.openjdk&utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+MarkmailNetjavaopenjdk+%28Follow+OpenJDK+development+e-mail+traffic%29#query:net.java.openjdk+page:1+mid:ao3xupqbbafdoax6+state:results – Jacob G. Jan 24 '19 at 00:47
  • Do I need to point out that you're intended to program against the interface (in this case, `Deque`) rather than the implementation? As for performance, `ArrayDeque` is faster at some operations while `LinkedList` is faster at others.... and `ConcurrentLinkedDeque` is the only one that's thread-safe out of the box. – Powerlord Jan 24 '19 at 01:00

3 Answers3

14

The answer is that there's no good reason. It would be easy to add a constant-time get(int) and set(int,E) to ArrayDeque. More than once I've had to implement the algorithms of ArrayDeque within an ArrayList to make up for that lack.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
  • There is an issue open for this, although it isn't getting much attention: https://bugs.openjdk.java.net/browse/JDK-8143850 – john16384 Jan 29 '21 at 11:00
  • Yeah, that change request asks for too much. – Matt Timmermans Jan 29 '21 at 13:42
  • There would be very good reasons for it. I've just bumped into a case where I need to sum up some elements in the queue (and even do a weighted sum). Fortunately, Kotlin was smarter than to say there's no reason for it. :-) – Gábor Jul 26 '22 at 22:39
4

As mentioned in here, ArrayDeque is resizable-array implementation of the Deque interface. Underlining data-structure is Array. However, it doesn't support random access because it exposes double-ended queue interface. If you want to access a random element of Deque, you can invoke toArray() and then access elements by index.

Tarun Kumar
  • 5,150
  • 6
  • 26
  • 30
  • Thank you for answer. If I want to use Random Access in ArrayDeque, is it better to just use ArrayList? If I were to use the toArray() method? – Taylous Jan 24 '19 at 01:18
  • `toArray()` has the drawback that it sets all the values in an array, so it's O(N). I have [an alternative answer](https://stackoverflow.com/a/75584860/1889018), which should be O(1). I did a few measurements, and `toArray()` is faster for a relatively small size of an `ArrayDeque`, but it is significantly slower with larger sizes (millions or more). Of course, usage patterns matter a lot too. What surprised me is that the variant of `toArray()` that uses a preallocated array seems always slower than the one that creates a new array. – ciobi Feb 28 '23 at 08:09
0

I think the short answer to "why there is no random access" is that it didn't seem necessary when the class was created, and also it sort of doesn't make sense: ArrayDeque is firstly a kind of Deque, which is something mainly allowing access at both ends and that's about it. So I sort of agree that a random access function shouldn't be in Deque (though, by the same logic, it shouldn't be in List either). You can also have ArrayDeque implementing List, as others pointed out, but it's hard to retrofit and perhaps there are other issues. I personally think the collection interfaces in Java are a big mess, but I'll leave it at this.

Now, if you want a solution to the drawback of ArrayDeque not having random access, there are some options:

  • First of all, do you really need random access? Perhaps iterator() or descendingIterator() are good enough.
  • For truly random access, this is probably not very fast, but it should be O(1): deque.stream().skip(index).findFirst().get()
ciobi
  • 97
  • 1
  • 10