A mutable, generic deque, implemented as a doubly-linked list in Java for didactic purposes (download zip and extract, compile with javac Deque.java DequeDemo.java, run with java DequeDemo)

Deque.java

/* a deque (double-ended queue)
 * implemented as a mutable, generic, doubly-linked list in Java
 *
 * what do we mean by this?
 *   deque: a Double-Ended QUEue. a data structure supporting fast insertion or
 *     removal at either end, used in various algorithms and data-sharing
 *     techniques.
 *
 *   mutable: the structure contains state which may be altered by various
 *     mutating operations. for example, when we enqueue an element at the
 *     front, the operation does not return a new deque containing the
 *     additional element (and preserving the original deque) but rather changes
 *     the deque's internal structure to contain the new element. this is the
 *     common way of working in object-oriented programming and indeed OOP seems
 *     uniquely suited to constructing programs as interacting networks of
 *     stateful elements. nonetheless, this complicates reasoning about our
 *     programs: we must now concern ourselves with not merely values but with
 *     evolutions of values over time, and (potentially) their interaction over
 *     non-deterministically sequenced threads of execution. hic sunt dracones.
 *
 *   generic: just as described before, the deque type is parametrically
 *     polymorphic over the type of contained elements.
 *
 *   doubly-linked: each node will store two links, to the next and the previous
 *     elements in the list. this will permit fast in-place reversal as well as
 *     the required deque operations.
 */

// some imports we'll need
import java.util.Iterator;
import java.util.Collection;
import java.util.NoSuchElementException;

// just as before
public final class Deque<T> implements Iterable<T> {
    // default constructor: an empty deque
    public Deque()
    {
        head = tail = null;
    }

    // key deque operations
    // for consistency, we'll use the "stack-like" terminology we used before,
    //   but this time we'll distinguish which end of the deque we're acting on

    // first, accessors for the first and last elements (again, we'll throw
    //   NoSuchElementException on an empty deque)
    public T front() throws NoSuchElementException
    {
        if (head == null)
            throw new NoSuchElementException("front() on empty deque");
        return head.value;
    }

    public T back() throws NoSuchElementException
    {
        if (head == null)
            throw new NoSuchElementException("back() on empty deque");
        return tail.value;
    }

    // next, operations to add new elements at the front or the back 
    public void pushFront(T value)
    {
        // the new head contains the given value; it's prev pointer is null
        //   (it's the new first element) and it's next pointer is the old
        //   head of the deque
        ListNode newHead = new ListNode(value, null, head);
        // set our old head's prev pointer to the new head, or (if we're empty)
        //   set our head and tail to the new node
        if (head != null) {
            head.prev = newHead;
            // set our head pointer to the new head
            head = newHead;
        } else {
            head = tail = newHead;
        }
    }

    public void pushBack(T value)
    {
        // this is the mirror image case of pushFront
        ListNode newTail = new ListNode(value, tail, null);
        if (tail != null) {
            tail.next = newTail;
            tail = newTail;
        } else {
            head = tail = newTail;
        }
    }

    // operations to remove the element at the front or back (returning
    //   the value).
    // these throw NoSuchElementException on an empty Deque
    public T popFront()
    {
        T result = front();
        head = head.next;
        return result;
    }

    public T popBack()
    {
        T result = back();
        tail = tail.prev;
        return result;
    }

    // some general random-access collection operations
    public boolean isEmpty()
    {
        return head == null;
    }

    public int size()
    {
        // this looks just like the singly-linked case, though we could
        //   have also walked the list backwards
        int count = 0;
        ListNode node = head;
        while (node != null) {
            ++count;
            node = node.next;
        }
        return count;
    }

    // get an element by index (zero-based, from the front)
    public T get(int index) throws IndexOutOfBoundsException
    {
        if (index < 0)
            throw new IndexOutOfBoundsException("negative index to get()");
        ListNode node = head;
        while (node != null && index > 0) {
            --index;
            node = node.next;
        }
        if (node == null)
            throw new IndexOutOfBoundsException("invalid index to get()");
        return node.value;
    }

    // get an element by index (zero-based, from the back)
    // the mirror-image case, enabled by a doubly-linked list
    public T getFromBack(int index) throws IndexOutOfBoundsException
    {
        if (index < 0)
            throw new IndexOutOfBoundsException("negative index to get()");
        ListNode node = tail;
        while (node != null && index > 0) {
            --index;
            node = node.prev;
        }
        if (node == null)
            throw new IndexOutOfBoundsException("invalid index to get()");
        return node.value;
    }

    // just for name symmetry, if a client wants to be explicit
    public T getFromFront(int index) throws IndexOutOfBoundsException
    {
        return get(index);
    }

    // this time around, our reverse operation will change the deque in place
    // this can be done quite quickly!
    public void reverse()
    {
        ListNode node = head;
        while (node != null) {
            // swap the node's next and prev, then advance to the next node
            //   (in the original order)
            ListNode next = node.next;
            node.next = node.prev;
            node.prev = next;
            node = next;
        }

        // now swap the head and tail, using node as a temporary
        node = tail;
        tail = head;
        head = node;
    }

    // instead of a copying "concat" function, we'll have an "append" function
    //   that copies the contents of another deque onto our tail.
    // this will be enabled by our Iterable support
    public void appendBack(Deque<? extends T> other)
    {
        // I blew up on this the first time, and its a key example of the
        //   problems with mutable state: what happens if we get ourselves as
        //   other? i.e. this == other? well, without a special case, we end up
        //   reading one element at a time from ourselves and pushing it to our
        //   own tail: we keep growing as we push, and so our iteration over
        //   other aka this never ends! an infinte loop, repeating our own
        //   elements onto our tail.
        if (other == this) {
            // clone ourselves and append the clone
            appendBack(new Deque<T>(other));
        } else {
            for (T v : other)
                pushBack(v);
        }
    }

    // and the mirror-image (but this time, we'll need the reverse iterator
    //   for other!)
    public void appendFront(Deque<? extends T> other)
    {
        if (other == this) {
            appendFront(new Deque<T>(other));
        } else {
            Iterator<? extends T> rev = other.reverseIterator();
            while (rev.hasNext())
                pushFront(rev.next());
        }
    }

    // we'll again provide standard java iteration, with an inner class...
    public Iterator<T> iterator() 
    {
        return new ListIterator(head, true);
    }

    // ... as well as iteration in reverse order!
    public Iterator<T> reverseIterator() 
    {
        return new ListIterator(tail, false);
    }

    // I don't want to implement all of Collection for Deque, so I'm going
    //   to have an explicit Deque "copy constructor" that clones from another
    //   Deque. In likely defiance of Java convention, this is a "shallow" copy.
    public Deque(Deque<? extends T> other)
    {
        this(); // invoke default constructor
        for (T v : other)
            pushBack(v);
    }

    // finally, we'll provide a constructor that can build a Deque from
    //   any standard Collection of any type which
    //   is a subtype of T (including T itself); this is much easier now
    //   that we can pushBack()
    public Deque(Collection<? extends T> items)
    {
        this(); // invoke default constructor
        for (T v : items)
            pushBack(v);
    }

    // we'll again use a private inner class to describe the structure of
    //   our nodes; a Deque is then represented by references to the first and
    //   last nodes.
    private final class ListNode {
        public ListNode(T value, ListNode prev, ListNode next)
        {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }

        // two notes:
        //   first, this time these are not final: we're going to mutate them
        //   second, this time we have pointers in both directions
        public T value;
        public ListNode prev;
        public ListNode next;
    }

    // this private inner class is used to implement the Iterable<T> interface;
    // it must implement Iterator<T>.
    // this one takes an extra boolean parameter to control iteration direction,
    //   letting us re-use the same class both both directions
    private final class ListIterator implements Iterator<T> {
        public ListIterator(ListNode node, boolean forward)
        {
            this.node = node;
            this.forward = forward;
        }

        public boolean hasNext()
        {
            return node != null;
        }

        public T next() throws NoSuchElementException
        {
            if (node == null)
                throw new NoSuchElementException(
                        "next() on empty iterator");
            T val = node.value;
            if (forward)
                node = node.next;
            else
                node = node.prev;
            return val;
        }

        private ListNode node;
        private final boolean forward;
    }

    // this time, these aren't final: they're our key pieces of
    //   mutable internal state. we'll keep them private, and ensure that
    //   our public API carefully maintains their critical invariants.
    // namely: head is always either null (for an empty deque), or points to the
    //   "first" node in the deque; and, tail is always either null, or points
    //   to the "last" node in the deque. n.b. head is null iff tail is null.
    private ListNode head;
    private ListNode tail;
}

DequeDemo.java

import java.util.Iterator;
import java.util.Arrays;

class DequeDemo {
    public static void main(String[] args)
    {
        // an empty deque
        Deque<Object> empty = new Deque<>();
        System.out.println("empty.size() = " + empty.size());

        // build a list of numbers, statefully...
        Deque<Integer> nums = new Deque<>();
        for (int i = 1; i <= 4; ++i)
            nums.pushBack(i);

        System.out.println("nums.front() = " + nums.front());
        System.out.println("nums.back() = " + nums.back());
        System.out.println("nums.size() = " + nums.size());
        System.out.println("nums.get(1) = " + nums.get(1));
        System.out.println("nums.getFromBack(1) = " + nums.getFromBack(1));

        // copy nums onto its own tail:
        nums.appendBack(nums);
        for (int i : nums)
            System.out.print(i + ", ");
        System.out.println();

        // reverse nums in-place
        nums.reverse();
        for (int i : nums)
            System.out.print(i + ", ");
        System.out.println();

        // now print the reversed list in reverse, using reverseIterator()
        Iterator<Integer> rev = nums.reverseIterator();
        while (rev.hasNext())
            System.out.print(rev.next() + ", ");
        System.out.println();

        // stick stuff on the front, then demo pop at both ends
        //   and track the size (why not?)
        nums.appendFront(new Deque<Integer>(Arrays.asList(
                    new Integer[] { 7, 7, 7 })));
        System.out.println("nums.size() = " + nums.size());
        System.out.println("nums.popFront() = " + nums.popFront());
        System.out.println("nums.size() = " + nums.size());
        System.out.println("nums.popBack() = " + nums.popBack());

        for (int i : nums)
            System.out.print(i + ", ");
        System.out.println();
    }
}