Java 双端队列实现:无法在方法 addLast() 中找到逻辑错误

Question

我的代码：

注意：readInt(( 和 readString(( 等函数是普林斯顿大学 algs4.jar 包的一部分。

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());
      }
    }
  }
}

我正在将 Deque 实现为链接节点的集合。每个节点都有三个特征 - 内容、指向下一项的链接和指向上一项的链接。类变量的前面和后面分别是第一个和最后一个元素的指针。

当我使用我的测试客户端运行该程序时，我发现这里的方法 addLast(Item( 将项目插入前面而不是后面。

为什么会这样？我的逻辑有什么问题？

Answer 1

这是

你的addLast代码

  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++;
  }

请注意，当有一个节点时，front和back指向同一节点。然后，当您将第二个节点添加到后面时，您将back.prev分配给newnode，这是错误的。它应该是：

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

Answer 2

这是你的代码

 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
      //**Here is the issue**
      newnode.next = back;
      newnode.prev = null;
      back.prev = newnode;
      back = newnode;
    }
    numberOfItems++;
  }

而不是

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

它应该是

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

希望这有帮助