6

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?

gengkev
  • 1,890
  • 2
  • 20
  • 31
  • 1
    From https://en.wikipedia.org/wiki/Circular_buffer _"However, expanding a circular buffer requires shifting memory, which is comparatively costly."_ – xrisk Jul 11 '15 at 06:56
  • From same source, _"For arbitrarily expanding queues, a linked list approach may be preferred instead."_ – xrisk Jul 11 '15 at 06:58
  • Array-based deques can be faster than linked-list deques, although it's true that linked-list deques can be preferable because of the shifting memory issue. However, the question I wanted to ask was why not use this instead of an array list, which must also shift memory? – gengkev Jul 11 '15 at 07:03

1 Answers1

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.

Community
  • 1
  • 1
Kevin L. Stern
  • 365
  • 1
  • 7
  • I understand there's some extra overhead involved (I like the bitwise operation!) but it only seems to be a few extra CPU instructions, on top of the standard out-of-bounds check in languages other than C++. Does this really impact performance significantly? – gengkev Jul 12 '15 at 02:56
  • The performance impact depends upon the characteristics of your software, the compiler that you're using, and the architecture on which you are running. That being said, my intuition agrees with yours that it generally would not be noticeable. – Kevin L. Stern Jul 12 '15 at 19:20