0

リンク リストを介して実装された Java で PriorityQueue クラスを作成しようとしています。キューでは、優先度の異なるオブジェクトが特定の順序でリストの最後に追加されます。そのため、要素の追加は O(1) になり、優先度が最も高い要素の削除は O(n) になります。しかし、remove メソッドを書くのに苦労しています。Linked List クラスに「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 に答える