按语法排序的链表返回空指针异常

Question

我正在尝试构建一个按字典顺序排列的链表。我在纸上计划好了这一切，并认为我需要正确的一切，但一旦我插入第二个或第三个条目，它就会返回一个空指针异常。

Exception in thread "main" java.lang.NullPointerException
at DoublyLL.insert(DoublyLL.java:88)

如果我输入，例如：

"chris", "andy", then "bob", "bob" returns the excpetion.
"chris", "bob", then "andy", "andy" returns the exception
"andy", "bob", I get the same exception with the addition of at DoublyLL$Node.access$000(DoublyLL.java:148)

代码：

public boolean insert(StudentListing newListing)
{  Node n = new Node();
    if(n == null) // out of memory
       return false;
    else
    {
                    Node q = new Node();
        q = h;
        int lex;
        if (q.next == null)     // first inputed node
        {
            n.next = q.next;
            q.next = n;
            n.back = q;
            n.l = newListing.deepCopy();
            return true;
        } else                  // not first node
        {
            q = q.next;
            do
            {
               // This is the line the error is called vvv
                lex = q.l.getKey().compareTo(newListing.getKey());
               // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                if (lex < 0)
                {
                    // keep going
                    q = q.next;
                } else if (lex > 0)
                {
                    // place before q
                    n.back = q.back;
                    q.back = n;
                    n.next = q;
                    n.back.next = n;
                    return true;
                } else if (lex == 0)
                {
                    // q and listing match
                }
            } while (lex < 0);
        }
    }
    return false;
}

Inner class

 public class Node
 {   private StudentListing l;
     private Node next;
     private Node back;
     public Node()
 { }
}

Answer 1

这里最大的问题是，当您将一个新的StudentListing插入到一个非空列表中时，您会迭代该列表，直到找到一个大于您插入的StudentListing的元素。但是，如果您插入的StudentListing大于列表中的任何元素，那么您永远找不到这样的元素，所以您会从列表的末尾运行。在编写q = q.next之前，您需要检查是否为q.next == null，并适当地处理这种情况。

（在您的代码中也有各种小的非Java主义—例如，if(n == null) // out of memory永远不会是真的，因为Java通过引发异常而不是返回null来指示内存不足错误—但在我看来，这些都不是大问题。）