I'm attempting to create a PriorityQueue class in Java implemented via a Linked List. In the queue, objects with different priorities will be added to the end of the list in no particular order, so that adding an element would be O(1) and removing an element with the highest priority would be O(n). However, I'm having difficulty writing the remove method. I've created a "removeHighestPriorityNode" method in my Linked List class, but I am stuck. This is what I have thus far:
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
}
}
Finding the node with the highest priority is no problem, but finding a way to switch the pointer (next) from the node before the one with the highest priority to the one after is what I'm having trouble with. Also, this is my first time posting on this site, so if I am being to vague in any way, please let me know. Any help would be greatly appreciated! Thanks.
