Why not always use circular array deques instead of array lists?

Question

Almost all programming languages have some implementation of a list that uses a dynamic array, which automatically expands when it reaches a certain capacity. For example, Java has ArrayList, and C++ has std::vector.

Recently I learned about circular array deques, which are also implemented using dynamic arrays. They keep track of the starting index of the list, and use modular arithmetic to access elements. Like array lists, they allow O(1) lookup and O(1) insertion at the end, and space proportional to O(N). However, they also allow O(1) insertion at the beginning.

(While Java's ArrayDeque implements this data structure, it doesn't allow lookup of elements. C++'s std::deque appears to use a different implementation.)

If these array deques have the same or better performance characteristics as array lists, then why not always use them as the default implementation for lists?

Answer 1

If you don't need insertion at the head of the list, then a circular deque gives unnecessary overhead, e.g. for indexed methods. In a circular deque, accessing index i requires adding i to the index of the head element and looping around (e.g. using modulo, or bitwise operators) before accessing the underlying array, whereas with a vanilla vector, no manipulation to i is necessary before accessing the underlying array.

To demonstrate this overhead, a typical deque implementation might look like:

template <typename T>
class Deque {
  private:
    T* array; // The underlying array, holding elements of the deque.
    int size; // The number of elements held by the deque.
    int capacity; // The size of array ** must be a power of two **.
    int head; // The index of the head element within array.

  public:
    T& operator[](int index) {
        // Notice the calculation required before accessing array.
        return array[(head + index) & (capacity - 1)]
    }
};

In addition, if you require access to the underlying array where your elements are contiguous beginning at index 0, a deque would not deliver.

See question Why would I prefer using vector to deque, which is very similar to yours.