我正在使用Java中的单链表实现deque。我的addLast（）不起作用

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

我正在使用Java中的单链表实现deque。我的addFirst()函数工作正常,但addLast()不起作用。

Whenever I call addLast(), I got the following error message:

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

java.lang.NullPointerException

2 个解决方案

#1

Giving your Node class a constructor will help to keep your code short and DRY:

为Node类提供构造函数将有助于保持代码简短和干燥:

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

That aside, a singly linked list is not the ideal data structure for a deque. While adding is O(1) on both ends, removing from the back would be O(N)!

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

#2

Your last is null at first.

你的姓氏一开始是空的。

When you assign it to old_last, old_last is null too.

将它分配给old_last时,old_last也为null。

So when you call old_last.next, NPE will throw.

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