Java双端队列实现: Unable to find logic error in method 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());
      }
    }
  }
}

我将双端队列实现为链接节点的集合。每个节点具有三个特征——内容、到下一项的链接以及到前一项的链接。类变量 front 和 back 分别是第一个和最后一个元素的指针。

当我使用测试客户端运行该程序时，我发现这里的方法 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;