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
