Null pointer exception in Deque implementation

Question

I am learning Java, and implementing a Deque data structure. This is the Node class:

import java.util.*;

public class Deque<Item> implements Iterable<Item> {
    private Node sentinel;

    private class Node {
        Item item;
        Node next;
        Node previous;
        Node(Item value) {
            item = value;
            next = this;
            previous = this;
        }
    }

    public Deque(Item item)                           // construct an empty deque
    {
        Node sentinel = new Node(item);
    }

    public boolean isEmpty()                 // is the deque empty?
    {
        return (size() == 0);
    }
    public int size()                        // return the number of items on the deque
    {
        System.out.println("size");
        if (sentinel.next == sentinel) {
            System.out.println("empty");}
        return 0;

//        }
//        int count = 0;
//        Node temp = sentinel;
//        while (temp != sentinel)
//        {
//            count += 1;
//            temp = temp.next;
//        }
//        return count;
    }
    public void addFirst(Item item)          // insert the item at the front
    {
        if (item == null) {
            throw new java.util.NoSuchElementException();
        }
        Node a = new Node(item);
        if (isEmpty())
        {
            System.out.println("Hello world");
            sentinel.next = a;
            a.previous = sentinel;
        }
        else
        {
            sentinel.next.previous = a;
            sentinel.next = a;
            a.previous = sentinel;
        }
    }
    public void addLast(Item item)           // insert the item at the end
    {
        if (item == null)
            throw new java.util.NoSuchElementException();
        Node a = new Node(item);
        sentinel.previous = a;
        a.next = sentinel;
    }
    public Item removeFirst()                // delete and return the item at the front
    {
        if (isEmpty())
            throw new UnsupportedOperationException();
        Item value = sentinel.next.item;
        sentinel.next = sentinel.next.next;
        sentinel.next.previous = sentinel;
        return value;
    }
    public Item removeLast()                 // delete and return the item at the end
    {
        if (isEmpty())
            throw new UnsupportedOperationException();
        Item value = sentinel.previous.item;
        sentinel.previous = sentinel.previous.previous;
        sentinel.previous.next = sentinel;
        return value;
    }
    public Iterator<Item> iterator()         // return an iterator over items in order from front to end
    {
        return new DequeueIterator();
    }

    private class DequeueIterator implements Iterator<Item>
    {
        private Node current = sentinel;
        public boolean hasNext() {
            return current != null;
        }
        public void remove() {}
        public Item next() {
            Item value = current.item;
            current = current.next;
            return value;
        }

    }
    public static void main(String[] args)   // unit testing
    {
        System.out.println(Thread.currentThread().getStackTrace());
        Deque<Integer> d = new Deque<Integer>(0);
        System.out.println(d.isEmpty());
                System.out.println(Thread.currentThread().getStackTrace());
//        d.addFirst(10);

//        System.out.println(d.size());
        // System.out.println(d.removeLast());
    }
}

Then when checking the size of the Deque as following:

public class Deque<Item> implements Iterable<Item> {
    public Deque()                           // construct an empty deque
    {
        Node sentinel = new Node(null);
        if (sentinel.next == sentinel)
            System.out.println("empty");
    }
}

The compiler error is NullPointerException. Is it due to the initialization of Node(null)? If yes, how can I input a zero value for the generic Item?

Stacktrace:

java.lang.NullPointerException
    at Deque.size(Deque.java:29)
    at Deque.isEmpty(Deque.java:24)
    at Deque.main(Deque.java:111)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
    at java.lang.reflect.Method.invoke(Method.java:597)
    at edu.rice.cs.drjava.model.compiler.JavacCompiler.runCommand(JavacCompiler.java:272)

And line 29 is:

    if (sentinel.next == sentinel)

NullPointerException is a run time error. Give us the full stacktrace. — Sotirios Delimanolis
– Sotirios Delimanolis, Commented Apr 1, 2014 at 5:18
Can u please post ur complete code and stacktrace of exception — Sagar Gandhi
– Sagar Gandhi, Commented Apr 1, 2014 at 5:21

Sotirios Delimanolis · Accepted Answer · 2014-04-01 05:25:14Z

5

You're declaring a local variable called sentinel and assigning it instead of using the instance field and assigning it.

public Deque(Item item)                           // construct an empty deque
{
    Node sentinel = new Node(item);
}

should be

public Deque(Item item)                           // construct an empty deque
{
    this.sentinel = new Node(item);
}

otherwise the instance variable sentinel remains null and causes a NullPointerException when you try to dereference it

public int size()                        // return the number of items on the deque
{
    System.out.println("size");
    if (sentinel.next == sentinel) { // here
        System.out.println("empty");
    }
    return 0;
}

answered Apr 1, 2014 at 5:25

Sotirios Delimanolis

281k62 gold badges718 silver badges744 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dzung Nguyen Over a year ago

Thanks. How should I avoid this:Deque<Integer> d = new Deque<Integer>(0). (The zero)?

Sotirios Delimanolis Over a year ago

@DzungNguyen Is that meant to be the root value of the Deque? Don't do it when you initialize the Deque, do it when you first add an element to it. With this solution you'd have to make the appropriate changes to size so that the same NPE doesn't happen.

Jason · Accepted Answer · 2014-04-01 05:26:26Z

0

If you get a NullPointerException on the following line:

if (sentinel.next == sentinel)

then the only cause can possibly be that sentinel is null. This is because in the constructor for Deque, you are creating a new variable called sentinel, not using the one in the class.

answered Apr 1, 2014 at 5:26

Jason

11.8k3 gold badges45 silver badges48 bronze badges

Collectives™ on Stack Overflow

Null pointer exception in Deque implementation

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related