Priority Linked Queue add method assistance

Question

I'm trying to implement priority queue using linked nodes, and I have all of my methods working correctly except for the add method. The purpose of the add method is to add a comparable object into the queue in the correct order. The order of the queue is as follows: the highest priority node is the firstNode. Any help as to what I'm doing wrong with my attempt would be much appreciated.

public void add(T newEntry) {

   if(newEntry == null) {
       return;
   }

   if(isEmpty()) { 
      firstNode = new Node(newEntry);
   } else {
       Node currentNode = firstNode;
       if(newEntry.compareTo(firstNode.data)<0) {
           firstNode = new Node(newEntry, firstNode);
           length++;
           return;
       } else {
           while(currentNode.getNextNode() != null && newEntry.compareTo(currentNode.next.data) > 0) {
                  currentNode = currentNode.next;
                  currentNode.setNextNode(new Node(newEntry, currentNode.getNextNode()));
           }
       }
   }
   length++;
   return;     
} 

Answer 1

You have at least two problems, which I've pointed out in code comments:

public void add(T newEntry) {

   if(newEntry == null) {
       return;
   }

   if(isEmpty()) { 
      firstNode = new Node(newEntry);
   } else {
       Node currentNode = firstNode;
       if(newEntry.compareTo(firstNode.data)<0) {
// Here you're assigning a new value to firstNode, but not linking to the old
// firstNode. So you're losing the entire list.
           firstNode = new Node(newEntry, firstNode);
           length++;
           return;
       } else {
           while(currentNode.getNextNode() != null && newEntry.compareTo(currentNode.next.data) > 0) {
                  currentNode = currentNode.next;
// Here you're adding multiple new nodes to the list.
                  currentNode.setNextNode(new Node(newEntry, currentNode.getNextNode()));
           }
       }
   }
   length++;
   return;     
}

You can simplify that pretty easily:

public void add(T newEntry) {

   if(newEntry == null) {
       return;
   }
   Node newNode = new Node(newEntry);

   if(isEmpty()) { 
      firstNode = newNode;
   } else if (newNode.data < firstNode.data) {
      // make newNode point to the firstNode,
      // and then re-assign firstNode
      newNode.setNextNode(firstNode);
      firstNode = newNode;
   } else {
       Node currentNode = firstNode;
       Node nextNode = currentNode.getNextNode;
       while (nextNode != null && nextNode.data > newNode.data) {
           currentNode = nextNode;
           nextNode = currentNode.getNextNode;
       }
       // insert newNode between currentNode and nextNode
       newNode.setNextNode(nextNode);
       currentNode.setNextNode = newNode;
   }
   length++;
   return;     
}