Why doesn't ArrayDeque implement the List interface?
Joe Gottman
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
Mark Space
> 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
Check the documentation of ArrayDeque
(http://java.sun.com/javase/6/docs/api/java/util/ArrayDeque.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
Mike Schilling
>
> Check the documentation of ArrayDeque
> (http://java.sun.com/javase/6/docs/api/java/util/ArrayDeque.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.
Lew
> Check the documentation of ArrayDeque
> (http://java.sun.com/javase/6/docs/api/java/util/ArrayDeque.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
Joe Gottman
Is there a procedure for requesting this functionality be added?
Joe Gottman
Lew
> 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
Mark Space
> Check the documentation of ArrayDeque
> (http://java.sun.com/javase/6/docs/api/java/util/ArrayDeque.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.
Daniel Pitts
> Joe Gottman wrote:
>
>> Check the documentation of ArrayDeque
>> (http://java.sun.com/javase/6/docs/api/java/util/ArrayDeque.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/>
Mike Schilling
> 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).)
Mike Schilling
> Joe Gottman wrote:
>
>> Check the documentation of ArrayDeque
>> (http://java.sun.com/javase/6/docs/api/java/util/ArrayDeque.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.)
All true, but the offset is still known at any given time, since it's
where you'd find the first member.
> I think if you try implementing your own you'll find out exactly
> what
> the issue is. I'll bet it's nasty too.
If it's more complicated that "head + N mod size" I'm not seeing why.
Mark Space
>
> 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.
I was thinking that the result of this operation would be poorly defined:
Object o1 = new Object();
Object o2 = new Object();
ArrayDeque aq = new ArrayDeque();
aq.addFirst( o1 );
Object o3 = aq.get( 0 ); // Zero
aq.addFirst( o2 );
Object o4 = aq.get( 0 ); // Zero
But it works with a LinkedList (by returning different objects into o3
and o4, I assume) so I guess an array/ring buffer shouldn't be any
different. OK, I guess get() could be implemented after all for an
ArrayDeque.
Patrick
>
> Is there a procedure for requesting this functionality be added?
Joe Gottman
Thank you,
Joe Gottman
Mike Schilling
This even works with ArrayList if you write
Object o1 = new Object();
Object o2 = new Object();
ArrayList al = new ArrayList();
aq.add(0, o1 );
Object o3 = aq.get( 0 ); // Zero
aq.add( 0, o2 );
Object o4 = aq.get( 0 ); // Zero
It's far less efficient, of course, since all the items in the List
need to be moved to accomodate the next first item. Anyway, the point
is that any particular List implementation can define methods that
modify itself in any way it likes, e .g.
class SillyList extends ArrayList
{
public void moveStuffAroundAtRandom();
}
Daniel Pitts
> If it's more complicated that "head + N mod size" I'm not seeing why.
Giovanni Azua
"Joe Gottman" <jgot...@carolina.rr.com> wrote in message
> [snip]
> 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?
The List interface includes a few methods that would break the Queue or
Dequeue semantics and invariants i.e. these List methods do not belong to
a Queue interface e.g.
http://java.sun.com/j2se/1.5.0/docs/api/java/util/List.html#get(int)
http://java.sun.com/j2se/1.5.0/docs/api/java/util/List.html#add(int,%20E)
http://java.sun.com/j2se/1.5.0/docs/api/java/util/List.html#remove(java.lang.Object)
HTH,
regards,
Giovanni
Mike Schilling
Note that ArrayDeque does support the last of these (and I don't see
how get(), which doesn't modify the queue, could break its
invariants.)
Giovanni Azua
"Mike Schilling" <mscotts...@hotmail.com> wrote
>> The List interface includes a few methods that would break the Queue
>> or Dequeue semantics and invariants i.e. these List methods do not
>> belong to a Queue interface e.g.
>>
>> http://java.sun.com/j2se/1.5.0/docs/api/java/util/List.html#get(int)
>> http://java.sun.com/j2se/1.5.0/docs/api/java/util/List.html#add(int,%20E)
>> http://java.sun.com/j2se/1.5.0/docs/api/java/util/List.html#remove(java.lang.Object)
>
> Note that ArrayDeque does support the last of these (and I don't see
Sorry I meant this method:
http://java.sun.com/javase/6/docs/api/java/util/List.html#remove(int)
> how get(), which doesn't modify the queue, could break its invariants.)
get does not modify the invariant but it does modify the semantics of a
Queue i.e. you are not supposed to get elements from arbitrary positions.
Best regards,
Giovanni
Joe Gottman
I think that we have a philosophical difference here. You think
that an ArrayDeque should ONLY be used as a queue. I think that it
should be usable as a queue, and for whatever other uses a coder
desires, as long as those uses don't make it less efficient when used as
a Queue. Note that an ArrayList can be used as either a List or a Queue,
even though it is has linear complexity on its get() method. As it is
currently implemented, ArrayDeque could be given a constant-complexity
get() method. I find it annoying that in my use-case (a data structure
with allowing indexing everywhere and insertions and deletions at the
ends) the standard demands I either use a highly inefficient class or
write my own. This is not an uncommon use case; see for example the C++
deque class, which has precisely these semantics.
If you want to use an ArrayDeque but only want users to use it as a
Deque, you can just write code like
Deque<String> myDeque = new ArrayDeque<String>();
This will ensure that users of your code not misuse your ArrayDeque,
while allowing others to use their own ArrayDeques as they see fit.
Joe Gottman
Giovanni Azua
"Joe Gottman" <jgot...@carolina.rr.com> wrote
> Giovanni Azua wrote:
> I think that we have a philosophical difference here. You think that an
> ArrayDeque should ONLY be used as a queue. I think that it [snip]
>
Well not exactly. I think that any implementation, in this case an
ArrayDeque should be used as whatever interface(s) it implements, no more
but no less.
If you have very specific needs and in very rare cases you could resort to
extending the closest match in the Collections API and creating an ad
hoc implementation that fits your needs e.g. if you needed something like a
"CircularPriorityQueue" then you would extend PriorityQueue (or preferably
use the Decorator Pattern) and add the circularity feature.
Dequeue main use-case is to manipulate and retrieve elements from the ends
and that's O(c) complexity, not linear. If you try using a helicopter as a
blender then you are getting into troubles no one could have ever predicted
like ending up in a very inefficient usage.
> should be usable as a queue, and for whatever other uses a coder desires,
> as long as those uses don't make it less efficient when used as a Queue.
> Note that an ArrayList can be used as either a List or a Queue, even
> though it is has linear complexity on its get() method.
>
I disagree, ArrayList should be only used as what its official contract
offers i.e. its implemented interfaces. ArrayList only offers to customers
the List and RandomAccess contracts. As you know you are free to leave the
contracts and get into slightly hacking arena but then you will be on your
own like now. ArrayList does not offer fast search per se, it is not built
for that purpose. If you need fast retrieval you should use e.g.
- TreeSet O(log N)
- TreeMap O(log N)
> As it is currently implemented, ArrayDeque could be given a
> constant-complexity get() method.
>
I think this is not possible without implementing the ArrayDeque to
internally manipulate a redundant data structure optimized for searching.
But then it would not be an ArrayDeque anymore but something else.
What I would myself do in this case is:
1) create a new interface e.g. LogNSearchDeque extends Deque and adds a
method search(Element anElement)
2) introduce new class LogNSearchArrayDeque that implements #1 and extends
ArrayDeque. This implementation could e.g. aggregate and delegate to a
redundant collection optimized for search like the ones above or do it
yourself using a sorted ArrayList and Collections.binarySearch:
http://java.sun.com/javase/6/docs/api/java/util/Collections.html#binarySearch(java.util.List,%20T,%20java.util.Comparator)
> I find it annoying that in my use-case (a data structure
> with allowing indexing everywhere and insertions and deletions at the
> ends) the standard demands I either use a highly inefficient class or
> write my own. This is not an uncommon use case; see for example the C++
> deque class, which has precisely these semantics.
>
I checked the deque class in std and it does not offer a fast search get
method. I can only see the access "operator[]" and "at" methods where you
should provide the position index:
http://www.cplusplus.com/reference/stl/deque/
http://www.cplusplus.com/reference/stl/deque/at.html
Since ArrayDeque lacks a get(i) you can easily do:
Deque<String> myDeque = new ArrayDeque<String>();
// ... insert elements
// get the i-th element
int i = 3;
String myThirdElement = myDeque.toArray(new String[0])[i];
HTH,
Best regards,
Giovanni
Mike Schilling
>>
>
> I think that we have a philosophical difference here. You think
> that an ArrayDeque should ONLY be used as a queue. I think that it
> should be usable as a queue, and for whatever other uses a coder
> desires, as long as those uses don't make it less efficient when
> used
> as a Queue. Note that an ArrayList can be used as either a List or a
> Queue, even though it is has linear complexity on its get() method.
ITYM LinkedList, since ArrayList has a constant-cost get() method (and
would make a terrible queue, though a pretty good stack.)
Mike Schilling
No, the get method would be trivial to implement:
public T get(int i)
{
if ( i < 0 || i >= size)
throw new IllegalIndexException();
return members[(firstIndex + i) % size];
}
Patricia Shanahan
> Hi Joe,
>
> "Joe Gottman" <jgot...@carolina.rr.com> wrote
>> Giovanni Azua wrote:
>> I think that we have a philosophical difference here. You think that an
>> ArrayDeque should ONLY be used as a queue. I think that it [snip]
>>
> Well not exactly. I think that any implementation, in this case an
> ArrayDeque should be used as whatever interface(s) it implements, no more
> but no less.
I think the suggestion here is to add "List" to its interfaces, so
List myList = new ArrayDeque();
would use it as one of the interfaces it implements.
LinkedList combines the List and Deque interfaces, and is commonly used
as a List. The only difference between it and the proposed
List-implementing ArrayDeque is one of implementation, and resulting
operation speeds.
Patricia
Giovanni Azua
"Mike Schilling" <mscotts...@hotmail.com> wrote
> No, the get method would be trivial to implement:
>
> public T get(int i)
> {
> if ( i < 0 || i >= size)
> throw new IllegalIndexException();
> return members[(firstIndex + i) % size];
> }
>
Even more trivial would be just to myDeque.getArray() and get the i-th
element.
regards,
Giovanni
Mike Schilling
> "Mike Schilling" <mscotts...@hotmail.com> wrote
>> No, the get method would be trivial to implement:
>>
>> public T get(int i)
>> {
>> if ( i < 0 || i >= size)
>> throw new IllegalIndexException();
>> return members[(firstIndex + i) % size];
>> }
>>
> No, I was not refering to this access method but to a binary search
> method.
No one was asking for that.
>
> Even more trivial would be just to myDeque.getArray() and get the
> i-th
> element.
You have an odd notion of "constant cost".
Patricia Shanahan
> "Mike Schilling" <mscotts...@hotmail.com> wrote
>> No, the get method would be trivial to implement:
>>
>> public T get(int i)
>> {
>> if ( i < 0 || i >= size)
>> throw new IllegalIndexException();
>> return members[(firstIndex + i) % size];
>> }
>>
> No, I was not refering to this access method but to a binary search method.
But indexed get is the method the OP needs that ArrayDeque does not
implement.
If ArrayDeque did implement a fast get(i), it would meet the conditions
for the RandomAccess interface, and would presumably implement it. The
binarySearch in Collections would be O(log n). There would be no need to
do anything (other than implement RandomAccess) in ArrayDeque to
implement binary search.
> Even more trivial would be just to myDeque.getArray() and get the i-th
> element.
As far as I can tell, ArrayDeque does not have a getArray method. If you
mean toArray, that is not a solution because it is an O(n) operation. It
is the same time complexity, and higher space complexity, than the
LinkedList random element indexed get.
If the List is not performance-critical the choice of implementing class
does not matter. Any List would be as good as any other List. This
discussion only makes sense in the context of a need for a List that
has both fast indexed access and fast head and tail insert and delete.
Patricia
Giovanni Azua
"Mike Schilling" <mscotts...@hotmail.com> wrote
> No, the get method would be trivial to implement:
>
> public T get(int i)
> {
> if ( i < 0 || i >= size)
> throw new IllegalIndexException();
> return members[(firstIndex + i) % size];
> }
>
i.e. ArrayDeque does not have a "members" attribute but an "elements" one
and it has private access.
>> Even more trivial would be just to myDeque.getArray() and get the i-th
>> element.
>
> You have an odd notion of "constant cost".
No, I just never looked at the implementation. Now I see it is O(n).
Giovanni
Mike Schilling
> "Mike Schilling" <mscotts...@hotmail.com> wrote
>> No, the get method would be trivial to implement:
>>
>> public T get(int i)
>> {
>> if ( i < 0 || i >= size)
>> throw new IllegalIndexException();
>> return members[(firstIndex + i) % size];
>> }
>>
> This would be trivial to implement only if you could change the JDK
> yourself i.e. ArrayDeque does not have a "members" attribute but an
> "elements" one and it has private access.
Yes, exactly, it would be trivial for the maintainer of ArrayDeque to
implement..
>
>>> Even more trivial would be just to myDeque.getArray() and get the
>>> i-th element.
>>
>> You have an odd notion of "constant cost".
> No, I just never looked at the implementation. Now I see it is O(n).
I didn't look at the implementation either, but it seems clear that creating
an array of n elements would be (at least) O(n)
Daniel Pitts
There has been no talk of ordering of the ArrayDeque. It has only been
about indexed-get.
Giovanni Azua
> Why are you talking about a search method? No one else here has been.
> There has been no talk of ordering of the ArrayDeque. It has only been
> about indexed-get.
>
regards,
Giovanni
iam...@gmail.com
> 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
> 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
>
I just noticed that ArrayList and LinkedList are added in Java 1.2, while ArrayDeque is added in Java 6. Maybe the team think it is better for the new implementation ArrayDeque to be only for Deque, and leaving ArrayList for List.
Hogan Shi
Marcel Mueller
> On Wednesday, March 4, 2009 at 8:55:14 AM UTC+8, Joe Gottman wrote:
Seems that it took a bit longer to write the answer this time. :-)
Marcel