Deque Implementations

Question 1

Deque

Answer 1

The Deque interface, pronounced as “deck”, represents a double-ended queue. The Deque interface can be implemented as various types of Collections.

Question 2

Type of Deque Impl

Answer 2

The Deque interface implementations are grouped into general-purpose and concurrent implementations.

Question 3

General-Purpose Deque Implementations

Answer 3

The general-purpose implementations include LinkedList and ArrayDeque classes.
The Deque interface supports insertion, removal and retrieval of elements at both ends.

The ArrayDeque class is the resizable array implementation of the Deque interface,

whereas the LinkedList class is the list implementation.

Question 4

The basic operations in the Deque interface

Answer 4

The basic insertion, removal and retieval operations in the Deque interface addFirst, addLast, removeFirst, removeLast, getFirst and getLast. The method addFirst adds an element at the head whereas addLast adds an element at the tail of the Deque instance.

Question 5

Deque Note/Diff (ArrayDeque & LinkedList )

Answer 5

The LinkedList implementation is more flexible than the ArrayDeque implementation. LinkedList implements all optional list operations. null elements are allowed in the LinkedList implementation but not in the ArrayDeque implementation.

	LinkedList lldeque = new LinkedList<>();

	ArrayDeque adeque = new ArrayDeque<>();

In terms of efficiency, ArrayDeque is more efficient than the LinkedList for add and remove operation at both ends. The best operation in a LinkedList implementation is removing the current element during the iteration. LinkedList implementations are not ideal structures to iterate.

The LinkedList implementation consumes more memory than the ArrayDeque implementation.

Both the LinkedList and ArrayDeque classes do not support concurrent access by multiple threads.

Question 6

Concurrent Deque Implementations

Answer 6

The LinkedBlockingDeque class is the concurrent implementation of the Deque interface. If the deque is empty then methods such as takeFirst and takeLast wait until the element becomes available, and then retrieves and removes the same element.