Ovewriting toString method in deque class using generics

Question

I am trying to print the first and last elements in a deque using a toString method however I'm not entirely sure if I am overwriting the toString method correctly.

As far as I can tell, the methods all seem to behave correctly but I have no way of being able to tell as I am unable to see any readable output.

I am aware that there is already a deque interface, however this is part of an exercise in using generics in Java.

This piece of code should create a deque, be able to add values to the front of the deque, remove values from the front, add values to the rear and remove values from the rear.

Here's the class in question:

import java.util.Iterator;
import java.util.NoSuchElementException;

class Deque<T> implements Iterable<T> {
    private class Node<T> {
        public Node<T> left, right;
        private final T item;

        public Node(T item) {
            if (item == null) {
                throw new NullPointerException();
            }
            this.item = item;
        }

        public void connectRight(Node<T> other) {
            this.right = other;
            other.left = this;
        }
    }

    private class DequeIterator implements Iterator<T> {

        private Node<T> curr = head;

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

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            T item = curr.item;
            curr = curr.right;
            return item;
        }
    }

    private Node<T> head, tail;
    private int size;

    public Iterator<T> iterator() {
        return new DequeIterator();
    }

    public Deque() {
    }

    public int size() {
        return size;
    }

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

    public void checkInvariants() {
        assert size >= 0;
        assert size > 0 || (head == null && tail == null);
        assert (head == null && tail == null) || (head != null && tail != null);
    }

    public void addFirst(T item) {
        Node<T> prevHead = head;
        Node<T> newHead = new Node<T>(item);
        if (prevHead != null) {
            newHead.connectRight(prevHead);
        } else {
            tail = newHead;
        }
        head = newHead;
        size++;
        checkInvariants();
    }

    public void addLast(T item) {
        Node<T> newTail = new Node<T>(item);
        Node<T> prevTail = tail;
        if (prevTail != null) {
            prevTail.connectRight(newTail);
        } else {
            head = newTail;
        }
        tail = newTail;
        size++;
        checkInvariants();
    }

    public T removeFirst() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException();
        }
        size--;
        Node<T> prevHead = head;
        head = prevHead.right;
        prevHead.right = null;
        if (head != null) {
            head.left = null;
        }
        checkInvariants();
        return prevHead.item;
    }

    public T removeLast() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException();
        }
        size--;
        Node<T> prevTail = tail;
        tail = prevTail.left;
        prevTail.left = null;
        if (tail != null) tail.right = null;
        checkInvariants();
        return prevTail.item;
    }

    @Override
    public String toString() {
        Node<T> currTail = tail;
        Node<T> currHead = head;
        head = currHead.right;
        tail = currTail.left;

        StringBuilder builder = new StringBuilder();

        while (currHead != null && currTail != null) {
            builder.append(currHead.item + "\n");
        }

        return builder.toString();

    }

    public static void main(String[] args) {
        Deque<Double> d = new Deque<Double>();
        d.addFirst(1.0);
        System.out.println(d);
        d.addLast(1.0);
        //d.removeFirst();
        //d.removeLast();

        System.out.println(d.toString());

    }
}

Answer 1

First of all, you're setting the instance variables head and tail to their respective neighbours, which is definitely not what you're out to do. This leaves your queue in an inconsistent state, where the second element is the head, but it still has a left neighbour, the original head. Same thing for the tail. Generally the toString method shouldn't have side effects.

Neither currTail nor currHead ever change in your while-loop, so your condition currHead != null && currTail != null will always be true if the deque is non-empty. You'd have to set those variables in the loop, however, you don't need to iterate from both ends at once. Iterating from the start will be enough. And then, you can use a for loop, like this:

@Override
public String toString() {
    final StringJoiner stringJoiner = new StringJoiner("\n");

    for (Node<T> node = head; node != null; node = node.right) {
        stringJoiner.add(node.item.toString());
    }

    return stringJoiner.toString();
}

This sets the variable node to it's right neighbour after every iteration, and if the deque is empty, node will be null from the get-go and the loop will not be entered as is expected.

This is just the more concise (In my opinion) version of this:

@Override
public String toString() {
    final StringJoiner stringJoiner = new StringJoiner("\n");

    Node<?> node = head;

    while (node != null) {
        stringJoiner.add(node.item.toString());
        node = node.right;
    }

    return stringJoiner.toString();
}

which is basically your attempt, just fixed.

Not that I've used a StringJoiner instead of a StringBuilder, as it allows you to set a delimeter that is used between each String, which is exactly what you're doing.