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

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