dw19
dw19

Reputation: 73

NullPointerException while implementing Queue using Linked List

I am following Coursera Algorithm 1 course, and right now implementing Queues using linked list, but getting a NullPointerException. Please help me out.

package algo_packages;

public class QueueLinkedList {
    private Node first, last;
    public class Node{
        String item;
        Node next;
    }

    public QueueLinkedList(){
        first = null;
        last = null;
    }
    public boolean isEmpty(){
        return first == last;
    }
    public void enqueue(String item){
        Node oldLast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if(isEmpty()){
            first = last;
        }
        else {
            oldLast.next = last;
        }
    }
    public String dequeue(){
        String item = first.item;
        first = first.next;
        if (isEmpty()) last = null;
        return item;
    }
}

I am getting the exception at:

oldLast.next = last;

oldLast.next caused the NullPointerException when I tried to debug the program.

Upvotes: 0

Views: 459

Answers (2)

brso05
brso05

Reputation: 13232

When you check isEmpty() it always returns false for enqueue because you are setting last to a new Node() which will never equal first. You don't need to check if list isEmpty() because if list is empty then first == last so you don't need to assign first = last because they are already equal. Try this:

public void enqueue(String item){
    Node oldLast = last;
    last = new Node();
    last.item = item;
    last.next = null;
    if(oldLast != null)
    {
        oldLast.next = last;
    }
    else
    {
        first = last;
    }
}

Upvotes: 0

Eran
Eran

Reputation: 394156

The first time you enqueue an item isEmpty() returns false, since it checks if first==last, but first is still null and last is no longer null (since you already assigned the new Node to it). This brings you to access oldLast.next when oldLast is null, hence the NullPointerException.

A possible fix :

public void enqueue(String item)
{
    Node oldLast = last;
    Node newNode = new Node();
    newNode.item = item;
    newNode.next = null;
    if(isEmpty()) { // last is not assigned yet, so isEmpty returns correct result
        last = newNode;
        first = last;
    } else {
        last = newNode;
        oldLast.next = last;
    }
}

Upvotes: 1

Related Questions