Each week my department holds a morning tech review. Subjects vary from testing tools, advanced caching mechanisms, to good ol' basic .NET facts. This week the tech review was an "Asymptomatic Analysis of .NET Collections". While most of the material was pretty straight forward, I always find getting back to the basics to be a good thing.
I thought that it was fun to see all of the collection run times aggregated into one table. As several of my coworkers pointed out, it can be a bit of a pain to find all these "simple" facts on the SEO crammed internet...so then why does no one simply blog about it?
In summary: here is some stolen content. Thanks Byron!
List-Like Collections
| List | LinkedList | SortedList | |
|---|---|---|---|
| Add | O(1) or O(N) | O(1) | O(Log N) or O(N) |
| Remove | O(N) | O(N) | O(N) |
| Clear | O(N) | O(1) | O(Log N) |
| Get | O(1) | O(N) | O(Log N) |
| Find | O(N) | O(N) | O(Log N) |
| Sort | O(N log N) or O(N^2) | - | Already sorted |
| Underlying Data Structure |
Array | Dynamically allocated nodes | Array |
Hash-Like Collections
| Dictionary | SortedDictionary | HashSet | SortedSet | |
|---|---|---|---|---|
| Add | O(1) or O(N) |
O(Log N) | O(1) or O(N) |
O(log N) |
| Remove | O(1) | O(log N) | O(1) | O(N) |
| Clear | O(N) | O(Log N) | O(N) | O(N) |
| Get / Find | O(1) | O(Log N) | O(1) | O(Log N) |
| Sort | - | Already sorted | - | - |
| Underlying Data Structure |
Array + Linked List | Dynamically allocated nodes (Binary Search Tree) |
Array + Linked List | Dynamically allocated nodes (Binary Search Tree) |
If you would like to see any updates/additions please feel free to leave a comment.
Enjoy,
Tom
