The last of the core interfaces in the collection framework is the Deque interface (pronounced “Deck”). A Deque is a collection that allows us to manipulate elements from both the front and end of the collection.

The Deque interface has two types of methods for manipulating the front and back of the collection.

The following methods throw an exception when:

• addFirst(), addLast() - there is no space to add an element.
• removeFirst(), removeLast() - there is no element to remove.
• getFirst(), getLast() - there is no element to get.

The following methods return a special value:

• offerFirst(), offerLast() - false when there is no space to add an element.
• pollFirst(), pollLast() - null when there is no element to remove.
• peekFirst(), peekLast() - null when there is no element to get.

A Deque has many implementations and we’ll focus on the LinkedList and ArrayDeque implementations. The LinkedList, although not the most optimized, is flexible enough to not only be used as a List and Queue but also a Deque. The ArrayDeque is the preferred implementation when needing to manipulate elements at the front and end of a collection.

Let’s look at a LinkedList implementation of a Deque:

Deque<String> stringDeque = new LinkedList<>();
stringDeque.addFirst("A"); // Front -> "A" <- end
stringDeque.offerFirst("B"); // Return `true` - front -> "B", "A" <- end
stringDeque.offerLast("Z"); // Returns `true` - front -> "B", "A", "Z" <- end

String a = stringDeque.removeFirst()  // Returns "B" - front -> "A", "Z"
String b = stringDeque.pollLast()  // Returns "Z" - front -> "A" <- back
String c = stringDeque.removeLast()  // Returns "A" - empty deque

String d = stringDeque.peekFirst()  // Returns null
String e = stringDeque.getLast() // Throws NoSuchElementException

In the example above we:

• Called addFirst(), offerFirst(), and offerLast() to add elements. Note that the offer() methods return a boolean.
• Called removeFirst(), pollLast(), and removeLast() to remove elements.
• Called peekFirst() and getLast() to get but not remove the element at the front and back of deque respectively.

We can iterate Deque from front to back using an enhanced for-loop and we can use the descendingIterator() method and use the Iterator returned to go from back to front.

// Assuming `stringDeque` has elements front -> "Mike", "Jack", "John" <- back
Iterator<String> descItr = stringDeque.descendingIterator();

while(descItr.hasNext()) {
  System.out.println(descItr.next());
}
// OUTPUT TERMINAL:  "John", "Jack", "Mike"

Let’s practice creating a Deque and iterating through it.