Thursday, March 29, 2012

An Overview Of System.Collections.Generic

Posted by Unknown at 4:34 AM


System.Collections.Generic.Dictionary<TKey,TValue>

The next collection that we are going to look at is the Dictionary. The Dictionary class is an implementation of a dictionary data structure (sometimes referred to as an associative array or a map). Its operations look very similar to a SortedList, since it takes both a key and a value, but in reality they have very different performance characteristics.
The reason for this is that while a SortedList performs an insertions and lookups using a binary search, the Dictionary class actually uses a hash table as its backing store. This means that the data stored inside of the dictionary isn’t sorted, it is looked up by a hash value (meaning that the keys must also be unique). This allows for individual items to be looked up extremely quickly by hashing it, and then looking up its hash inside the hash table:
 image
Because of this, finding a range of values would require you to iterate over all of the values in the dictionary and look for your values. It also means that the data stored in the Dictionary, when iterated over, comes back in an non-determinant order (currently this appears to be in inserted order, but don’t rely on that because it could change at any time) and not in a sorted order.
Example of most common operations:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var dictionary = new Dictionary<int, string>();
dictionary.Add(1, "one");
dictionary.Add(2, "two");
dictionary.Add(3, "three");
dictionary.Add(4, "four");
 
// returns true
dictionary.ContainsKey(1);
 
// returns true
dictionary.ContainsValue("two");
 
// remove by key
dictionary.Remove(3);
 
// lookup by key
string indexedValue = dictionary[4];
 
string value;
if (dictionary.TryGetValue(4, out value))
    //do something
 
foreach (int key in dictionary.Keys)
{
}
 
foreach (string value in dictionary.Values)
{
}
 
//removes all elements
dictionary.Clear();
Bottom Line:
AddAverage – O(1)
InsertsNot applicable, data isn’t in any order
LookupAverage – O(N)
Indexed LookupFast – O(1)
DeleteFast – O(1)
VersatilityLow

System.Collections.Generic.SortedDictionary<TKey,TValue>

In all likelihood, you have probably never used a SortedDictionary. You might not even know what in the world a SortedDictionary is, or why it would be any different from a SortedList. You might also be thinking that it doesn’t really make any sense to have a sorted dictionary since the idea of a dictionary is to provide indexed lookup of items. So where does this leave the SortedDictionary?
Well, the SortedDictionary is actually quite a different beast. Internally it is implemented as a Red-black tree. Red-black trees are a much more complicated data structure than what we have looked at so far, so I’ll just give you a link to the Wikipedia page on Red-black trees. What is important to know about Red-black trees is that they have very good worst-case operations.
The biggest difference between this and a SortedList is that the SortedDictionary doesn’t allow indexed access. It does however have faster add, insertion, and deletion times. Also, because of the tree structure in which the data is stored, the SortedDictionary uses more memory than a SortedList.
Example of most common operations:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var sortedDictionary = new SortedDictionary<int, string>();
sortedDictionary.Add(1, "one");
sortedDictionary.Add(2, "two");
sortedDictionary.Add(3, "three");
sortedDictionary.Add(4, "four");
 
// returns true
sortedDictionary.ContainsKey(1);
 
// returns true
sortedDictionary.ContainsValue("two");           
 
// remove by key
sortedDictionary.Remove(3);           
 
// lookup by key
string value = sortedDictionary[2];
 
string value;
if (sortedDictionary.TryGetValue(4, out value))
    //do something
 
// sorted by key
foreach (int key in sortedDictionary.Keys)
{
    Console.WriteLine(key);
}
 
// sorted by key
foreach (string value in sortedDictionary.Values)
{
    Console.WriteLine(value);
}           
 
//removes all elements
sortedDictionary.Clear();
Bottom Line:
AddFast – O(log N)
InsertsFast – O(log N)
LookupNot Applicable
Sorted LookupFast – O(log N)
DeleteFast – O(log N)
VersatilityLow

System.Collections.Generic.LinkedList<T>

The LinkedList class is an implementation of a doubly linked list data structure. A doubly linked list is a fairly simple data structure consisting of a bunch of nodes with pointers to the previous and next node:
image
The .Net Framework implementation also point the next and previous pointers on the first and last item to each other. Because of the way that this data structure works, it makes it very cheap to add and insert items, assuming that you are already in the place in the list where the data needs to be inserted. In order to insert a node, the pointers merely need to be redirected:
image
Also, since pointers only exist between nodes, there is no indexed access and it in order to find items in the list, each item needs to be iterated through.
The LinkedList may be a simple data structure, but it is an excellent data structure if you have a list which has a heavy amount of insertion and deletion within the list. It is especially useful if you are inserting ranges of data into the middle of a list.
Example of most common operations:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
var linkedList = new LinkedList<string>();
 
// add node to front of list
linkedList.AddFirst("one");           
 
// add node to end of list
var nodeThree = linkedList.AddLast("three");
 
// add node before given node
linkedList.AddBefore(nodeThree, "two");
 
// add node after given node
linkedList.AddAfter(nodeThree, "four");
 
// iterate list printing one, two, three, four
foreach (string value in linkedList)
{
    Console.WriteLine(value);
}
 
// find first node with value "two"
var nodeTwo = linkedList.Find("two");
 
// find last node with value "three"
nodeThree = linkedList.FindLast("three");
 
// get first node in list
var firstNode = linkedList.First;
 
// get last node in list
var lastNode = linkedList.Last;
 
// remove the first node with value "two"
linkedList.Remove("two");
 
// remove first node in list
linkedList.RemoveFirst();
 
// remove last node in list
linkedList.RemoveLast();
 
// remove all items from list
linkedList.Clear();
Bottom Line:
AddVery Fast – O(1)
InsertsVery Fast – O(1)
LookupSlow – O(N)
Sorted LookupNot Applicable
DeleteVery Fast – O(1)
VersatilityLow


 

0 comments:

Post a Comment

Subscribe to: Post Comments (Atom)