Deque vs List in C++

Underlying:

• Deque (double-end queue) manages its elements with a dynamic array, provides random access, and has almost the same interface as a vector. Any insertion or deletion of elements other than at the beginning or end invalidates all pointers, references, and iterators that refer to elements of the deque.
• List manages its elements as a doubly linked list and does not provide random access. Inserting and deleting elements does not invalidate pointers, references, and iterators to other elements.

Complexity:

• Deque provides Fast insertions and deletions at both the end and the beginning. Inserting and deleting elements in the middle is relatively slow because all elements up to either of both ends may be moved to make room or to fill a gap. Accessing elements is O(1). Insertion or Removal are O(N). Insertion and Removal at both ends are O(1).
• In List, inserting and removing elements is fast at each position, including both ends.