我正在 Java 中使用单向链表实现双端队列。我的 addLast() 不工作

Question

我正在 Java 中使用单向链表实现双端队列。我的 addFirst() 功能工作正常，但 addLast() 不工作。

每当我调用 addLast() 时，我都会收到以下错误消息：

java.lang.NullPointerException

Answer 1

你的最后一个是null。

当您将它分配给 old_last 时，old_last 也为 null。

所以当你调用old_last.next时，NPE会抛出。

Answer 2

为您的节点 class 提供一个构造函数将有助于保持您的代码简短和干爽：

private class Node {
  Item item;
  Node next;
  private Node(Item item, Node next) {
    if (item == null) throw new NullPointerException();
// 'this' refers to the created instance and helps distinguish the field from the param
    this.item = item;  
    this.next = next;
  }
}

public void addFirst(Item item) {
  // creates a new Node before first so to speak and then repoints first to this node 
  first = new Node(item, first);   
  if (num_elements==0) last = first;
  num_elements++;
}

public void addLast(Item item) {
  if (num_elements == 0) {  
    // this will deal with the case (last==null) which causes the NPE
    addFirst(item);
    return;
  }
  last.next = new Node(item, null);
  last = last.next;
  num_elements++;
}

除此之外，单向链表并不是双端队列的理想数据结构。虽然在两端添加是 O(1)，但从后面删除将是 O(N)!

我正在 Java 中使用单向链表实现双端队列。我的 addLast() 不工作

I'm implementing a deque using singly linked list in Java. My addLast() is not working

java

linked-list

stack

queue

deque