Java Deque without using any of the existing classes like LinkedList?

Question

Hi, I've got to write a very short bit of code on a deque, however I'm not sure how to write the code for the methods, if someone could help me with one of the methods, (eg. a method to add an object to the from of the deque) then that would get me started. I'm sure I could manage the rest of the methods, just at the moment I'm pretty stumped. Many thanks.

Answer 1

I'm not sure exactly what you're after, but the available methods for the Deque are listed in the Javadoc

Answer 2

Deques are usually implemented as doubly linked lists. You implement a doubly linked list by keeping track of the first and last element in the list and letting each element keep track of its predecessor and successor.

public class Deque<T> {
    private class Node {
        Node(T value) {
            this.value = value;
        }
        T value;
        Node next, prev;
    }

    private Node first, last;

    public void addFront(T value) {
        Node oldFirst = first;
        first = new Node(value);

        // The old first item is now the second item, so its the successor of
        // the new first item
        first.next = oldFirst;

        // if first was null before, that means the deque was empty
        // so first and last should both point to the new item
        if(oldFirst == null) {
            last = first;
        } else {
            // If there previously was a first element, this element is
            // now the second element and its prev field should point to
            // the new first item
            oldFirst.prev = first;
        }
    }
}