可迭代双端队列 NullPointerException

Question

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

import java.util.Iterator;

public class 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；我能理解为什么，但我不确定如何在不破坏列表的情况下修复它。任何解决方案？是否可能没有必要使用双向链接格式（即完全删除前一个引用节点）？

Answer 1

您的尺寸如何从 2 开始？它应该是 0，直到您添加 Item。

你的初始条件应该是 prev 和 next 都是 null。当您添加单个项目时，大小应为 1，并且 prev 和 next 都应指向该对象。

Answer 2

Deque为空时，没有"next"和"previous"。它完全是空的。只要有数据就会有"next"和"previous"

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

当然，大小应该为零。

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

如果 first 或 last 中的项目分别不为空，则仅按您所做的那样进行（添加项目，更正链接）。

并且记得在您的 removeFirst 和 removeLast 方法中检查 null。

简写：空列表的情况比较特殊。您应该从一个空列表开始。您应该在 add 和 remove 方法中检查这种特殊情况。

Answer 3

您可以通过避免访问未初始化的变量来避免 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

可迭代双端队列 NullPointerException

Iterable Deque NullPointerException

java

nullpointerexception

deque