java - 优先级链接队列添加方法帮助

Question

我正在尝试使用链接节点来实现优先级队列，并且我的所有方法都可以正常工作，除了 add 方法。add 方法的目的是以正确的顺序将可比较的对象添加到队列中。队列的顺序如下：优先级最高的节点是firstNode。任何有关我在尝试中做错了什么的帮助将不胜感激。

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;     
} 

标签： javanodespriority-queue

Answer 1

你至少有两个问题，我在代码注释中已经指出：

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;     
}

你可以很容易地简化它：

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;     
}