Documentation
The Java™ Tutorials
Download Ebooks
Download JDK
Search Java Tutorials
Hide TOC
Implementations
Set Implementations
List Implementations
Map Implementations
Queue Implementations
Deque Implementations
Wrapper Implementations
Convenience Implementations
Summary of Implementations
Questions and Exercises
Trail: Collections
Lesson: Implementations
« Previous • Trail • Next »

# Deque Implementations

The `Deque` interface, pronounced as "deck", represents a double-ended queue. The `Deque` interface can be implemented as various types of `Collections`. The `Deque` interface implementations are grouped into general-purpose and concurrent implementations.

## General-Purpose Deque Implementations

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.

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.

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.

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. For the `ArrayDeque` instance traversal use any of the following:

### foreach

The `foreach` is fast and can be used for all kinds of lists.

    ArrayDeque<String> aDeque = new ArrayDeque<String>();

    . . .
    for (String str : aDeque) {
        System.out.println(str);
    }

### Iterator

The `Iterator` can be used for the forward traversal on all kinds of lists for all kinds of data.

    ArrayDeque<String> aDeque = new ArrayDeque<String>();
    . . .
    for (Iterator<String> iter = aDeque.iterator(); iter.hasNext();  ) {
        System.out.println(iter.next());
    }

The `ArrayDeque` class is used in this tutorial to implement the `Deque` interface. The complete code of the example used in this tutorial is available in ``ArrayDequeSample``. Both the `LinkedList` and `ArrayDeque` classes do not support concurrent access by multiple threads.

## Concurrent Deque Implementations

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.

« Previous • Trail • Next »

Previous page: Queue Implementations
Next page: Wrapper Implementations