Queue<T> vs List<T>

Question

I'm currently using a List<T> as a queue (use lst[0] then lst.removeAt(0)) to hold objects. There's about 20 items max at a given time. I realized there was an actual Queue<T> class. I'm wondering if there's any benefit (performance, memory, etc.) to using a Queue<T> over a List<T> acting like a queue?

Answer 1

Performance can be profiled. Though in this case of so few items, you may need to run the code millions of times to actually get worthwhile differences.

I will say this: Queue<T> will expose your intent more explicitly, people know how a queue works.

A list being used like a queue is not as clear, especially if you have a lot of needless indexing and RemoveAt(magicNumber) code. Dequeue is a lot more consumable from a code maintenance point of view.

If this then gives you measurable performance issues, you can address it. Don't address every potential performance issue upfront.

Answer 2

Short answer:
Queue<T> is faster than List<T> when it's used like a queue. List<T> is faster than Queue<T> when used like a list.

Long answer:
A Queue<T> is faster for dequeuing operation, which is an O(1) operation. The entire block of subsequent items of the array is not moved up. This is possible because a Queue<T> need not facilitate removal from random positions, but only from the top. So it maintains a head (from which the item is pulled upon Dequeue) and tail position (to which the item is added upon Enqueue). On the other hand removing from the top of a List<T> requires itself to shift positions of every subsequent item one up. This is O(n) - worst case if you're removing from the top, which is what a dequeue operation is. The speed advantage can be noticeable if you're dequeuing in a loop.

A List<T> is more performant if you need indexed access, random retrieval etc. A Queue<T> will have to enumerate fully to find the appropriate index position (it doesn't expose IList<T>).

That said, a Stack<T> vs List<T> is much closer, there is no performance difference in pushing and popping operations. They both push to end and remove from end of array structures (both of which are O(1)).

---

Of course you should use the correct structure that reveals the intent. In most cases they will perform better as well since they are tailor-made for the purpose. I believe had there been no performance difference at all, Microsoft wouldn't have included Queue<T> and Stack<T> in the framework for merely different semantics. It would have been simply easily extensible if that was the case. Think about SortedDictionary<K, V> and SortedList<K, V>, both of which do exactly the same but is differentiated by only performance characteristic; they find a place in BCL.