NET data structures ArrayList List HashTable Dictionary SortedList SortedDictionary -- Speed memory and when to use each

Question

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

User · Answer

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 lt   lookups is O 1

User · Answer

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   Array  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   ArrayList  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 56       myArrayList Add  String        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      C  Data Structures     Collections and Data Structures   List vs IEnumerable vs IQueryable vs ICollection vs IDictionary System Collections Generic Namespace  System Collections Namespace

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

If at all possible  use generics   This includes    List instead of ArrayList Dictionary instead of HashTable

User · Answer

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 lt string gt   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 lt string  string gt  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

User · Answer

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

User · Answer

I found  Choose a Collection  section of Microsoft Docs on Collection and Data Structure page really useful  C  Collections and Data Structures   Choose a collection    And also the following matrix to compare some other features

User · Answer

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

User · Answer

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

User · Answer

NET data structures  More to conversation about why ArrayList and List are actually different Arrays As one user states  Arrays are the  quot old school quot  collection  yes  arrays are considered a collection though not part of System Collections   But  what is  quot old school quot  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   quot mechanisms that allow you to treat several  logically-related  items as a single collection  quot   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  quot common-ness quot  of zero-based arrays  Microsoft has spent a lot of time optimizing their performance  therefore  single dimension  zero-based  SZs  arrays are  quot special quot  - 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  quot fixed quot  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   quot Using multidimensional arrays as elements    is not supported quot   Again  another nail in the coffin of ArrayLists  ArrayLists are also not  quot typed quot  - 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  quot object quot   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   quot     a strongly typed list of objects that can be accessed by index  quot  The importance here is the  quot strongly typed quot  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   quot It is to your advantage to use the type-specific implementation of the List Of T  class instead of using the ArrayList class     quot  Essentially  List Of T  is ArrayList  but better  It is the  quot generic equivalent quot  of ArrayList  Like ArrayList  it is not guaranteed to be sorted until sorted  go figure   List Of T  also has some added functionality

User · Answer

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

[c#] .NET data structures: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary -- Speed, memory, and when to use each?

Examples related to c#

Examples related to .net

Examples related to vb.net

Examples related to arrays

Examples related to data-structures