Why am I getting this error message My BinarySearchTree clas

Why am I getting this error message?

My BinarySearchTree class works so I know the problem is with the SortedListLinked class. The SortedListLinked code is below.

////////////////////////////////////////////////////////////////////////////

public class SortedListLinked
{
private Node head;
private int size;

public SortedListLinked()
{
head = null;
size = 0;
}

public boolean isEmpty()
{
return (size == 0);
}

public int size()
{
return size;
}

public KeyedItem remove()
{
   //DO THIS
   //remove the smallest item
       if(head == null) return null;
      
       KeyedItem itm = (KeyedItem)head.getItem();
       head = head.getNext();
       size--;
       return itm;
}

private Node locateNodeAdd(KeyedItem item)
{
//DO THIS
//find the insertion location (remember FIFO for duplicates)
  
       Node curr = head;
       Node prev = null;
      
       String itm1 = item.getKey();
       KeyedItem k = (KeyedItem) curr.getItem();
       String itm2 = k.getKey();
      
       //keep looking until the it find the correct insertion spot

       while(curr != null && (itm2.compareTo(itm1)) >= 0)
       {
           prev = curr;
           curr = curr.getNext();
           k = (KeyedItem) curr.getItem();
           itm2 = k.getKey();
       }
       return prev;
}

public void add(KeyedItem item)
{
Node prev = locateNodeAdd(item);
     
if (prev == null)
{
//insert the new node containing the new item at the beginning of the list
       Node node = new Node(item);
node.setNext(head);
head = node;
}
else
{
//insert the new node containing the new item after the node that prev references
Node node = new Node(item);
       node.setNext(prev.getNext());
prev.setNext(node);
}
size++;
}
}

C: WINDOWS system32 cmd.exe [mkdir] Created dir C:\\progi starting files build build [javac Compiling 23 source files to C: prog starting files build [javaj Excel ion in thread main\" java lang.Null PointerException [java at pqsort. SortedListLinked.locateNodeAdd (Unknown Source) [java at pqsort.SortedListLinked.add(Unknown Source) [java at pqsort.PQSLL.pqInsert (Unknown Source) [java at pgsort.PQSort.pqsort(Unknown Source) [java at cds CDSort main (Unknown Source BUILD FAILED C:\\progi starting files build.xml :33: Java returned 1 Total time: 1 second C:\\progi starting files

Solution

Hopefully this should do the trick. I added some code along with comments for you. If it didn\'t work, please post the whole code, so that we can compile and check with the errors.

public class SortedListLinked
{
private Node head;
private int size;
public SortedListLinked()
{
head = null;
size = 0;
}
public boolean isEmpty()
{
return (size == 0);
}
public int size()
{
return size;
}
public KeyedItem remove()
{
//DO THIS
//remove the smallest item
if(head == null) return null;
  
KeyedItem itm = (KeyedItem)head.getItem();
head = head.getNext();
size--;
return itm;
}
private Node locateNodeAdd(KeyedItem item)
{
//DO THIS
//find the insertion location (remember FIFO for duplicates)
  
//The problem here is you\'re not handling an empty list.
//What if the list is empty, and you\'re trying to insert the first item.
//So, lets add an extreme case:
if(head == null)   //If there are no nodes in the list.
return head;     //Insert at the head of the list.
Node curr = head;   //If not, make head the current node.
Node prev = null;   //Make previous null.
  
String itm1 = item.getKey();   //Get the key value of item.
KeyedItem k = (KeyedItem) curr.getItem();   //Get the node of head node.
String itm2 = k.getKey();       //Get the key value of head.
  
//keep looking until the it find the correct insertion spot
       //This loop uses the follower to move further.
while(curr != null && (itm2.compareTo(itm1)) >= 0)  
//Till there are nodes to move further, and the value of that node is greater than item value.
{
prev = curr;       //Make current node previous.
curr = curr.getNext();   //Make next node current.
k = (KeyedItem) curr.getItem();   //Get the node of current node.
itm2 = k.getKey();       //Get the key of current node.
}
return prev;   //Returns the previous node value.
}
public void add(KeyedItem item)
{
Node prev = locateNodeAdd(item);

if (prev == null)   //If you should insert at a null position, i.e., when there are no nodes in the list.
{
//insert the new node containing the new item at the beginning of the list
Node node = new Node(item);   //Create a node with the specified item.
node.setNext(head);           //Make this newly created node->next point to null.
head = node;                   //Make head point to this node.
}
else
{
//insert the new node containing the new item after the node that prev references
Node node = new Node(item);       //Create a node with the specified item.
node.setNext(prev.getNext());       //Make this newly created node->next point to what prev->next is pointing to.
prev.setNext(node);               //Make the prev->next now point to this node.
}
size++;                               //Increase the size.
}
}