Why doesn't ArrayDeque implement the List interface?

[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]

Hi Joe,

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.

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];
}

 

[Giovanni Azua]

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.

Even more trivial would be just to myDeque.getArray() and get the i-th
element.

regards,
Giovanni

 

[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];
}

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".

 

[Giovanni Azua]

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.

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]

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..

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]

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.

Even more trivial would be just to myDeque.getArray() and get the i-th
element.

regards,
Giovanni

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.

 

[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.

Sorry, I mixed it up.

regards,
Giovanni

 

[tennenrishin]

CircularArrayList implementation for Java

This thread is old, but in case anyone else (like I did) still comes here looking for a ready-to-use implementation of a circular buffer in Java, here is one:
CircularArrayList
It is probably the simplest possible implementation. I use it in production code. It supports generic element type. And it follows the Javadocs' instructions for extending AbstractList.