#Introduction
In data processing, a data structure is a logical structure intended to contain data, to give them an organization enabling them to be processed. Knowledge of them makes it possible to choose the one that best responds to a given problem. My goal is not to do an algorithm course but only to detail some of the implementations chosen by Microsoft to realize the classes of the .Net Framework and to be able to choose the one that best corresponds to our needs. If you want to understand in more detail how a data structure works, I advise you to go on your favorite search engine and type its name.
#The notations
To measure the effectiveness of an algorithm, one will measure the time it uses. Just count the instructions and weight them by their cost. There are several types of operations:
- Arithmetic operations
- Read / assign variables
- Comparisons
- …
To note the complexity of the algorithms the notion of O(n) (as in maths) is used. O(n) means "at worst". Here are some examples for everyone to understand. Let us imagine that we are a list containing 1 million elements. If an algorithm is
- O(1): Whatever the number of elements, the time is always identical.
- O(ln(n)): For our list, it means that ln(1000000)≈14 operations to realize the algorithm
In order of complexity (from the fastest to the slowest): 1, ln(n), n, n ln(n), n2, en
#LinkedList<T>
It is a twice-chained circular list. This makes it possible to make head and tail insertions at 0(1). Indeed to insert an element in the tail, it is enough to insert it before the head element because the list is circular. To search for an item you have to browse the entire list item by item until you find the right one, which is not the most efficient.
#List<T>
This is an array that increases its size when needed. The initial size of the array by default is 4. When you try to insert an element while the array is full, a new array is allocated. This one is twice as big as the previous one. The items of the old array are copied to the new array and the new item can be added. To insert an element at a precise index, you must first move all the following elements of the array one space and then put the new element in its place. Removal involves shifting left all of the following items. To search for an item you have to browse the entire list item by item until you find the right one. Again, this is not the most effective.
#SortedList<TKey, TValue>
Its operations are identical to List. However, the items in the table are sorted in ascending order. When adding, it is necessary to start by looking for his place in the table. For this, a dichotomous search is performed (O(log(n)). The rest of the operations are strictly identical to the insertion in an unsorted list.
#HashSet<T>
The HashSet is a hash table with resolution of collisions by coalesced chaining. To insert an element, the function starts by computing the hash value using the GetHashCode method and thus deduces the index of the element in the array (hash modulo size of the array). If there is already an element at this position (this is called conflict), a chaining principle is used. That is, we look for an empty bucket from the end of the table and add the element. At the position we should have inserted the element we added information indicating the index that was used to store a value having the same hash value. To find an element, you calculate its hash and fetch the element at the corresponding index. If the value in this box matches the value you are looking for: Bingo. Otherwise, you look at whether there was a collision (there is a link to another element) and you follow the link. If it is still not the right value, you keep going until there is no more link to follow. A hash function is considered good if there are no more than 5 elements in the collection having the same hash value. On average the search is in O(1). However, if the hash function is bad and generates too much collision, the search can be in O(n).
#Dictionary<TKey, TValue>
The dictionary works like the HashSet except that the hash value is calculated from the key (TKey) and not from the value (TValue).
#SortedSet<T>
The SortedSet is implemented with a Red-Black tree (or two-color tree). This is a balanced search binary tree. All operations are done in O(log(n)).
#SortedDictionary<TKey, TValue>
In short, it is a SortedSet<KeyValuePair<TKey, TValue>>. So, it has the same operating mode as the SortedSet.
#Summary
##Insert item
| General | Head | Tail |
|---|
| LinkedList | O(n) | O(1) | O(1) |
| List | O(n) | O(n) | O(1) |
| SortedDictionary | O(log(n)) | N/A | N/A |
| Dictionary | O(1) | N/A | N/A |
| HashSet | O(1) | N/A | N/A |
| SortedSet | O(log(n)) | N/A | N/A |
| SortedList | O(n) | N/A | N/A |
##Remove item
| General | Head | Tail |
|---|
| LinkedList | O(n) | O(1) | O(1) |
| List | O(n) | O(n) | O(1) |
| SortedDictionary | O(log(n)) | N/A | N/A |
| Dictionary | O(1) | N/A | N/A |
| HashSet | O(1) | N/A | N/A |
| SortedSet | O(log(n)) | N/A | N/A |
| SortedList | O(n) | N/A | N/A |
##Get by index
| General |
|---|
| LinkedList | O(n) |
| List | O(1) |
| SortedList | O(1) |
##Get by value
| General |
|---|
| LinkedList | O(n) |
| List | O(n) |
| SortedDictionary | O(log(n)) |
| Dictionary | O(1) |
| HashSet | O(1) |
| SortedSet | O(log(n)) |
| SortedList | O(log(n)) |
#Measures
##Add First
##Add Last
##Contains
##Remove First
##Remove Last
#Conclusion
I hope to have succeeded in demonstrating that each data structure has a different purpose and good performance for some operations and less good performance for others. So, you have to make the right choice according to your needs.
Source code of the tests: Test Performance
Do you have a question or a suggestion about this post? Contact me!
