[ACCEPTED]-Comparison of collection datatypes in C#-data-structures

Accepted answer
Score: 31

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).

Complexity table

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.
Score: 8

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