Random access in ArrayDeque

[David M. Lloyd]

Just want to say that we've also had the need to implement an 
array-backed Deque+List; we found no surprises implementing it and thus 
I believe that extending ArrayDeque to implement List would be a 
positive change.  Failing that, a combined ArrayListAndDeque class seems 
like a good idea.

I think that calling it "Masters' thesis" material is perhaps 
overblowing the complexity a bit though. ;)  Given that the basic 
algorithmic complexity of ArrayList is well-understood and is 
well-suited to many (some would say "most") applications, going for a 
O(sqrt(N)) middle insert/remove complexity would be something I would 
consider "scope creep"; LinkedList is usually a fine choice for these cases.

On 02/07/2014 11:44 AM, Dan Smith wrote:
> I noticed recently that the javac scanner is making use of ArrayList.remove(0) when it consumes a buffer.  Obviously this is an inefficient way to implement a buffer, so I thought I'd try to fix it [1].  ArrayDeque seems to provide just the behavior I need, with one fatal flaw: despite encoding its data with an array, the class exposes no random-access operations.  For lookahead, I need to be able to call get(int).
>
> This seems to be a fairly common complaint [2][3].
>
> I found an old bug requesting that ArrayDeque be enhanced to implement List [4], as well as a thread from 2010 that included a proof-of-concept ArrayDeque+List [5] and had a note from Martin Buchholz saying he regrets that ArrayDeque doesn't already implement List [6].
>
> Is there any hope of ArrayDeque being enhanced in the near future to provide random access?  There's some risk that any such initiative would be derailed by a quest for an uber-collection.  I think a lot of people would be quite happy just to have a (trivial) 'get(int)' method added to ArrayDeque.
>
> —Dan
>
> [1] https://bugs.openjdk.java.net/browse/JDK-8033158
> [2] http://en.wikipedia.org/wiki/Deque#Language_support
> [3] https://www.google.com/#q=arraydeque+%22random+access%22
> [4] https://bugs.openjdk.java.net/browse/JDK-6368844
> [5] http://mail.openjdk.java.net/pipermail/core-libs-dev/2010-April/004038.html
> [6] http://mail.openjdk.java.net/pipermail/core-libs-dev/2010-April/004031.html
>


-- 
- DML