Zhengxi Tan Zhengxi Tan - 10 months ago 54
Java Question

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

I'm implementing a deque using singly linked list in Java. My

function is working fine, but
is not working.

Whenever I call
, I got the following error message:


This is my function implementations

Answer Source

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

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;

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

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)!