title: What is the fastest collection in c# to implement a prioritizing queue?
body: <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>