ArrayDeque

Question 1

What is the runtime of an ArrayDeque get(i) operation?

Answer 1

O(1)

Question 2

What is the runtime of an ArrayDeque set(i,x) operation?

Answer 2

O(1)

Question 3

What is the runtime of an ArrayDeque add(i,x) operation?

Answer 3

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.

Question 4

What is the runtime of an ArrayDeque remove(i) operation?

Answer 4

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.

Question 5

How much extra space is needed for an ArrayDeque to store n elements?

Answer 5

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.

Question 6

What index i leads to the worst-case running time for the add(i,x) operation in an ArrayDeque?

Answer 6

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.

Question 7

Pros of an ArrayDeque

Answer 7

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.

Question 8

Cons of an ArrayDeque

Answer 8

Amortized time, which isn’t always ideal.

O(n) extra space used when storing n elements.

Question 9

What index i leads to the best-case runtime of the ArrayDeque add(i,x) operation?

Answer 9

Either i=0 or i=n-1.

These lead to O(1) runtimes.

Question 10

What makes the runtimes of the ArrayDeque’s add(i,x) and remove(i) operations amortized?

Answer 10

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.)

Question 11

What is the backing storage of an ArrayDeque?

Answer 11

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”)