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 实现为 linked 节点的集合。每个节点具有三个特征 - 内容，link 指向下一项，link 指向前一项。 class 变量 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;

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

希望对您有所帮助

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

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

java

linked-list

deque