0

我正在尝试在通过链接列表实现的 Java 中创建 PriorityQueue 类。在队列中，具有不同优先级的对象将不按特定顺序添加到列表的末尾，因此添加一个元素将是 O(1)，而删除具有最高优先级的元素将是 O(n)。但是，我很难编写 remove 方法。我在我的链接列表类中创建了一个“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
    }
}

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

4

1 回答 1

0

要么考虑使用双向链表，这样您就可以同时引用下一个和上一个节点，或者Node<E> nodeReferencingHighestPriority;在循环中使用并跟踪它：

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

        previous = current;
        current = current.next;
    }
于 2012-04-12T15:09:56.343 回答