All about when to use what:
The Associative Collection Classes
The Dictionary<TKey,TVale> is probably the most used associative container class. The Dictionary<TKey,TValue> is the fastest class for associative lookups/inserts/deletes because it uses a hash table under the covers. Because the keys are hashed, the key type should correctly implement GetHashCode() and Equals() appropriately or you should provide an external IEqualityComparer to the dictionary on construction. The insert/delete/lookup time of items in the dictionary is amortized constant time - O(1) - which means no matter how big the dictionary gets, the time it takes to find something remains relatively constant. This is highly desirable for high-speed lookups. The only downside is that the dictionary, by nature of using a hash table, is unordered, so you cannot easily traverse the items in a Dictionary in order.
The SortedDictionary<TKey,TValue> is similar to the Dictionary<TKey,TValue> in usage but very different in implementation. TheSortedDictionary<TKey,TValye> uses a binary tree under the covers to maintain the items in order by the key. As a consequence of sorting, the type used for the key must correctly implement IComparable<TKey> so that the keys can be correctly sorted. The sorted dictionary trades a little bit of lookup time for the ability to maintain the items in order, thus insert/delete/lookup times in a sorted dictionary are logarithmic - O(log n). Generally speaking, with logarithmic time, you can double the size of the collection and it only has to perform one extra comparison to find the item. Use the SortedDictionary<TKey,TValue> when you want fast lookups but also want to be able to maintain the collection in order by the key.
SortedList<TKey,TValue> is same as SortedDictionary<TKey,TValue>
This means that insertions and deletions are linear - O(n) - because deleting or adding an item may involve shifting all items up or down in the list.Lookup time, however is O(log n) because the SortedList can use a binary search to find any item in the list by its key - not that used but can be prefered for lookup.
The Non-Associative Containers
The other container classes are non-associative. They don't use keys to manipulate the collection but rely on the object itself being stored or some other means (such as index) to manipulate the collection.
The List<T> Generic version of Arraylist. Because the items are stored contiguously as an array, you can access items in the List<T> by index very quickly. However inserting and removing in the beginning or middle of the List<T> are very costly because you must shift all the items up or down as you delete or insert respective.
However, adding and removing at the end of a List<T> is an amortized constant operation - O(1).
The LinkedList<T> is a basic implementation of a doubly-linked list. This means that you can add or remove items in the middle of a linked list very quickly (because there's no items to move up or down in contiguous memory), but you also lose the ability to index items by position quickly.
Most of the time we tend to favor List<T> over LinkedList<T>. if you are doinglot of adding and removing from the collection, LinkedList<T> may make more sense.
The HashSet<T> is an unordered collection of unique items. In these cases a HashSet<T> is useful for super-quick lookups where order is not important
SortedSet<T>-This once again means that adding/removing/lookups are logarithmic - O(log n)
Finally, the Stack<T> and Queue<T> are two very specific collections that allow you to handle a sequential collection of objects in very specific ways. The Stack<T> is a last-in-first-out (LIFO) container where items are added and removed from the top of the stack. Typically this is useful in situations where you want to stack actions and then be able to undo those actions in reverse order as needed. The Queue<T> on the other hand is a first-in-first-out container which adds items at the end of the queue and removes items from the front.
- ArrayList
- A dynamic, contiguous collection of objects.
- Favor the generic collection List<T> instead.
- Hashtable
- Associative, unordered collection of key-value pairs of objects.
- Favor the generic collection Dictionary<TKey,TValue> instead.
- Queue
- First-in-first-out (FIFO) collection of objects.
- Favor the generic collection Queue<T> instead.
- SortedList
- Associative, ordered collection of key-value pairs of objects.
- Favor the generic collection SortedList<T> instead.
- Stack
- Last-in-first-out (LIFO) collection of objects.
- Favor the generic collection Stack<T> instead.
At its most complex,it holds references,often to many other objects.
List. This is an efficient, dynamically-allocated array. It does not provide fast lookup in the general case (the Dictionary is better for lookups)
Generic: List<string> list = new List<string>();
// 2. Search for this element. if (list.Contains("dog")) { Console.WriteLine("dog was found"); } // 3. Search for this element in any string case. // This is the LINQ method with the same name. if (list.Contains("MOTH", StringComparer.OrdinalIgnoreCase)) { Console.WriteLine("MOTH was found (insensitive)"); } // 4. This element is not found. Console.WriteLine(list.Contains("fish")); }
Performance: Good for small list
List<int> list = new List<int>(new int[] { 19, 23, 29 });
// Finds first element greater than 20
int result = list.Find(item => item > 20);
Dictionary. This is an implementation of a hash table: an extremely efficient way to store keys for lookup.Dictionary is fast,well-designed and eliable.
DictionaryDictionary<string, int> dictionary =
new Dictionary<string, int>();
TryGetValue. This is often the most efficient look up method
if (values.TryGetValue("bird", out test)) // Returns false. { Console.WriteLine(false); // Not reached. }Concurrent. Does a program use threads? If so, consider the ConcurrentDictionary. It improves thread-safety. ConcurrentBag offers a simple way to share data between threads.ConcurrentDictionaryConcurrentBagKeyValuePair. When a collection that implements IDictionary (like Dictionary) is used in a foreach-loop, it returns an enumeration. A Dictionary will return KeyValuePair structs in a loop.var list = new List<KeyValuePair<string, int>>(); list.Add(new KeyValuePair<string, int>("Cat", 1)); list.Add(new KeyValuePair<string, int>("Dog", 2)); list.Add(new KeyValuePair<string, int>("Rabbit", 4)); foreach (var element in list) { Console.WriteLine(element); }Dictionary<string, int> d = new Dictionary<string, int>() { {"cat", 2}, {"dog", 1}, {"llama", 0}, {"iguana", -1} }; // Loop over pairs with foreach. foreach (KeyValuePair<string, int> pair in d) { Console.WriteLine("{0}, {1}", pair.Key, pair.Value); } // Use var keyword to enumerate dictionary. foreach (var pair in d) { Console.WriteLine("{0}, {1}", pair.Key, pair.Value); } } }List versus Dictionary. I suggest almost always using Dictionary for lookups. In large collections, a List will become unusable for lookups.But:A Dictionary will still work well with large amounts of data.It is faster to loop through elements in a List. If looping through elements is the most common operation, a List is superiorArrayList list = new ArrayList(); list.Add("Cat"); list.Add("Zebra"); list.Add("Dog"); list.Add("Cow");Generic type of arraylist is List;Hashtable. This is a lookup data structure. It uses a hash code to quickly find elements. Dictionary is usually more appropriate for programs.Hashtable hashtable = new Hashtable(); hashtable[1] = "One"; hashtable[2] = "Two"; hashtable[13] = "Thirteen"; foreach (DictionaryEntry entry in hashtable) { Console.WriteLine("{0}, {1}", entry.Key, entry.Value); }TupleTuple<int, string, bool> tuple = new Tuple<int, string, bool>(1, "cat", true); // Access tuple properties. if (tuple.Item1 == 1) { Console.WriteLine(tuple.Item1); } if (tuple.Item2 == "dog") { Console.WriteLine(tuple.Item2); } if (tuple.Item3) { Console.WriteLine(tuple.Item3); }
- o that's the basic collections. Let's summarize what we've learned in a quick reference table.CollectionOrderingContiguous Storage?Direct Access?Lookup EfficiencyManipulateEfficiencyNotesDictionaryUnorderedYesVia KeyKey:O(1)O(1)Best for high performance lookups.
SortedDictionary Sorted No Via Key Key: O(log n) O(log n) Compromise of Dictionary speed and ordering, uses binarysearch tree.SortedListSortedYesVia KeyKey:O(log n)O(n)Very similar toSortedDictionary, except tree is implemented in an array, so has faster lookup on preloaded data, but slower loads.ListUser has precise control over element orderingYesVia IndexIndex: O(1)Value: O(n)O(n)Best for smaller lists where direct access required and no sorting.LinkedListUser has precise control over element orderingNoNoValue:O(n)O(1)Best for lists where inserting/deleting in middle is common and no direct access required.HashSetUnorderedYesVia Key Key:O(1)O(1)Unique unordered collection, like a Dictionary except key and value are same object. SortedSetSortedNoVia KeyKey:O(log n)O(log n)Unique sorted collection, like SortedDictionary except key and value are same object.StackLIFOYesOnly TopTop: O(1)O(1)*Essentially same as List<T> except only process as LIFOQueueFIFOYesOnly FrontFront: O(1)O(1)Essentially same as List<T> except only process as FIFO
From multiple Internet Sources:
http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx
