Random access in ArrayDeque

Doug Lea dl at cs.oswego.edu
Sat Feb 8 19:33:15 UTC 2014


On 02/07/2014 01:59 PM, Martin Buchholz wrote:

> ArrayDeque should implement most of the methods in List, notably get(i).
>
> ArrayDeque should not actually implement List itself, because the change in
> contract/behavior for hashCode/equals would be too great.

Right. My vague recollection is that these were among initial reasons
for not implementing List. Also, the List.sublist method is questionable
for a Queue.

Too bad there is no interface with only get(index), set(index, x),
and indexOf(x). Implementing only these would probably satisfy
all candidate usages.

> But we can
> provide a
> List asList()
> method.

This might be the best compromise. Possibly with the sublist
method returning an unmodifiable list (which is legal and
probably not too surprising). Maybe even similarly for listIterator.

-Doug


>
> If we have agreement, we can do the relatively easy implementation.
>
>
> On Fri, Feb 7, 2014 at 10:07 AM, David M. Lloyd <david.lloyd at redhat.com>wrote:
>
>> 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
>>
>





More information about the core-libs-dev mailing list