Two Deques, Side by Side

We now have two implementations of the same Deque contract:

Operation	`LinkedDeque`	`ArrayDeque`
`addFirst`	$O (1)$	$O (1)$ amortized
`addLast`	$O (1)$	$O (1)$ amortized
`removeFirst`	$O (1)$	$O (1)$
`removeLast`	$O (1)$	$O (1)$
`getFirst`	$O (1)$	$O (1)$
`getLast`	$O (1)$	$O (1)$
`isEmpty`	$O (1)$	$O (1)$

LinkedDeque needed a doubly linked list: the prev link lets removeLast run in $O (1)$ . ArrayDeque needed the same circular array as ArrayQueue, with front moving in both directions.

The memory trade-off is the one we saw with the stacks and the queues, except that each node now stores two links, and the linked version also has the two sentinel nodes.

So which one should you use? Either one works. A client should program to the interface, declaring Deque<T> without caring which class is behind it.