Извлечение элемента из очереди приоритетов на основе связанного списка

Question

Я пытаюсь создать класс PriorityQueue в Java, реализованный через связанный список. В очереди объекты с разными приоритетами будут добавлены в конец списка без особого порядка, так что добавление элемента будет O (1), а удаление элемента с наивысшим приоритетом будет O (n). Однако мне трудно написать метод remove. Я создал метод removeHighestPriorityNode в моем классе Linked List, но я застрял. Это то, что я до сих пор:

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