Iterable Deque NullPointerException

Question

我试图通过实现双重链接列表格式来创建一个Deque类(Stack/Queue，可以在两端添加和引用)。

import java.util.Iterator;

公共类Deque实现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);
    }
}

}

当我运行代码时，当NullPointerException尝试执行first.next =last时，我会得到它；我可以理解为什么，但我不知道如何在不打破列表的情况下修复它。有什么解决办法吗？是否没有必要使用双链接格式(即完全删除prev引用节点)？

Answer 1

通过避免访问未初始化的变量，可以避免NullPointerException。

在这个特定的例子中，省略：

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

在构造函数中使用防御性编程，并在访问变量之前检查null是否可以未初始化。

例如，在addFirst方法中：

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

等。

顺便问一下，这是一个学习练习吗？如果没有，Java库已经准备好使用Deques，包括链接列表：http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

Answer 2

你的尺寸在2是怎么开始的？它应该是0，直到您添加一个Item。

初始条件应该是prev和next都是null。添加单个项时，大小应该是1，prev和next都应该指向该对象。

Answer 3

当Deque是空的，没有“下一步”和“前”。它完全是空的。只有在有数据的情况下，才会有“下一步”和“先前”。

因此，在初始化Deque时，不应该尝试将prev和next分配给null引用。它们是null这一事实表明，这里没有任何东西，所以当然，在它之前或之后都没有任何东西。

当然，尺寸应该是零。

然后，在addFirst和addLast方法中，您应该处理first和last为null的情况。在这种情况下，必须将它们初始化为相同的值，其中next和prev都是null。并将大小设置为1。

如果first或last中的项分别不是null，则只按您所做的那样进行(添加项，更正链接)。

记住也要检查null在removeFirst和removeLast方法中的位置。

短版本：空列表的情况是特殊的。你应该从一个空列表开始。您应该在add和remove方法中检查这个特殊情况。