2

I'm currently taking an algorithms class online, and our textbook is Pat Morin's Open Data Structures.

In his discussion of ArrayDeque, Morin claims, "The ArrayDeque data structure allows for efficient addition and removal at both ends. This structure implements the List interface." He then goes on to discuss a C++ implementation of the data structure, including the expected List methods: get(i), set(i, x), add(i, x), and remove(i).

I found the author's treatment confusing, as I can't imagine how this implementation could be considered a Deque; it features insertion/deletion at any position, after all.

On the other hand, other resources indicate that ArrayDeque implements the Deque interface ("duh," right?). In fact, this article claims, "the ArrayDeque is the array-based implementation of the Deque interface." Furthermore, "the ArrayDeque, unlike the LinkedList, does not implement the List interface, and so we never think about using it for positional access." This treatment makes perfect sense to me, and it seems to follow the consensus of the various articles I've found.

So is Morin's book just wrong, or am I missing something fundamental?

4
  • If you look at the Java API ArrayDeque does implement Deque
    – Courage
    May 24, 2017 at 3:09
  • The ArrayDeque data structure supports efficient insertion and removal at both ends, so it's perfectly reasonable to use it as a Deque. An ArrayList, in contrast, only supports efficient insertion and removal at the end, so you can use it for a stack, but you shouldn't use it as a queue. Both data structures also support efficient random access and iteration, so you can use either one as a random access list, even though Java doesn't implement List on their ArrayDeque May 24, 2017 at 3:22
  • @yurikilochek Just because the question mentions things that exist in Java doesn't mean that's the only place they exist. This seems to be about the general data structure as opposed to any given implementation. The first link is C++-related. Jun 6, 2017 at 18:19
  • @Dukeling fair enough. Jun 6, 2017 at 19:01

2 Answers 2

0

Different implementations of array-based deques support different functionality, while using the same underlying structure. For example, in the Java Collections Framework, ArrayDeque only implements the Deque interface and does not support constant-time access by index.

Morin's implementation of ArrayDeque implements only the List interface. However, implementing the Deque interface with a List is straight-forward:

addFirst(x) { add(0, x); }
removeFirst() { return remove(0); }
addLast(x) { add(size, x); }
removeLast() { return remove(size - 1); }

The performance guarantees for add and remove imply that each of these operations runs in constant time, making it an efficient deque.

So using the underlying structure of an array-based deque, it is possible to implement both the List and Deque interfaces, and different implementations make different choices in this.

0

From the Java docs

java.util
Class ArrayDeque

* java.lang.Object
* * java.util.AbstractCollection
* * * java.util.ArrayDeque

Type Parameters:
E - the type of elements held in this collection

All Implemented Interfaces:
Serializable, Cloneable, Iterable, Collection, Deque, Queue

ArrayDeque implements Iterable, Collection, Deque, and Queue (and Serializable, Cloneable); so no List, just Iterable.

In Morin's book, he is talking about writing your own ArrayDeque that has nothing to do with the Java implementation; and the auther is explaining that by using this underlying data-structure to implement an ArrayDeque, you can implement the List interface. (Key here, they are not saying that all ArrayDeque will implement List, because random access kinda messes with the whole 'que' part of the structure. But you CAN (and shouldn't))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.