5 / 8 Dynamic Arrays, Linked Lists & Deques

Wrapping Around Six Slots

Open Data Structures implements ArrayDeque over a circular array with a backing array a, a head index j and a count n. Element i of the deque lives at a[(j + i) % a.length], and the single method add(i, x) shifts whichever side is shorter. Call its two end cases addFirst and addLast. Adding at the front runs j = (j == 0) ? a.length - 1 : j - 1 and then writes a[j] = x; adding at the back writes a[(j + n) % a.length] = x. Neither end case shifts anything.

Start from this state and run addLast(1), addLast(2), addLast(3), addLast(4), addFirst(9), addFirst(8).

Starting state: backing array of length 6, j = 0, n = 0 012 345 -- -- -- j = 0, n = 0

What are the physical contents of a[0..5] and the value of j at the end?

A

a = [9, 8, 1, 2, 3, 4], j = 4

B

a = [1, 2, 3, 4, 8, 9], j = 4

C

a = [8, 9, 1, 2, 3, 4], j = 0

D

a = [1, 2, 3, 4, 9, 8], j = 4