Why doesn't ArrayDeque implement the List interface?

Discussion in 'Java' started by Joe Gottman, Mar 4, 2009.

  1. Joe Gottman

    Joe Gottman Guest

    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, Mar 4, 2009
    #1
    1. Advertising

  2. Joe Gottman

    Mark Space Guest

    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, Mar 4, 2009
    #2
    1. Advertising

  3. Joe Gottman

    Joe Gottman Guest

    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/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
     
    Joe Gottman, Mar 4, 2009
    #3
  4. 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 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.
     
    Mike Schilling, Mar 4, 2009
    #4
  5. Joe Gottman

    Lew Guest

    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
    > 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, Mar 4, 2009
    #5
  6. Joe Gottman

    Joe Gottman Guest

    Lew wrote:
    > 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 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, Mar 4, 2009
    #6
  7. Joe Gottman

    Lew Guest

    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
     
    Lew, Mar 4, 2009
    #7
  8. Joe Gottman

    Mark Space Guest

    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 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, Mar 4, 2009
    #8
  9. Joe Gottman

    Daniel Pitts Guest

    Mark Space wrote:
    > 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/>
     
    Daniel Pitts, Mar 4, 2009
    #9
  10. 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).)
     
    Mike Schilling, Mar 4, 2009
    #10
  11. Joe Gottman

    Mark Space Guest

    Daniel Pitts wrote:

    >
    > 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.
     
    Mark Space, Mar 4, 2009
    #11
  12. Joe Gottman

    Patrick Guest

    Patrick, Mar 4, 2009
    #12
  13. Joe Gottman

    Joe Gottman Guest

    Patrick wrote:
    > Le 04/03/2009 04:21, Joe Gottman a écrit :
    >> Is there a procedure for requesting this functionality be added?

    >
    > http://openjdk.java.net/projects/coin/


    Thank you,

    Joe Gottman
     
    Joe Gottman, Mar 4, 2009
    #13
  14. Mark Space wrote:
    > Daniel Pitts wrote:
    >
    >>
    >> 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.


    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();
    }
     
    Mike Schilling, Mar 4, 2009
    #14
  15. Joe Gottman

    Daniel Pitts Guest

    Mike Schilling wrote:
    > If it's more complicated that "head + N mod size" I'm not seeing why.

    You missed a parenthesis :)


    --
    Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
     
    Daniel Pitts, Mar 5, 2009
    #15
  16. Hi Joe,

    "Joe Gottman" <> 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, E)
    http://java.sun.com/j2se/1.5.0/docs/api/java/util/List.html#remove(java.lang.Object)

    HTH,
    regards,
    Giovanni
     
    Giovanni Azua, Mar 9, 2009
    #16
  17. Giovanni Azua wrote:
    > Hi Joe,
    >
    > "Joe Gottman" <> 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, E)
    > 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
    how get(), which doesn't modify the queue, could break its
    invariants.)
     
    Mike Schilling, Mar 9, 2009
    #17
  18. Hi Mike,

    "Mike Schilling" <> 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, E)
    >> 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
     
    Giovanni Azua, Mar 9, 2009
    #18
  19. Joe Gottman

    Joe Gottman Guest

    Giovanni Azua wrote:
    > Hi Mike,
    >
    > "Mike Schilling" <> 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, E)
    >>> 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
    >
    >


    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
     
    Joe Gottman, Mar 9, 2009
    #19
  20. Hi Joe,

    "Joe Gottman" <> 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/a...earch(java.util.List, T, java.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]);

    HTH,
    Best regards,
    Giovanni
     
    Giovanni Azua, Mar 10, 2009
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jan Schulze
    Replies:
    1
    Views:
    599
    Esmond Pitt
    Mar 26, 2005
  2. Mr. SweatyFinger

    why why why why why

    Mr. SweatyFinger, Nov 28, 2006, in forum: ASP .Net
    Replies:
    4
    Views:
    996
    Mark Rae
    Dec 21, 2006
  3. Mr. SweatyFinger
    Replies:
    2
    Views:
    2,266
    Smokey Grindel
    Dec 2, 2006
  4. Tony

    Why Re-implement Interface

    Tony, Oct 5, 2007, in forum: Java
    Replies:
    4
    Views:
    472
    Roedy Green
    Oct 5, 2007
  5. dhruvbird
    Replies:
    16
    Views:
    1,395
    John Nagle
    Jul 16, 2010
Loading...

Share This Page