java - 可迭代双端队列 NullPointerException

Question

我正在尝试通过实现双向链表格式来创建 Deque 类(可以在两端添加和引用的 Stack/Queue)。

import java.util.Iterator;

公共(public)类 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);
    }
}

当我运行代码时，当它尝试执行 first.next = last; 时，我得到一个 NullPointerException；我能理解为什么，但我不确定如何在不破坏列表的情况下修复它。任何解决方案？是否可能没有必要使用双向链接格式(即完全删除 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