data structures - Why not always use circular array deques instead of array lists? -

almost programming languages have implementation of list uses dynamic array, automatically expands when reaches capacity. example, java has arraylist, , c++ has std::vector.

recently learned circular array deques, implemented using dynamic arrays. keep track of starting index of list, , use modular arithmetic access elements. array lists, allow o(1) lookup , o(1) insertion @ end, , space proportional o(n). however, allow o(1) insertion @ beginning.

(while java's arraydeque implements data structure, doesn't allow lookup of elements. c++'s std::deque appears use different implementation.)

if these array deques have same or better performance characteristics array lists, why not use them default implementation lists?

if don't need insertion @ head of list, circular deque gives unnecessary overhead, e.g. indexed methods. in circular deque, accessing index requires adding index of head element , looping around (e.g. using modulo, or bitwise operators) before accessing underlying array, whereas vanilla vector, no manipulation necessary before accessing underlying array.

to demonstrate overhead, typical deque implementation might like:

template <typename t> class deque {   private:     t* array; // underlying array, holding elements of deque.     int size; // number of elements held deque.     int capacity; // size of array ** must power of 2 **.     int head; // index of head element within array.    public:     t& operator[](int index) {         // notice calculation required before accessing array.         return array[(head + index) & (capacity - 1)]     } }; 

in addition, if require access underlying array elements contiguous beginning @ index 0, deque not deliver.

see question why prefer using vector deque, similar yours.