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!

Improve this question
2
  • 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: markmail.org/message/… Commented Jan 24, 2019 at 0: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. Commented Jan 24, 2019 at 1:00

3 Answers 3

Reset to default
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.

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

3 Comments

There is an issue open for this, although it isn't getting much attention: bugs.openjdk.java.net/browse/JDK-8143850
Yeah, that change request asks for too much.
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. :-)
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.

Improve this answer

2 Comments

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?
toArray() has the drawback that it sets all the values in an array, so it's O(N). I have an alternative answer, 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.
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()
Improve this answer

1 Comment

Nonsense. LinkedList is primarily a List, yet it somehow implemented Deque.

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.