Лексографически упорядоченный связанный список возвращает исключение нулевого указателя

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 & mdash; но ни один из них не выглядит для меня серьезной проблемой.)