What is the runtime of an ArrayDeque get(i) operation?
O(1)
What is the runtime of an ArrayDeque set(i,x) operation?
O(1)
What is the runtime of an ArrayDeque add(i,x) operation?
O(min{i, n-i}), amortized.
Recall that since the ArrayDeque is implemented by a circular array, you make space for item i by either shifting (i-1) items to the left, or (n-i+1) items to the right, whichever is smaller.
What is the runtime of an ArrayDeque remove(i) operation?
O(min{i, n-i}), amortized.
Recall that since the ArrayDeque is implemented by a circular array, once you remove item i you can either shift the (i-1) items preceding i to the right, or shift the (n-i) items following i to the left, whichever is smaller.
How much extra space is needed for an ArrayDeque to store n elements?
O(n) extra space.
An ArrayDeque uses an array as backing storage, and that means that our array can be as much as 3 times the size of the elements it is storing, before we resize it to twice the number of elements.
What index i leads to the worst-case running time for the add(i,x) operation in an ArrayDeque?
i=n/2, that is, adding to the middle of an ArrayDeque is the worst.
This is because min{i, n-i} is maximized when i=n/2.
Pros of an ArrayDeque
Good (O(1) amortized) add and remove from both ends, which makes it a good implementation of the Deque interface.
Fairly straight-forward implementation.
Good (O(1)) get and set methods, so good for random access.
Cons of an ArrayDeque
Amortized time, which isn’t always ideal.
O(n) extra space used when storing n elements.
What index i leads to the best-case runtime of the ArrayDeque add(i,x) operation?
Either i=0 or i=n-1.
These lead to O(1) runtimes.
What makes the runtimes of the ArrayDeque’s add(i,x) and remove(i) operations amortized?
The copying in the resize() method.
(Arrays are of fixed length; therefore, any array-based List implementation must occasionally resize this array as we need more space. When we resize, we create a new array and copy all n elements from the original array into the new array, and this copying takes O(n) time that is amortized over all adds/removes that happened since the last add/remove.)
What is the backing storage of an ArrayDeque?
an array a to store the elements
an integer n for the size
an integer j to store the index of the first element
(a.k.a. a “circular array”)
