Editing Double-ended queue (section)

== Complexity ==
* In a doubly-linked list implementation and assuming no allocation/deallocation overhead, the [[Computational complexity theory|time complexity]] of all deque operations is [[Big O notation|O(1)]]. Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n).
* In a growing array, the [[Amortized analysis|amortized]] time complexity of all deque operations is [[Big O notation|O(1)]]. Additionally, the time complexity of random access by index is O(1); but the time complexity of insertion or deletion in the middle is [[Big O notation|O(n)]].