«

I have an application where I need to access the elements of a
container by index and add and remove elements at either end. I thought
that ArrayDeque was the obvious solution, but I was surprised to find
that it doesn't implement the List interface. Why is this? My use case
isn't unusual; it's the same as the C++ deque template. It's especially
galling in that it would be possible to implement a get() member
function with constant time complexity in ArrayDeque, but the LinkedList
class, which does implement the List() interface, requires linear time
to perform get(). It seems backward to me that Java mandates the less
efficient data structure for my use case.

Joe Gottman

Joe Gottman wrote:
> I have an application where I need to access the elements of a
> container by index and add and remove elements at either end. I thought
> that ArrayDeque was the obvious solution, but I was surprised to find
> that it doesn't implement the List interface. Why is this? My use case


Probably be inserting elements at the head of an ArrayDeque would give
very poor performance. Look at LinkedList instead, it implements both
List and Deque.

Mark Space wrote:
Mark Space wrote:
> Joe Gottman wrote:
>> I have an application where I need to access the elements of a
>> container by index and add and remove elements at either end. I
>> thought that ArrayDeque was the obvious solution, but I was surprised
>> to find that it doesn't implement the List interface. Why is this?
>> My use case
>
>
> Probably be inserting elements at the head of an ArrayDeque would give
> very poor performance. Look at LinkedList instead, it implements both
> List and Deque.

> Joe Gottman wrote:
>> I have an application where I need to access the elements of a
>> container by index and add and remove elements at either end. I
>> thought that ArrayDeque was the obvious solution, but I was surprised
>> to find that it doesn't implement the List interface. Why is this?
>> My use case
>
>
> Probably be inserting elements at the head of an ArrayDeque would give
> very poor performance. Look at LinkedList instead, it implements both
> List and Deque.

Check the documentation of ArrayDeque
(http://java.sun.com/javase/6/docs/ap...rayDeque.html). It's
faster than LinkedList for inserting and deleting at either end. It
would also be faster than LinkedList for element access, if only the
get() function were provided.



Joe Gottman

Joe Gottman wrote:
>
> Check the documentation of ArrayDeque
> (http://java.sun.com/javase/6/docs/ap...rayDeque.html). It's
> faster than LinkedList for inserting and deleting at either end.
> It would also be faster than LinkedList for element access, if only
> the get() function were provided.

Good question; get() would be trivial to code in the current ArrayDeque
implementation.

Joe Gottman wrote:
> Check the documentation of ArrayDeque
> (http://java.sun.com/javase/6/docs/ap...rayDeque.html). It's
> faster than LinkedList for inserting and deleting at either end. It
> would also be faster than LinkedList for element access, if only the
> get() function were provided.

If I had some ham I could have a ham and cheese sandwich, if I only had some
cheese.

This is one of those rare cases when Sun hasn't done your job for you,
necessitating that one implement the desired functionality oneself.

You asked upthread why ArrayDeque doesn't do what you want. I guess Sun just
wasn't paying you close enough attention when they wrote their API.

--
Lew

Lew wrote:
> Joe Gottman wrote:
>> Check the documentation of ArrayDeque
>> (http://java.sun.com/javase/6/docs/ap...rayDeque.html).
>> It's faster than LinkedList for inserting and deleting at either end.
>> It would also be faster than LinkedList for element access, if only
>> the get() function were provided.
>
> If I had some ham I could have a ham and cheese sandwich, if I only had
> some cheese.
>
> This is one of those rare cases when Sun hasn't done your job for you,
> necessitating that one implement the desired functionality oneself.
>
> You asked upthread why ArrayDeque doesn't do what you want. I guess Sun
> just wasn't paying you close enough attention when they wrote their API.
>

Is there a procedure for requesting this functionality be added?

Joe Gottman

Joe Gottman wrote:
> Is there a procedure for requesting this functionality be added?

Actually, you may be stuck with LinkedList.

It could be that ArrayDeque can't be all things to all your desired interfaces
with all the performance that you want, because it is contradictory to want
constant (amortized) access time for 'get()' and for the other operations for
which you want fast action.

Joe Gottman wrote:
>> It's especially galling ...
>> It seems backward to me that Java mandates the less efficient
>> data structure for my use case.

Since it's your use case, maybe you should write the code.

--
Lew

Joe Gottman wrote:

> Check the documentation of ArrayDeque
> (http://java.sun.com/javase/6/docs/ap...rayDeque.html). It's
> faster than LinkedList for inserting and deleting at either end. It


It actually doesn't say that. It says "faster than Stack" ... Stack is
synchronized. It says "faster than LinkedList when used as a Queue" ...
Queues are inserted at the end and removed from the head. That's not
inserting and deleting at either end.

The latter makes me wonder if ArrayDeques are implemented as circular
buffers. This might mean that the "offset" which get() would use is
likely to shift around. That offset also might change completely if the
underlying array fills up and has to be copied to a larger array.
(ArrayDeques are specified to grow as needed, they don't block or throw
errors related to being out of storage.)


> would also be faster than LinkedList for element access, if only the
> get() function were provided.


I think if you try implementing your own you'll find out exactly what
the issue is. I'll bet it's nasty too.

Mark Space wrote:
> Joe Gottman wrote:
>
>> Check the documentation of ArrayDeque
>> (http://java.sun.com/javase/6/docs/ap...rayDeque.html).
>> It's faster than LinkedList for inserting and deleting at either end. It
>
>
> It actually doesn't say that. It says "faster than Stack" ... Stack is
> synchronized. It says "faster than LinkedList when used as a Queue" ...
> Queues are inserted at the end and removed from the head. That's not
> inserting and deleting at either end.
>
> The latter makes me wonder if ArrayDeques are implemented as circular
> buffers. This might mean that the "offset" which get() would use is
> likely to shift around. That offset also might change completely if the
> underlying array fills up and has to be copied to a larger array.
> (ArrayDeques are specified to grow as needed, they don't block or throw
> errors related to being out of storage.)
>
>
>> would also be faster than LinkedList for element access, if only the
>> get() function were provided.

I'm thinking you might actually have to create your own low-level
implementation, in order to get the functionality you desire. That is
unfortunate, but sometimes is the case.
>
>
> I think if you try implementing your own you'll find out exactly what
> the issue is. I'll bet it's nasty too.

It seems to me that you could pretty easily create a ring-buffer that
had a List style get/set, which was reasonably defined to consider the
get/set index as an offset from the buffer. An implementation wouldn't
be terribly difficult.


--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>

Lew wrote:
> Joe Gottman wrote:
>> Is there a procedure for requesting this functionality be added?
>
> Actually, you may be stuck with LinkedList.
>
> It could be that ArrayDeque can't be all things to all your desired
> interfaces with all the performance that you want, because it is
> contradictory to want constant (amortized) access time for 'get()'
> and for the other operations for which you want fast action.

Not in this case, though. Keep the current implementation, and get()
would be about five lines of code with no looping required.
(ArrayDeque is implemented as a segment of an an array, which might
wrap when it reaches the array end. Once you know the current head
and the current tail, finding member "n" is roughly ((head + n) mod
arraySize).)