Comparison of collection datatypes in C#
The following content was originally taken from MSDN http://xbox.create.msdn.com/downloads/?id=123&filename=DataStructures_CheatSheet.doc (but the link has since died).
As in the image above, the content was originally provided as a table (which StackOverflow doesn't support).
Given an image isn't easily indexed below is a somewhat crude programmatic conversion of the information to lists:
Array
- add to end:
O(n) - remove from end:
O(n) - insert at middle:
O(n) - remove from middle:
O(n) - Random Access:
O(1) - In-order Access:
O(1) - Search for specific element:
O(n) - Notes: Most efficient use of memory; use in cases where data size is fixed.
List
- add to end:
best case O(1); worst case O(n) - remove from end:
O(1) - insert at middle:
O(n) - remove from middle:
O(n) - Random Access:
O(1) - In-order Access:
O(1) - Search for specific element:
O(n) - Notes: Implementation is optimized for speed. In many cases, List will be the best choice.
Collection
- add to end:
best case O(1); worst case O(n) - remove from end:
O(1) - insert at middle:
O(n) - remove from middle:
O(n) - Random Access:
O(1) - In-order Access:
O(1) - Search for specific element:
O(n) - Notes: List is a better choice, unless publicly exposed as API.
LinkedList
- add to end:
O(1) - remove from end:
O(1) - insert at middle:
O(1) - remove from middle:
O(1) - Random Access:
O(n) - In-order Access:
O(1) - Search for specific element:
O(n) - Notes: Many operations are fast, but watch out for cache coherency.
Stack
- add to end:
best case O(1); worst case O(n) - remove from end:
O(1) - insert at middle:
N/A - remove from middle:
N/A - Random Access:
N/A - In-order Access:
N/A - Search for specific element:
N/A - Notes: Shouldn't be selected for performance reasons, but algorithmic ones.
Queue
- add to end:
best case O(1); worst case O(n) - remove from end:
O(1) - insert at middle:
N/A - remove from middle:
N/A - Random Access:
N/A - In-order Access:
N/A - Search for specific element:
N/A - Notes: Shouldn't be selected for performance reasons, but algorithmic ones.
Dictionary
- add to end:
best case O(1); worst case O(n) - remove from end:
O(1) - insert at middle:
best case O(1); worst case O(n) - remove from middle:
O(1) - Random Access:
O(1)* - In-order Access:
O(1)* - Search for specific element:
O(1) - Notes: Although in-order access time is constant time, it is usually slower than other structures due to the over-head of looking up the key.
This isn't a cheat sheet but it is a good place to start learning: Collection Classes (C# Programming Guide).
Edit: I would look specifically at this related section: Selecting a Collection Class .
Be sure to choose your System.Collections class carefully. Using the wrong type can restrict your use of the collection.