Deque Implementation in Java

Question

Please review my Deque implementation in Java and suggest ways of improving this.

    public class DequeImplementation<T> {
    private QueueNode<T> first;
    private QueueNode<T> last;
    private int size;

    private static class QueueNode<T> {
        private T val;
        private QueueNode<T> next;
        private QueueNode<T> prev;

        public QueueNode(T val) {
            this.val = val;
            this.next = null;
            this.prev = null;
        }

        public T getValue() {
            return val;
        }

        public void setNext(QueueNode<T> nextNode) {
            next = nextNode;
        }

        public QueueNode<T> getNext() {
            return next;
        }

        public void setPrev(QueueNode<T> prevNode) {
            prev = prevNode;
        }

        public QueueNode<T> getPrev() {
            return prev;
        }

        public String toString() {
            if(val == null) {
                return "null";
            }
            return val.toString();
        }
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void offerLast(T val) {
        QueueNode<T> cur = new QueueNode(val);
        if(size == 0) {
            cur.setNext(first);
            first = cur;
            last = cur;
            size++;
            return;
        }

        last.setNext(cur);
        cur.setPrev(last);
        last = cur;
        size++;
    }

    public void offerFirst(T val) {
        QueueNode<T> cur = new QueueNode(val);
        if(size == 0) {
            cur.setNext(first);
            first = cur;
            last = cur;
            size++;
            return;
        }

        cur.setNext(first);
        first.setPrev(cur);
        first = cur;
        size++;
    }

    public T peekLast() {
        if(isEmpty()) {
            return null;
        }
        return last.getValue();
    }

    public T peekFirst() {
        if(isEmpty()) {
            return null;
        }
        return first.getValue();
    }

    public QueueNode<T> pollFirst() {
        if(isEmpty()) {
            return null;
        }

        QueueNode<T> cur = first;
        first = first.getNext();
        if(first != null) {
            first.setPrev(null);
        }
        size--;
        return cur;
    }

    public QueueNode<T> pollLast() {
        if(isEmpty()) {
            return null;
        }

        QueueNode<T> cur = last;
        last = last.getPrev();
        if(last != null) {
            last.setNext(null);
        }
        size--;
        return cur;
    }

    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    @Override
    public String toString() {
        if(size == 0) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder("null<-");
        QueueNode<T> cur = first;
        sb.append(cur.getValue() + "<-");

        while(cur.getNext() != null && !cur.equals(last)) {
            sb.append(cur.getNext().getValue() + "<-");
            cur = cur.getNext();
        }

        sb.append("null");
        return sb.toString();
    }

    public static void main(String[] args) {
        DequeImplementation<Integer> dq = new DequeImplementation<>();
        System.out.println(dq.size());
        System.out.println(dq.pollLast()); //returns null
        System.out.println(dq);
        dq.offerLast(100);
        dq.offerFirst(10);
        dq.offerFirst(1);
        System.out.println(dq.pollFirst());
        System.out.println(dq);
        System.out.println(dq.size());
        System.out.println(dq.peekLast());
        System.out.println(dq.pollLast());
        System.out.println(dq);
        System.out.println(dq.size());
        System.out.println(dq.pollFirst());
        System.out.println(dq.pollLast()); //returns null
        dq.clear();
        System.out.println(dq.size());
    }   
}

Answer 1

I have embedded my comments straight in the code:

import java.util.Objects;

// 'Implementation' does not provide any more information on this class.
// Remove it, so less typing.
//public class DequeImplementation<T> {
public class Deque<T> {

    private QueueNode<T> first;
    private QueueNode<T> last;
    private int size;

    // You can add 'final' if you WANT:
    private static final class QueueNode<T> {

        private T val;
        private QueueNode<T> next;
        private QueueNode<T> prev;

        // You don't really need 'public' since the class is the inner private
        // static class:
        /*public*/ QueueNode(T val) {
            this.val = val;
            // Reference fields are 'null' by default:
            //this.next = null;
            //this.prev = null;
        }

        // Remove 'public' as well:
        /*public*/ T getValue() {
            return val;
        }

        /*public*/ void setNext(QueueNode<T> nextNode) {
            next = nextNode;
        }

        /*public*/ QueueNode<T> getNext() {
            return next;
        }

        /*public*/ void setPrev(QueueNode<T> prevNode) {
            prev = prevNode;
        }

        /*public*/ QueueNode<T> getPrev() {
            return prev;
        }

        // Here we need 'public'.
        public String toString() {
            // if (val == null) {
            //    return "null";
            //}
            //return val.toString();
            // Does exactly the same as above 3 lines:
            return Objects.toString(val);
        }
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void offerLast(T val) {
        QueueNode<T> cur = new QueueNode(val);
        if (size == 0) {
            first = last = cur;
            size = 1;
            return;
        }

        last.setNext(cur);
        cur.setPrev(last);
        last = cur;
        size++;
    }

    public void offerFirst(T val) {
        QueueNode<T> cur = new QueueNode(val);
        if (size == 0) {
            first = last = cur;
            size = 1;
            return;
        }

        cur.setNext(first);
        first.setPrev(cur);
        first = cur;
        size++;
    }

    public T peekLast() {
        if (isEmpty()) {
            return null;
        }
        return last.getValue();
    }

    public T peekFirst() {
        if (isEmpty()) {
            return null;
        }
        return first.getValue();
    }

    // No reason to return a node since everything the user can do with it is
    // to ask its value; return the value:
    // public QueueNode<T> pollFirst() {
    public T pollFirst() {
        if (isEmpty()) {
            return null;
        }

        QueueNode<T> cur = first;
        first = first.getNext();
        if (first != null) {
            first.setPrev(null);
        }
        size--;
        return cur.getValue();
    }

    // Same argument as in 'pollFirst':
    public T pollLast() {
        if (isEmpty()) {
            return null;
        }

        QueueNode<T> cur = last;
        last = last.getPrev();
        if (last != null) {
            last.setNext(null);
        }
        size--;
        return cur.getValue();
    }

    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    // This is a matter of taste, yet I don't quite like your idea to prepend
    // and append the output with 'null'. Think what the user sees if he really
    // has null values in the deque..a
    @Override
    public String toString() {
        if (size == 0) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder("[");
        sb.append(first.getValue());
        QueueNode<T> node = first.getNext();

        while (node != null) {
            sb.append(" -> ").append(node.getValue());
            node = node.getNext();
        }

        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        Deque<Integer> dq = new Deque<>();
        System.out.println(dq.size());
        System.out.println(dq.pollLast()); //returns null
        System.out.println(dq);
        dq.offerLast(100);
        dq.offerFirst(10);
        dq.offerFirst(1);
        System.out.println(dq.pollFirst());
        System.out.println(dq);
        System.out.println(dq.size());
        System.out.println(dq.peekLast());
        System.out.println(dq.pollLast());
        System.out.println(dq);
        System.out.println(dq.size());
        System.out.println(dq.pollFirst());
        System.out.println(dq.pollLast()); //returns null
        dq.clear();
        System.out.println(dq.size());
    }
}

Hope that helps.

Answer 2

The one thing worth mentioning is code that you are not showing - like: there are no unit tests for this. I am coming from the fact that you have "some" testing code in your main method.

But that is simply the wrong approach. Most of those things just print stuff. It needs your sharp eye to notice when it would be printing an unexpected output.

Long story short: such code is perfect for writing unit-tests for it.

( if you wrote unit-tests; fine ... but: most people I know that still put test code into a main() method are not writing unit tests; and that's a shame )