System.Collections.Generic.List<T>
The first collection that we are going to look at is List<T>. Like I said before, this collection seems to be the fallback, and with good reason. It is unsorted (but supports sorting), items can be added, removed, or inserted at a specific index. It also has indexed access, meaning that items can be accessed directly using a numeric index. You can add Ranges, perform binary searches, perform sequential searches, built in sorting, get the count of items, check for items within it, pass a delegate to it to perform actions, etc… It really is the Swiss Army knife of collections.
In computer science we know that there are always trade-offs. Nothing comes for free, and in order to have the ability to perform operations like indexed lookups, we need to have some kind of data structure which will support this ability. Because of this, List<T> is internally implemented as a simple array. And as we add more and more items to the list, if the array fills up, then an entirely new array is allocated and the items in the current array are copied over into the new array, and the new item is added:
The default length of the array inside of a List<T> is 4, and it only doubles in size each time it fills up (so it goes 4, 8, 16, 32….), so if you know that you have a really large number of items to pass to the list, then you should probably consider using the constructor that allows you to tell the List<T> what size to start off at. It will really keep you from having to copy a lot of data around.
Most of the operations are really straight forward, and looking at the operations below, you can probably see why List<T> is the generic fallback for any list of unknown length, it provides good performance across a very wide variety of operations.
Examples 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
| var list = new List<string>();list.Add("one");list.Add("two");list.Add("three");list.AddRange(new[] {"four", "five", "six"});//insert item at index 2list.Insert(2, "seven");//removes first occurrence of "seven"list.Remove("seven"); //returns true//removes all occurrences of "seven"list.RemoveAll(s => s == "seven");//checks is list contains twolist.Contains("two"); //returns true//finds the first item which matches predicatestring value = list.Find(s => s == "three");//finds all items which match predicateList<string> values = list.FindAll(s => s == "three");//gets a range of the listList<string> range = list.GetRange(2, 3); //in-place sort of listlist.Sort();//performs a binary search of a sorted list to find index of itemint index = list.BinarySearch("three"); // must sort first!//removes all elementslist.Clear(); |
| Bottom Line: | |
| Add | Very Fast – O(1) |
| Inserts | Average – O(N) |
| Lookup | Average – O(N) |
| Sorted Lookup | Fast – O(log N) – must sort first |
| Delete | Average – O(N) |
| Versatility | High |
System.Collections.Generic.SortedList<TKey,TValue>
SortedList is very similar to List, with one obvious difference, it is sorted. In order to add an item, you have to provide a sort key and a value, which are both stored. A binary search is performed across the list in order to find the right place to insert the item, and then the item is inserted into the array. In order to do this, the entire array has to be shifted in order to make room for the new item:
Due to this, inserting items into the SortedList is an expensive operation. But because the list is maintained as sorted, lookups are very cheap. Because you need both a key and a value, you must provide these on most operations. Since lookups are so cheap, if you need a list which will have heavy lookups with a lower number of inserts, then the SortedList may be a good option for you.
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
44
45
46
47
48
49
| var sortedList = new SortedList<int, string>();sortedList.Add(1, "one");sortedList.Add(2, "two");sortedList.Add(3, "three");sortedList.Add(4, "four");// returns truesortedList.ContainsKey(1);// returns truesortedList.ContainsValue("two");// get index of keysortedList.IndexOfKey(1);// get index of valuesortedList.IndexOfValue("two");// remove by keysortedList.Remove(3);// remove by indexsortedList.RemoveAt(2);// lookup by keystring value = sortedList[2];// get value by indexstring value = sortedList.Values[2];// get key by indexint key = sortedList.Keys[2];string value;if (sortedList.TryGetValue(4, out value)) //do somethingforeach (int key in sortedList.Keys){ Console.WriteLine(key);}foreach (string value in sortedList.Values){ Console.WriteLine(value);} //removes all elementssortedList.Clear(); |
| Bottom Line: | |
| Add | Average – O(N) |
| Inserts | Average – O(N) |
| Lookup | Average – O(N) |
| Sorted Lookup | Fast – O(log N) -presorted |
| Delete | Average – O(N) |
| Versatility | Medium |
0 comments:
Post a Comment