18

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!

1
  • Requests for tutorials etc. are not considered good questions for SO. Jun 7, 2013 at 14:55

2 Answers 2

32

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

Complexity table

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.
8
  • Hey Guys, looks like that link no longer works. Does anyone know of a different location for that document / have a copy available anywhere? Thanks in advance.
    – JohnLBevan
    Aug 20, 2012 at 14:21
  • 1
    @JohnLBevan I've updated the link for you. Aug 21, 2012 at 4:33
  • Hm... Why is the complexity of adding an element to the end of a Stack<T>/Queue<T> greater than for LinkedList<T>? This doesn't make sense. Isn't a Stack<T>/Queue<T> a LinkedList<T> under the hood? Dec 7, 2012 at 16:03
  • @Abbondanza No, they're both implemented using an array buffer. Stack is implemented as a circular buffer. msdn.microsoft.com/en-us/library/system.collections.stack.aspx As elements are added to a Queue<T>, the capacity is automatically increased as required by reallocating the internal array. msdn.microsoft.com/en-us/library/7977ey2c.aspx Dec 10, 2012 at 8:11
  • 1
    Link no longer works.
    – yakya
    Dec 2, 2018 at 11:22
8

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.

1
  • This is great, as it runs through all the different collections. It includes many more collection types than the cheatsheet on creators.xna.com mentioned in the other answer. Apr 12, 2011 at 0:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.