Comparison of collection datatypes in C# [closed]

Question

Does anyone know of a good overview of the different C# collection types? I am looking for something showing which basic operations such as Add, Remove, RemoveLast etc. are supported, and giving the relative performance.

It would be particularly interesting for the various generic classes - and even better if it showed eg. if there is a difference in performance between a List<T> where T is a class and one where T is a struct.

A start would be a nice cheat-sheet for the abstract data structures, comparing Linked Lists, Hash Tables etc. etc. Thanks!

Answer 1

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.