Java Double-Ended Queue implementation: Unable to find logic error in method addLast()

Question

My code:

NOTE: Functions like readInt() and readString() are part of Princeton University's algs4.jar package.

import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class Deque < Item > implements Iterable < Item > {

  private Node < Item > front;
  private Node < Item > back;
  private int numberOfItems;

  private class Node < Item > {
    Item item;
    Node < Item > next;
    Node < Item > prev;
  }

  public Deque() {
    front = null;
    back = null;
    numberOfItems = 0;
  }

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

  public int size() {
    return numberOfItems;
  }

  public void addFirst(Item item) {
    if (item == null) {
      // When a null element is entered
      throw new java.lang.NullPointerException("Item cannot be null");
    }
    Node < Item > newnode = new Node < Item > ();
    newnode.item = item;
    if (numberOfItems == 0) {
      // When there are no elements
      front = newnode;
      back = newnode;
    } else {
      // When there are >=1 elements
      newnode.prev = front;
      newnode.next = null;
      front.next = newnode;
      front = newnode;

    }
    numberOfItems++;
  }

  public void addLast(Item item) {
    if (item == null) {
      // When a null element is entered
      throw new java.lang.NullPointerException("Item cannot be null");
    }
    Node < Item > newnode = new Node < Item > ();
    newnode.item = item;
    if (numberOfItems == 0) {
      // When there are no elements
      front = newnode;
      back = newnode;
    } else {
      // When there are >=1 elements
      newnode.next = back;
      newnode.prev = null;
      back.prev = newnode;
      back = newnode;
    }
    numberOfItems++;
  }

  public Item removeFirst() {
    if (numberOfItems == 0) {
      // When the deque is empty
      throw new NoSuchElementException("No item to remove");
    }
    Item oldfirst = front.item;
    if (numberOfItems == 1) {
      front = null;
      back = null;
    } else {
      front = front.prev;
    }
    numberOfItems--;
    return oldfirst;
  }

  public Item removeLast() {
    if (numberOfItems == 0) {
      // When deque is empty
      throw new NoSuchElementException("No item to remove");
    }
    Item oldlast = back.item;
    if (numberOfItems == 1) {
      front = null;
      back = null;
    } else {
      back = back.next;
    }
    numberOfItems--;
    return oldlast;
  }

  public Iterator < Item > iterator() {
    return new ListIterator();
  }

  private class ListIterator implements Iterator < Item > {
    private Node < Item > current = front;

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

    public void remove() {
      throw UnsupportedOperationException("remove is unsupported");
    }

    public Item next() {
      Item item = current.item;
      current = current.prev;
      return item;
    }
  }

  public static void main(String[] args) {
    Deque < String > deq = new Deque();
    String word;
    while (!StdIn.isEmpty()) {
      String cmd = StdIn.readString();
      if (cmd.equals("af")) {
        word = StdIn.readString();
        deq.addFirst(word);
      } else if (cmd.equals("al")) {
        word = StdIn.readString();
        deq.addFirst(word);
      } else if (cmd.equals("rf")) {
        deq.removeFirst();
      } else if (cmd.equals("rl")) {
        deq.removeLast();
      } else if (cmd.equals("noi")) {
        StdOut.println(deq.size());
      }
    }
  }
}

I'm implementing the Deque as a collection of linked nodes. Each node has three characteristics- the content, a link to the next item and a link to the previous item. The class variables front and back are pointers for the first and the last element respectively.

When I was ran the program with my test client, I discovered that the method addLast(Item) here, inserts the item in the front instead of the rear.

Why is this happening? What is wrong with my logic?

My guess is that you swapped the roles of the front and back nodes. You should check your logic throughout, as similar problems may be present in all your methods. — Tim Biegeleisen

Dat Nguyen Dat Nguyen · Accepted Answer · 2017-06-22T11:26:17

Here is your addLast code

  public void addLast(Item item) {
    if (item == null) {
      // When a null element is entered
      throw new java.lang.NullPointerException("Item cannot be null");
    }
    Node < Item > newnode = new Node < Item > ();
    newnode.item = item;
    if (numberOfItems == 0) {
      // When there are no elements
      front = newnode;
      back = newnode;
    } else {
      // When there are >=1 elements
      newnode.next = back;
      newnode.prev = null;
      back.prev = newnode;
      back = newnode;
    }
    numberOfItems++;
  }

Note that when there's one node, the front and the back point to the same node. Then when you add the second node to the back, you assign back.prev to newnode, which is wrong. It should have been:

back.next = newnode;
newnode.prev = back;
back = newnode;

Java Double-Ended Queue implementation: Unable to find logic error in method addLast()

2 Answers