[ACCEPTED]-Comparison of collection datatypes in C#-data-structures
The following content was originally taken 6 from MSDN http://xbox.create.msdn.com/downloads/?id=123&filename=DataStructures_CheatSheet.doc (but the link has since died).
As 5 in the image above, the content was originally 4 provided as a table (which StackOverflow 3 doesn't support).
Given an image isn't easily 2 indexed below is a somewhat crude programmatic 1 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 5 place to start learning: Collection Classes (C# Programming Guide).
Edit: I would look 4 specifically at this related section: Selecting a Collection Class .
Be 3 sure to choose your System.Collections 2 class carefully. Using the wrong type 1 can restrict your use of the collection.
More Related questions
We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.