java - Deque实现中的空指针异常

Question

我正在学习Java，并实现一个Deque数据结构。这是 Node 类:

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());
    }
}

然后在检查双端队列的大小时如下:

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");
    }
}

编译器错误为 NullPointerException。是因为Node(null)的初始化导致的吗？如果是，我如何为通用项目输入零值？

堆栈跟踪:

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)

第 29 行是:

    if (sentinel.next == sentinel)

Answer 1

您正在声明一个名为 sentinel 的局部变量并对其进行赋值，而不是使用实例字段并对其进行赋值。

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

应该是

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

否则，实例变量 sentinel 仍为 null，并在您尝试取消引用它时导致 NullPointerException

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