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

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

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;     

}