Post
Ask Question

Preparing .NET Interview: Sorted Collections - Part Nine

I am here to continue the series related to .NET interview preparation. Today, we will discuss the common questions related to the sorted collections and present the answers in an easy way.
 
Link to previous posts,
So let’s take questions one by one,
 
1. What are sorted collections in .NET?
 
The sorted collections are the collections used to provide the built-in sorting capability. Following are the sorted collections available in .NET.
  • SortedList
  • SortedDictionary
  • SortedSet
2. What are the similarities and the differences between Sorted Dictionary and Sorted List? Also, provide the uses scenarios.
 
Both SortedDictionary and SortedList are used in the cases when sorting is required to happen automatically based on the keys. However, they have some differences in the uses and performance as follows.
  • SortedDictionary(K, V) generic class is a binary search tree with O(log n) retrieval. On the other side, SortedList (K, V) generic class uses binary search over the sorted array and it too has O (log n) retrieval.
  • For unsorted data, SortedDictionary has faster addition and removal i.e. O(log n)than SortedList O (n).
  • For already sorted data, SortedList is faster i.e. O (1) than SortedDictionaryO(log n).
  • SortedDictionary can only be accessed, using a key whereas SortedList can be retrieved both by key and an index.
  • SortedList uses less memory than SortedDictionary.
To summarize, SortedDictionary<K, V> should be used, when-
  • More inserts and delete operations are required.
  • Data is not ordered.
  • Key access is enough and index access is not required.
  • Memory is not a bottleneck
Sotted List<K, V> should be used, when-
  • More lookups, fewer inserts, and delete operations are required.
  • Data is already sorted (if not all, mostly it is sorted)
  • Index access is required.
  • Memory is an overhead.
3. How to use generic SortedList. Explain with example.
 
Generic SortedList is similar to the list with the difference that it automatically keeps the data sorted by the keys.
 
Let’s understand SortedList by a simple example.
  1. SortedList<int, string>mySortedList = newSortedList<int, string>();  
  2.   
  3. mySortedList.Add(102, "Prakash");  
  4. mySortedList.Add(101, "Aradhana");  
  5. mySortedList.Add(104, "Beeda");  
  6. mySortedList.Add(103, "Satna");  
  7. mySortedList.Add(105, "Amarpatan");  
  8.   
  9. //Get the index by passing key  
  10. intfirstKey = mySortedList.Keys.First();  
  11. intfirstIndex = mySortedList.IndexOfKey(firstKey);   
  12. Console.WriteLine("Index of key {0} is: {1}", firstKey, firstIndex);  
  13.   
  14. //Get the value by passing the index  
  15. Console.WriteLine("Value of index {0} is: {1}", firstIndex, mySortedList.Values[firstIndex]);  
  16.   
  17. //Get the value by key as default indexer is implemented using key  
  18. Console.WriteLine("Value of key {0} is: {1}", firstKey, mySortedList[firstKey]);  
  19.   
  20. Console.WriteLine("\nPrinting the SortedList:");  
  21. foreach (varkvpinmySortedList)  
  22. {  
  23.    Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value);  
  24. }  
Output
 
 
As you can see, that although we have entered the keys in a random order SortedList has automatically adjusted the sort order. You can also see that SortedList exposes the index property apart from the keys and values.
 
4. How to use SortedDictionary. Explain with example.
 
SortedDictionary works similar to a dictionary except that it automatically keeps the data sorted by the keys.
 
Let’s understand SortedDictionary by a simple example.
  1. SortedDictionary < int, string > myDict = newSortedDictionary < int, string > ();  
  2. myDict.Add(102, "Prakash");  
  3. myDict.Add(101, "Aradhana");  
  4. myDict.Add(104, "Beeda");  
  5. myDict.Add(103, "Satna");  
  6. myDict.Add(105, "Amarpatan");  

  8. //Get the index by passing key  

  10. intfirstKey = myDict.Keys.First();  
  11. //intfirstIndex = myDict.IndexOfKey(firstKey); //Error as SortedDictionary can't be accessed by index  
  12. //Get the value by key as default indexer is implemented using key   
  13. Console.WriteLine("Value of key {0} is: {1}", firstKey, myDict[firstKey]);  
  14. Console.WriteLine("\nPrinting the SortedDictionary:");  
  15. foreach(varkvpinmyDict)  
  16. {  
  17.     Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value);  
  18. }  
Output
 
 
5. How to use SortedSet. Explain with example.
 
SortedSet is similar to HashSet with an additional built-in sorting functionality. HashSet is a unique non-ordered collection, optimized for lookups and SortedSet is one step, ahead with the support of sorting.
 
Let’s understand SortedSet by a simple example.
  1. SortedSet < string > mySet = newSortedSet < string > ();  
  2. mySet.Add("Prakash");  
  3. mySet.Add("Aradhana");  
  4. mySet.Add("Beeda");  
  5. mySet.Add("Satna");  
  6. mySet.Add("Prakash");  
  7. mySet.Add("Beeda");  
  8. mySet.Add("Amarpatan");  
  9. Console.WriteLine("Printing the SortedSet:");  
  10. foreach(var value inmySet)  
  11. {  
  12.     Console.WriteLine(value);  
  13. }  
  14. mySet.Remove("Prakash");  
  15. Console.WriteLine("\nPrinting the SortedSet After Removing an element:");  
  16. foreach(var value inmySet)  
  17. {  
  18.     Console.WriteLine(value);  
  19. }  
Output
 
 
As you can see in the output:
  • SortedSet removes the duplicate values, even if we manually add them (Prakash and Beeda added twice, but in the output, they are appearing only once).
  • Sorting is done automatically after adding values.
  • Sorting is maintained for the remaining values after removing an existing element.
You can also download the attached demo project (SortedCollectionsDemo.zip) to go through the source code used in the article.


Similar Articles