What is the fastest collection in c# to implement a prioritizing queue?
<p>I need to implement a FIFO queue for messages on a game server so it needs to as fast as possible.  There will be a queue for each user. </p>

<p>The queue will have a maxiumem size (lets say 2000).  The size won't change during runtime.</p>

<p>I need to prioritize messages ONLY if the queue reaches its maximum size by working backwards and removing a lower priority message (if one exists) before adding the new message.</p>

<p>A priority is an int with possible values of 1, 3, 5, 7, 10.</p>

<p>There can be multiple messages with the same priority.</p>

<p>A message cannot change its priority once allocated.</p>

<p>The application is asynchronous so access to the queue needs to be locked.</p>

<p>I'm currently implementing it using a LinkedList as the underlying storage but have concerns that searching and removing nodes will keep it locked for too long.</p>

<p>Heres the basic code I have at the moment:</p>

<pre><code>public class ActionQueue
{
    private LinkedList&lt;ClientAction&gt; _actions = new LinkedList&lt;ClientAction&gt;();
    private int _maxSize;

    /// &lt;summary&gt;
    /// Initializes a new instance of the ActionQueue class.
    /// &lt;/summary&gt;
    public ActionQueue(int maxSize)
    {
        _maxSize = maxSize;
    }

    public int Count
    {
        get { return _actions.Count; }            
    }

    public void Enqueue(ClientAction action)
    {
        lock (_actions)
        {
            if (Count &lt; _maxSize)
                _actions.AddLast(action);
            else
            {
                LinkedListNode&lt;ClientAction&gt; node = _actions.Last;
                while (node != null)
                {
                    if (node.Value.Priority &lt; action.Priority)
                    {
                        _actions.Remove(node);
                        _actions.AddLast(action);
                        break;
                    }

                    node = node.Previous;

                }                    
            }
        }
    }

    public ClientAction Dequeue()
    {
        ClientAction action = null;

        lock (_actions)
        {
            action = _actions.First.Value;
            _actions.RemoveFirst();
        }

        return action;
    }

}
</code></pre>
