DualArrayDeque

Question 1

What is the runtime of the DualArrayDeque get(i) operation?

Answer 1

O(1)

Question 2

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

Answer 2

O(1)

Question 3

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

Answer 3

O(min{i, n-i}), amortized

Question 4

What is the runtime of the DualArrayDeque remove(i) operation?

Answer 4

O(min{i, n-i}), amortized.

Question 5

How much extra space does a DualArrayDeque use to store n elements?

Answer 5

O(n)

Question 6

What is the backing storage of a DualArrayDeque?

Answer 6

2 ArrayStacks.

Question 7

What index i yields the worst-case runtime for the DualArrayDeque add(i,x) operation?

Answer 7

i=n/2

In this case, the runtime is O(n), since min{i, n-i}=n/2 when i=n/2.

Question 8

What index i yields the best-case runtime for the DualArrayDeque add(i,x) operation?

Answer 8

Both i=0 and i=n-1.

These have O(1) runtime.

Question 9

Pros of DualArrayDeque

Answer 9

Good (O(1) amortized) runtime to add and remove from both ends (so, a good implementation of the Deque interface)
Good (O(1)) random access.

Question 10

Cons of DualArrayDeque

Answer 10

Not good to add/remove from the middle.
O(n) extra space required.
More complex than ArrayDeque, yet doesn’t give an improvement to runtime.