title: Why not always use circular array deques instead of array lists?
body: <p>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 <code>ArrayList</code>, and C++ has <code>std::vector</code>.</p>
  
  <p>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. </p>
  
  <p>(While Java's <code>ArrayDeque</code> implements this data structure, it doesn't allow lookup of elements. C++'s <code>std::deque</code> appears to use a different implementation.)</p>
  
  <p>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?</p>