Iterable Deque NullPointerException

Question

I am attempting to create an Deque class (Stack/Queue that can be added to and referenced at both ends) by implementing a doubly linked-list format.

import java.util.Iterator;

public class Deque implements Iterable {

Node first;
Node last;
int size;

public Deque()
{
    first = null;
    last = null;
    size = 2;

    first.next = last;
    last.prev = first;
}

private class Node
{
    Node next;
    Node prev;
    Item item;
}

private class ListIterator implements Iterator<Item>
{
    private Node current = first;

    public boolean hasNext()
    {
        return current.next != null;
    }
    public Item next()
    {
        Item item = current.item;
        current = current.next;
        return item;
    }
    public void remove()
    {
        /* not supported */
    }
}

public boolean isEmpty()
{
    if(first == null&&last == null)
        return true;
    return false;
}

public int size()
{
    return size;
}

public void addFirst(Item item)
{
    Node oldfirst = first;
    first = new Node();
    first.item = item;
    first.next = oldfirst;
    oldfirst.prev = first;
    size++;
}

public void addLast(Item item)
{
    Node oldlast = last;
    last = new Node();
    last.item = item;
    last.prev = oldlast;
    oldlast.next = last;
    size++;
}

public Item removeFirst()
{
    Item item = first.item;
    first = first.next;
    size--;
    return item;
}

public Item removeLast()
{
    Item item = last.item;
    last = last.next;
    size--;
    return item;
}

@Override
public Iterator<Item> iterator() 
{
    return (new ListIterator());
}

public static void main(String[] args)
{
    Deque<Integer> deque = new Deque<Integer>();
    for(int i=0; i<5; i++)
    {
        deque.addFirst(i);
        deque.addLast(9-i);
    }

    for(Integer i : deque)
    {
        StdOut.println(i);
    }
}

}

When I run the code, I get a NullPointerException when it tries to do first.next = last; I can understand why, but I'm not sure how to fix it without breaking the list. Any solutions? Is it perhaps unnecessary to use a doubly linked format (i.e. remove the prev reference Node altogether)?

Answer 1

You avoid NullPointerException by avoiding access to uninitialized variables.

In that particular example, leave out the:

first.next = last;
last.prev = first;

in your constructor and use defensive programming and check for null if it could be uninitialized, before accessing a variable.

For example in your addFirst method:

public void addFirst(Item item)
{
    Node oldfirst;
    if (first != null){
        oldfirst = first;
    }

    first = new Node();
    first.item = item;

    if (oldfirst != null){
        first.next = oldfirst;
        oldfirst.prev = first;
    }
    size++;
}

etc.

By the way, is this a learning exercise? If not, Java library does have Deques ready to use, including linked list: http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

Answer 2

How is your size beginning at 2? It should be 0 until you add an Item.

You initial conditions should be that both prev and next are null. When you add a single item, then size should be 1 and both prev and next should point to that object.