基於鏈接列表從優先級隊列中刪除項目

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