Lexographically有序的鏈表返回空指針異常

我試圖建立一個字典順序鏈接列表。我在紙上計劃了所有內容，並認爲我需要一切正確，但是一旦我插入第二個或第三個條目，它將返回一個空指針異常。Lexographically有序的鏈表返回空指針異常

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

來源

2012-03-10 Chris

這裏最大的問題是，當你插入一個新的StudentListing添加到非空列表中時，您將遍歷列表，直到找到大於您要插入的StudentListing的元素。但是如果你插入的StudentListing大於列表中的任何元素，那麼你永遠不會找到這樣的元素，所以你跑掉了列表的末尾。在編寫q = q.next之前，您需要檢查是否q.next == null，並適當處理該情況。

（也有各種各樣的小在你的代碼的非Java的ISMS —例如，if(n == null) // out of memory將永遠是真實的，因爲Java通過引發異常，而不是返回null —但沒有表明內存不足，錯誤那些看起來對我來說是一個主要問題。）

來源

2012-03-10 15:34:22 ruakh

Lexographically有序的鏈表返回空指針異常

回答

相關問題