基于链接列表从优先级队列中删除项目

Question

我试图通过链接列表实现在Java中实现的PriorityQueue类。在队列中，具有不同优先级的对象将以特定顺序被添加到列表的末尾，以便添加元素将是O（1）并且移除具有最高优先级的元素将是O（n）。但是，我很难编写删除方法。我在我的链接列表类中创建了一个“removeHighestPriorityNode”方法，但我被卡住了。这是我迄今：

public void removeHighestPriorityNode() 
{ 
    if(head == null)         
    { 
     throw new NoSuchElementException(); 
    } 
    else if (head.next != null) 
    { 
     Node<E> previous = head; 
     Node<E> current = head.next; 
     Node<E> highestPriority = head; 

     while(current != null) 
     { 
      if (current.priority > previous.priority) 
      { 
       highestPriority = current; 
      } 

      previous = current; 
      current = current.next; 
     } 
    } 
    else 
    { 
     clear(); //Clears the list 
    } 
} 

寻找具有最高优先级的节点是没有问题的，但要找到一个方式，一个具有最高优先级的一个之前切换从节点的指针（下）之后是我遇到的麻烦。另外，这是我第一次在这个网站上发布，所以如果我以任何方式模糊，请告诉我。任何帮助将不胜感激！谢谢。

Answer 1

或者考虑使用双向链表，所以你必须在下一个都和以前节点的引用，或使用Node<E> nodeReferencingHighestPriority;，并保持它的轨道在环：

while(current != null) 
    { 
     if (current.priority > previous.priority) 
     { 
      nodeReferencingHighestPriority = previous; 
      highestPriority = current; 
     } 

     previous = current; 
     current = current.next; 
    }