By Pretzel

2008-09-24 17:47:27 8 Comments

.NET has a lot of complex data structures. Unfortunately, some of them are quite similar, and I'm not always sure when to use one and when to use another. Most of my C# and Visual Basic books talk about them to a certain extent, but they never really go into any real detail.

What's the difference between Array, ArrayList, List, Hashtable, Dictionary, SortedList, and SortedDictionary?

Which ones are enumerable (IList -- can do 'foreach' loops)? Which ones use key/value pairs (IDict)?

What about memory footprint? Insertion speed? Retrieval speed?

Are there any other data structures worth mentioning?

I'm still searching for more details on memory usage and speed (Big-O notation).


@leonidaa 2018-05-09 22:46:12

Most popular C# Data Structures and Collections

  • Array
  • ArrayList
  • List
  • LinkedList
  • Dictionary
  • HashSet
  • Stack
  • Queue
  • SortedList

C#.NET has a lot of different data structures, for example, one of the most common ones is an Array. However C# comes with many more basic data structures. Choosing the correct data structure to use is part of writing a well structured and efficient program.

In this article I will go over the built-in C# data structures, including the new ones introduces in C#.NET 3.5. Note that many of these data structures apply for other programming languages.


The perhaps simplest and most common data structure is the array. A C# array is basically a list of objects. Its defining traits are that all the objects are the same type (in most cases) and there is a specific number of them. The nature of an array allows for very fast access to elements based on their position within the list (otherwise known as the index). A C# array is defined like this:

[object type][] myArray = new [object type][number of elements]

Some examples:

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

As you can see from the example above, an array can be intialized with no elements or from a set of existing values. Inserting values into an array is simple as long as they fit. The operation becomes costly when there are more elements than the size of the array, at which point the array needs to be expanded. This takes longer because all the existing elements must be copied over to the new, bigger array.


The C# data structure, ArrayList, is a dynamic array. What that means is an ArrayList can have any amount of objects and of any type. This data structure was designed to simplify the processes of adding new elements into an array. Under the hood, an ArrayList is an array whose size is doubled every time it runs out of space. Doubling the size of the internal array is a very effective strategy that reduces the amount of element-copying in the long run. We won't get into the proof of that here. The data structure is very simple to use:

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(new Form());

The downside to the ArrayList data structure is one must cast the retrived values back into their original type:

int arrayListValue = (int)myArrayList[0]

Sources and more info you can find here :

@Sam Schutte 2008-09-24 18:00:25

Off the top of my head:

  • Array* - represents an old-school memory array - kind of like a alias for a normal type[] array. Can enumerate. Can't grow automatically. I would assume very fast insert and retrival speed.

  • ArrayList - automatically growing array. Adds more overhead. Can enum., probably slower than a normal array but still pretty fast. These are used a lot in .NET

  • List - one of my favs - can be used with generics, so you can have a strongly typed array, e.g. List<string>. Other than that, acts very much like ArrayList

  • Hashtable - plain old hashtable. O(1) to O(n) worst case. Can enumerate the value and keys properties, and do key/val pairs

  • Dictionary - same as above only strongly typed via generics, such as Dictionary<string, string>

  • SortedList - a sorted generic list. Slowed on insertion since it has to figure out where to put things. Can enum., probably the same on retrieval since it doesn't have to resort, but deletion will be slower than a plain old list.

I tend to use List and Dictionary all the time - once you start using them strongly typed with generics, its really hard to go back to the standard non-generic ones.

There are lots of other data structures too - there's KeyValuePair which you can use to do some interesting things, there's a SortedDictionary which can be useful as well.

@Justin Bozonier 2008-10-18 16:00:43

Hash Table is O(1), worst case (with collisions) can be O(n)

@DarthVader 2011-08-25 19:00:10

There are many other data structures you need to add here. like LinkedList, Skip List, Stack, Queue, Heap, Trees, Graphs. These are very important data structures as well.

@Harindaka 2012-12-21 16:34:30

ConcurrentDictionary added in .Net 4.0 provides a generic dictionary with Thread Safety

@Harindaka 2012-12-21 16:36:30

Also BlockingCollection<T> provides a thread safe producer/consumer implementation

@Sam Harwell 2013-05-23 05:37:47

ArrayList uses virtual methods, but List<T> does not. ArrayList has been largely replaced with List<T> for standard collections and Collection<T> as a base class for custom collections. Hashtable has been largely replaced by Dictionary<TKey, TValue>. I would recommend avoiding ArrayList and Hashtable for new code.

@Hogan 2013-06-18 15:07:01

@280Z28 - You really should write a new answer -- Sam's was great but it is 5 years old at this point.

@RBT 2017-03-21 09:07:07

Efficiency of hash tables is amortized O(1), not O(1). More details here

@blackwing 2008-09-24 18:05:04

Here are a few general tips for you:

  • You can use foreach on types that implement IEnumerable. IList is essentially an IEnumberable with Count and Item (accessing items using a zero-based index) properties. IDictionary on the other hand means you can access items by any-hashable index.

  • Array, ArrayList and List all implement IList. Dictionary, SortedDictionary, and Hashtable implement IDictionary.

  • If you are using .NET 2.0 or higher, it is recommended that you use generic counterparts of mentioned types.

  • For time and space complexity of various operations on these types, you should consult their documentation.

  • .NET data structures are in System.Collections namespace. There are type libraries such as PowerCollections which offer additional data structures.

  • To get a thorough understanding of data structures, consult resources such as CLRS.

@Haim Bendanan 2016-11-23 18:45:26

from msdn, it seems like sortedList implement IDictionnary - not IList

@blackwing 2016-12-05 03:18:44

Fixed. thanks for the comment. Seems like SortedList keeps a list of key/values, so it basically represents a dictionary's data. Don't remember how this class worked when I first wrote the answer ...

@Thomas 2014-10-13 14:56:55

.NET data structures:

More to conversation about why ArrayList and List are actually different


As one user states, Arrays are the "old school" collection (yes, arrays are considered a collection though not part of System.Collections). But, what is "old school" about arrays in comparison to other collections, i.e the ones you have listed in your title (here, ArrayList and List(Of T))? Let's start with the basics by looking at Arrays.

To start, Arrays in Microsoft .NET are, "mechanisms that allow you to treat several [logically-related] items as a single collection," (see linked article). What does that mean? Arrays store individual members (elements) sequentially, one after the other in memory with a starting address. By using the array, we can easily access the sequentially stored elements beginning at that address.

Beyond that and contrary to programming 101 common conceptions, Arrays really can be quite complex:

Arrays can be single dimension, multidimensional, or jadded (jagged arrays are worth reading about). Arrays themselves are not dynamic: once initialized, an array of n size reserves enough space to hold n number of objects. The number of elements in the array cannot grow or shrink. Dim _array As Int32() = New Int32(100) reserves enough space on the memory block for the array to contain 100 Int32 primitive type objects (in this case, the array is initialized to contain 0s). The address of this block is returned to _array.

According to the article, Common Language Specification (CLS) requires that all arrays be zero-based. Arrays in .NET support non-zero-based arrays; however, this is less common. As a result of the "common-ness" of zero-based arrays, Microsoft has spent a lot of time optimizing their performance; therefore, single dimension, zero-based (SZs) arrays are "special" - and really the best implementation of an array (as opposed to multidimensional, etc.) - because SZs have specific intermediary language instructions for manipulating them.

Arrays are always passed by reference (as a memory address) - an important piece of the Array puzzle to know. While they do bounds checking (will throw an error), bounds checking can also be disabled on arrays.

Again, the biggest hindrance to arrays is that they are not re-sizable. They have a "fixed" capacity. Introducing ArrayList and List(Of T) to our history:

ArrayList - non-generic list

The ArrayList (along with List(Of T) - though there are some critical differences, here, explained later) - is perhaps best thought of as the next addition to collections (in the broad sense). ArrayList inherit from the IList (a descendant of 'ICollection') interface. ArrayLists, themselves, are bulkier - requiring more overhead - than Lists.

IList does enable the implementation to treat ArrayLists as fixed-sized lists (like Arrays); however, beyond the additional functionallity added by ArrayLists, there are no real advantages to using ArrayLists that are fixed size as ArrayLists (over Arrays) in this case are markedly slower.

From my reading, ArrayLists cannot be jagged: "Using multidimensional arrays as elements... is not supported". Again, another nail in the coffin of ArrayLists. ArrayLists are also not "typed" - meaning that, underneath everything, an ArrayList is simply a dynamic Array of Objects: Object[]. This requires a lot of boxing (implicit) and unboxing (explicit) when implementing ArrayLists, again adding to their overhead.

Unsubstantiated thought: I think I remember either reading or having heard from one of my professors that ArrayLists are sort of the bastard conceptual child of the attempt to move from Arrays to List-type Collections, i.e. while once having been a great improvement to Arrays, they are no longer the best option as further development has been done with respect to collections

List(Of T): What ArrayList became (and hoped to be)

The difference in memory usage is significant enough to where a List(Of Int32) consumed 56% less memory than an ArrayList containing the same primitive type (8 MB vs. 19 MB in the above gentleman's linked demonstration: again, linked here) - though this is a result compounded by the 64-bit machine. This difference really demonstrates two things: first (1), a boxed Int32-type "object" (ArrayList) is much bigger than a pure Int32 primitive type (List); second (2), the difference is exponential as a result of the inner-workings of a 64-bit machine.

So, what's the difference and what is a List(Of T)? MSDN defines a List(Of T) as, "... a strongly typed list of objects that can be accessed by index." The importance here is the "strongly typed" bit: a List(Of T) 'recognizes' types and stores the objects as their type. So, an Int32 is stored as an Int32 and not an Object type. This eliminates the issues caused by boxing and unboxing.

MSDN specifies this difference only comes into play when storing primitive types and not reference types. Too, the difference really occurs on a large scale: over 500 elements. What's more interesting is that the MSDN documentation reads, "It is to your advantage to use the type-specific implementation of the List(Of T) class instead of using the ArrayList class...."

Essentially, List(Of T) is ArrayList, but better. It is the "generic equivalent" of ArrayList. Like ArrayList, it is not guaranteed to be sorted until sorted (go figure). List(Of T) also has some added functionality.

@Krishna 2013-06-17 12:40:26

A good cheat sheet mentioning the complexities for data structures, algorithms, etc.

@smartcaveman 2015-06-18 02:37:17

wish i could upvote this twice, awesome freaking resource - can't believe i never saw this

@kingfrito_5005 2016-08-23 14:57:16

This is cool, but not entirely accurate for this question. In .NET Lists for example are implemented as Dynamic Arrays instead of as Linked Lists as you would expect. Because of this, the measure of complexity used here is not necessarily accurate.

@iliketocode 2017-12-08 03:14:17

@kingfrito_5005 yes, the bigocheatsheet is very helpful however it is not entirely specific to the .NET types (unfortunately...)

@Scott 2008-09-24 17:52:17

Actually, I think MSDN helps provide pretty good answers to all these questions. Just look up .NET collections.

@Kedar9444 2019-03-15 13:22:55

Providing a Wikipedia link doesn't solve the problem, you must have provided link to the original msdn article instead.

@Andy Brown 2011-11-11 08:56:14

I sympathise with the question - I too found (find?) the choice bewildering, so I set out scientifically to see which data structure is the fastest (I did the test using VB, but I imagine C# would be the same, since both languages do the same thing at the CLR level). You can see some benchmarking results conducted by me here (there's also some discussion of which data type is best to use in which circumstances).

@Rob 2011-08-27 19:59:50

An important note about Hashtable vs Dictionary for high frequency systematic trading engineering: Thread Safety Issue

Hashtable is thread safe for use by multiple threads. Dictionary public static members are thread safe, but any instance members are not guaranteed to be so.

So Hashtable remains the 'standard' choice in this regard.

@Bryan Menard 2011-08-27 22:05:13

This is partly true. The Hashtable is safe to use with only one writer and multiple readers concurrently. On the other hand, it is safe to use the Dictionary with multiple readers as long as it is not modified concurrently.

@Rob 2011-08-28 04:15:24

Definitely. In the trading space however, we're concurrently reading from live market data and running analytics that include the appended entries. It also depends on how many traders are utilizing the system - if it's just you, it obviously doesn't matter.

@Rob 2011-08-28 04:17:08

.NET 4.0 provides a ConcurrentDictionary<TKey, TValue>

@Russ Cam 2008-09-28 15:05:34

The generic collections will perform better than their non-generic counterparts, especially when iterating through many items. This is because boxing and unboxing no longer occurs.

@Chris 2008-09-24 21:04:16

Hashtables/Dictionaries are O(1) performance, meaning that performance is not a function of size. That's important to know.

EDIT: In practice, the average time complexity for Hashtable/Dictionary<> lookups is O(1).

@Ilya Ryzhenkov 2008-09-24 21:07:47

There is no such thing as "performance". The complexity depends on operation. For example, if you insert n elements into Dictionary<>, it will not be O(1) due to rehashing.

@supercat 2011-03-11 22:24:15

FYI, even with rehashing, Dictionary is still O(1). Consider the scenario just before the Dictionary expands. Half the elements--those that were added since the last expansion--will have been hashed once. Half of the remainder will have been hashed twice. Half of the remainder from that, three times, etc. The average number of hashing operations performed on each element will be 1+1/2+1/4+1/8...=2. The situation immediately after expansion is essentially the same, but with every element having been hashed one extra time (so average hash count is three). All other scenarios are between those.

@Ilya Ryzhenkov 2008-09-24 21:11:02

There are subtle and not-so-subtle differences between generic and non-generic collections. They merely use different underlying data structures. For example, Hashtable guarantees one-writer-many-readers without sync. Dictionary does not.

@Abe Heidebrecht 2008-09-24 17:58:05

First, all collections in .NET implement IEnumerable.

Second, a lot of the collections are duplicates because generics were added in version 2.0 of the framework.

So, although the generic collections likely add features, for the most part:

  • List is a generic implementation of ArrayList.
  • Dictionary is a generic implementation of Hashtable

Arrays are a fixed size collection that you can change the value stored at a given index.

SortedDictionary is an IDictionary that is sorted based on the keys. SortedList is an IDictionary that is sorted based on a required IComparer.

So, the IDictionary implementations (those supporting KeyValuePairs) are: * Hashtable * Dictionary * SortedList * SortedDictionary

Another collection that was added in .NET 3.5 is the Hashset. It is a collection that supports set operations.

Also, the LinkedList is a standard linked-list implementation (the List is an array-list for faster retrieval).

@Joel Coehoorn 2008-09-24 17:54:32

They're spelled out pretty well in intellisense. Just type System.Collections. or System.Collections.Generics (preferred) and you'll get a list and short description of what's available.

@Adam Tegen 2008-09-24 17:52:02

If at all possible, use generics. This includes:

  • List instead of ArrayList
  • Dictionary instead of HashTable

Related Questions

Sponsored Content

6 Answered Questions

[SOLVED] SortedList<>, SortedDictionary<> and Dictionary<>

10 Answered Questions

1 Answered Questions

[SOLVED] Comparison of C++ STL collections and C# collections?

  • 2010-09-07 13:27:26
  • Scott Stafford
  • 7273 View
  • 11 Score
  • 1 Answer
  • Tags:   c# c++ collections stl

6 Answered Questions

0 Answered Questions

Looking for a data structure (list) that tracks "usage frequency"

2 Answered Questions

[SOLVED] 'Dictionary Types' In .Net

1 Answered Questions

[SOLVED] Seek through massive data grouped with multiple keys C#

2 Answered Questions

[SOLVED] Best Practice: Nested ForEach

  • 2013-04-16 12:14:36
  • Dane Balia
  • 1434 View
  • 3 Score
  • 2 Answer
  • Tags:   c# nested-loops

4 Answered Questions

Sponsored Content