I need to implement a queue for messages on a game server so it needs to as fast as possible.

The queue will have a maxiumem size.

I need to prioritize messages once the queue is full by working backwards and removing a lower priority message (if one exists) before adding the new message.

The appliation is asynchronous so access to the queue needs to be locked.

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.

Heres the basic code I have at the moment:

public class ActionQueue
{
    private LinkedList<ClientAction> _actions = new LinkedList<ClientAction>();
    private int _maxSize;

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

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

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

    public ClientAction Dequeue()
    {
        ClientAction action = null;

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

        return action;
    }

}