Generic Collections

The System.Collections.Generic namespace in the FCL is a new addition for C# 2.0. This namespace contains generic classes that allow us to create collections of specific types. As you saw in Fig. 27.2, many of the classes are simply generic versions of non-generic collections. A couple classes implement new data structures. In this section, we demonstrate generic collections SortedDictionary and LinkedList.

27.5.1. Generic Class SortedDictionary

A dictionary is the general term for a collection of keyvalue pairs. A hash table is one way to implement a dictionary. The .NET Framework provides several implementations of dictionaries, both generic and non-generic (all of which implement the IDictionary interface in Fig. 27.1). The application in Fig. 27.8 is a modification of Fig. 27.7 that uses the generic class SortedDictionary. Generic class SortedDictionary does not use a hash table, but instead stores its keyvalue pairs in a binary search tree. (We discuss binary trees in depth in Section 25.5.) As the class name suggests, the entries in SortedDictionary are sorted in the tree by key. When the key implements generic interface IComparable, the SortedDictionary uses the results of IComparable method CompareTo to sort the keys. Notice that despite these implementation details, we use the same public methods, properties and indexers with classes Hashtable and SortedDictionary in the same ways. In fact, except for the generic-specific syntax, Fig. 27.8 looks remarkably similar to Fig. 27.7. This is the beauty of object-oriented programming.

Figure 27.8. Application counts the number of occurrences of each word in a string and stores them in a generic sorted dictionary.

 1 // Fig. 27.8: SortedDictionaryTest.cs
 2 // Application counts the number of occurrences of each word in a string
 3 // and stores them in a generic sorted dictionary.
 4 using System;
 5 using System.Text.RegularExpressions;
 6 using System.Collections.Generic;
 7
 8 public class SortedDictionaryTest
 9 {
10 public static void Main( string[] args )
11 {
12 // create sorted dictionary based on user input
13 SortedDictionary< string, int > dictionary = CollectWords();
14
15 // display sorted dictionary content
16 DisplayDictionary( dictionary );
17 } // end method Main
18
19 // create sorted dictionary from user input
20 private static SortedDictionary< string, int > CollectWords()
21 {
22 // create a new sorted dictionary
23 SortedDictionary< string, int > dictionary =
24  new SortedDictionary< string, int >(); 
25
26 Console.WriteLine( "Enter a string: " ); // prompt for user input
27 string input = Console.ReadLine(); // get input

28 29 // split input text into tokens 30 string[] words = Regex.Split( input, @"s+" ); 31 32 // processing input words 33 foreach ( string word in words ) 34 { 35 string wordKey = word.ToLower(); // get word in lowercase 36 37 // if the dictionary contains the word 38 if ( dictionary.ContainsKey( wordKey ) ) 39 { 40 ++dictionary[ wordKey ]; 41 } // end if 42 else 43 // add new word with a count of 1 to the dictionary 44 dictionary.Add( wordKey, 1 ); 45 } // end foreach 46 47 return dictionary; 48 } // end method CollectWords 49 50 // display dictionary content 51 private static void DisplayDictionary< K, V >( 52 SortedDictionary< K, V > dictionary ) 53 { 54 Console.WriteLine( " Sorted dictionary contains: {0,-12}{1,-12}", 55 "Key:", "Value:" ); 56 57 // generate output for each key in the sorted dictionary 58 // by iterating through the Keys property with a foreach statement 59 foreach ( K key in dictionary.Keys ) 60 Console.WriteLine( "{0,-12}{1,-12}", key, dictionary[ key ] ); 61 62 Console.WriteLine( " size: {0}", dictionary.Count ); 63 } // end method DisplayDictionary 64 } // end class SortedDictionaryTest

Enter a string:
We few, we happy few, we band of brothers

Sorted dictionary contains:
Key: Value:
band 1
brothers 1
few, 2
happy 1
of 1
we 3

size: 6

Line 6 contains a using directive for the System.Collections.Generic namespace, which contains class SortedDictionary. The generic class SortedDictionary takes two type argumentsthe first specifies the type of key (i.e., string), and the second specifies the type of value (i.e., int). We have simply replaced the word Hashtable in line 13 and lines 2324 with SortedDictionary< string, int > to create a dictionary of int values keyed with strings. Now, the compiler can check and notify us if we attempt to store an object of the wrong type in the dictionary. Also, because the compiler now knows that the data structure contains int values, there is no longer any need for the downcast in line 40. This allows line 40 to use the much more concise prefix increment (++) notation. These are the only changes made to methods Main and CollectWords.

Static method DisplayDictionary (lines 5163) has been modified to be completely generic. It takes type parameters K and V. These parameters are used in line 52 to indicate that DisplayDictionary takes a SortedDictionary with keys of type K and values of type V. We use type parameter K again in line 59 as the type of the iteration key. This use of generics is a marvelous example of code reuse. If we decide to change the application to count the number of times each character appears in a string, method DisplayDictionary could receive an argument of type SortedDictionary< char, int > without modification. This is precisely what you will do in Exercise 27.12.

Performance Tip 27 7

Because class SortedDictionary keeps its elements sorted in a binary tree, obtaining or inserting a keyvalue pair takes O(log n) time, which is fast compared to linear searching then inserting.

Common Programming Error 27 5

Invoking the get accessor of a SortedDictionary indexer with a key that does not exist in the collection causes a KeyNotFoundException. This behavior is different from that of the Hashtable indexer's get accessor, which would return null.

 

27.5.2. Generic Class LinkedList

Chapter 25 began our discussion of data structures with the concept of a linked list. We end our discussion with the .NET Framework's generic LinkedList class. The LinkedList class is a doubly-linked listwe can navigate the list both backwards and forwards with nodes of generic class LinkedListNode. Each node contains property Value and read-only properties Previous and Next. The Value property's type matches LinkedList's single type parameter because it contains the data stored in the node. The Previous property gets a reference to the preceding node in the linked list (or null if the node is the first of the list). Similarly, the Next property gets a reference to the subsequent reference in the linked list (or null if the node is the last of the list). We demonstrate a few linked list manipulations in Fig. 27.9.

Figure 27.9. Using LinkedLists.

 1 // Fig. 27.9: LinkedListTest.cs
 2 // Using LinkedLists.
 3 using System;
 4 using System.Collections.Generic;
 5
 6 public class LinkedListTest
 7 {
 8 private static readonly string[] colors = { "black", "yellow",
 9 "green", "blue", "violet", "silver" };
10 private static readonly string[] colors2 = { "gold", "white",
11 "brown", "blue", "gray" };
12
13 // set up and manipulate LinkedList objects
14 public static void Main( string[] args )
15 {
16 LinkedList< string > list1 = new LinkedList< string >();
17

18 // add elements to first linked list 19 foreach ( string color in colors ) 20 list1.AddLast( color ); 21 22 // add elements to second linked list via constructor 23 LinkedList< string > list2 = new LinkedList< string >( colors2 ); 24 25 Concatenate( list1, list2 ); // concatenate list2 onto list1 26 PrintList( list1 ); // print list1 elements 27 28 Console.WriteLine( " Converting strings in list1 to uppercase " ); 29 ToUppercaseStrings( list1 ); // convert to uppercase string 30 PrintList( list1 ); // print list1 elements 31 32 Console.WriteLine( " Deleting strings between BLACK and BROWN " ); 33 RemoveItemsBetween( list1, "BLACK", "BROWN" ); 34 35 PrintList( list1 ); // print list1 elements 36 PrintReversedList( list1 ); // print list in reverse order 37 } // end method Main 38 39 // output list contents 40 private static void PrintList< E >( LinkedList< E > list ) 41 { 42 Console.WriteLine( "Linked list: " ); 43 44 foreach ( E value in list ) 45 Console.Write( "{0} ", value ); 46 47 Console.WriteLine(); 48 } // end method PrintList 49 50 // concatenate the second list on the end of the first list 51 private static void Concatenate< E >( LinkedList< E > list1, 52 LinkedList< E > list2 ) 53 { 54 // concatenate lists by copying element values 55 // in order from the second list to the first list 56 foreach ( E value in list2 ) 57 list1.AddLast( value ); // add new node 58 } // end method Concatenate 59 60 // locate string objects and convert to uppercase 61 private static void ToUppercaseStrings( LinkedList< string > list ) 62 { 63 // iterate over the list by using the nodes 64 LinkedListNode< string > currentNode = list.First; 65 66 while ( currentNode != null ) 67 { 68 string color = currentNode.Value; // get value in node 69 currentNode.Value = color.ToUpper(); // convert to uppercase 70 71 currentNode = currentNode.Next; // get next node 72 } // end while 73 } // end method ToUppercaseStrings 74 75 // delete list items between two given items 76 private static void RemoveItemsBetween< E >( LinkedList< E > list, 77 E startItem, E endItem ) 78 { 79 // get the nodes corresponding to the start and end item 80 LinkedListNode< E > currentNode = list.Find( startItem ); 81 LinkedListNode< E > endNode = list.Find( endItem ); 82 83 // remove items after the start item 84 // until we find the last item or the end of the linked list 85 while ( ( currentNode.Next != null ) && 86 ( currentNode.Next != endNode ) ) 87 { 88 list.Remove( currentNode.Next ); // remove next node 89 } // end while 90 } // end method RemoveItemsBetween 91 92 // print reversed list 93 private static void PrintReversedList< E >( LinkedList< E > list ) 94 { 95 Console.WriteLine( "Reversed List:" ); 96 97 // iterate over the list by using the nodes 98 LinkedListNode< E > currentNode = list.Last; 99 100 while ( currentNode != null ) 101 { 102 Console.Write( "{0} ", currentNode.Value ); 103 currentNode = currentNode.Previous; // get previous node 104 } // end while 105 106 Console.WriteLine(); 107 } // end method PrintReversedList 108 } // end class LinkedListTest

Linked list:
black yellow green blue violet silver gold white brown blue gray

Converting strings in list1 to uppercase

Linked list:
BLACK YELLOW GREEN BLUE VIOLET SILVER GOLD WHITE BROWN BLUE GRAY

Deleting strings between BLACK and BROWN

Linked list:
BLACK BROWN BLUE GRAY
Reversed List:
GRAY BLUE BROWN BLACK

The using directive in line 4 allows us to use the LinkedList class by its unqualified name. Lines 1623 create LinkedLists list1 and list2 of strings and fill them with the contents of arrays colors and colors2, respectively. Note that LinkedList is a generic class that has one type parameter for which we specify the type argument string in this example (lines 16 and 23). We demonstrate two ways to fill the lists. In lines 1920, we use the foreach statement and method AddLast to fill list1. The AddLast method creates a new LinkedListNode (with the given value available via the Value property), and appends this node to the end of the list. There is also an AddFirst method that inserts a node at the beginning of the list. Line 23 invokes the constructor that takes an IEnumerable< string > parameter. All arrays implicitly inherit from the generic interfaces IList and IEnumerable with the type of the array as the type argument, so the string array colors2 implements IEnumerable< string >. The type parameter of this generic IEnumerable matches the type parameter of the generic LinkedList object. This constructor call copies the contents of the array colors2 to list2.

Line 25 calls generic method Concatenate (lines 5158) to append all elements of list2 to the end of list1. Line 26 calls method PrintList (lines 4048) to output list1's contents. Line 29 calls method ToUppercaseStrings (lines 6173) to convert each string element to uppercase, then line 30 calls PrintList again to display the modified strings. Line 33 calls method RemoveItemsBetween (lines 7690) to remove the elements between "BLACK" and "BROWN", but not including either. Line 35 outputs the list again, then line 36 invokes method PrintReversedList (lines 93107) to print the list in reverse order.

Generic method Concatenate (lines 5158) iterates over list2 with a foreach statement and calls method AddLast to append each value to the end of list1. The LinkedList class's enumerator loops over the values of the nodes, not the nodes themselves, so the iteration variable has type E. Notice that this creates a new node in list1 for each node in list2. One LinkedListNode cannot be a member of more than one LinkedList. Any attempt to add a node from one LinkedList to another generates an InvalidOperationException. If you want the same data to belong to more than one LinkedList, you must make a copy of the node for each list.

Generic method PrintList (lines 4048) similarly uses a foreach statement to iterate over the values in a LinkedList, and outputs them. Method ToUppercaseStrings (lines 6173) takes a linked list of strings and converts each string value to uppercase. This method replaces the strings stored in the list, so we cannot use an enumerator (via a foreach statement) as in the previous two methods. Instead, we obtain the first LinkedListNode via the First property (line 64), and use a while statement to loop through the list (lines 6672). Each iteration of the while statement obtains and updates the contents of currentNode via property Value, using string method ToUpper to create an uppercase version of string color. At the end of each iteration, we move the current node to the next node in the list by assigning currentNode to the node obtained by its own Next property (line 71). The Next property of the last node of the list gets null, so when the while statement iterates past the end of the list, the loop exits.

Notice that it does not make sense to declare ToUppercaseStrings as a generic method, because it uses the string-specific methods of the values in the nodes. Methods PrintList (lines 4048) and Concatenate (lines 5158) do not need to use any string-specific methods, so they can be declared with generic type parameters to promote maximal code reuse.

Generic method RemoveItemsBetween (lines 7690) removes a range of items between two nodes. Lines 8081 obtain the two "boundary" nodes of the range by using method Find. This method performs a linear search on the list, and returns the first node that contains a value equal to the passed argument. Method Find returns null if the value is not found. We store the node preceding the range in local variable currentNode and the node following the range in endNode.

The while statement in lines 8589 removes all the elements between currentNode and endNode. On each iteration of the loop, we remove the node following currentNode by invoking method Remove (line 88). Method Remove takes a LinkedListNode, splices that node out of the LinkedList, and fixes the references of the surrounding nodes. After the Remove call, currentNode's Next property now gets the node following the node just removed, and that node's Previous property now gets currentNode. The while statement continues to loop until there are no nodes left between currentNode and endNode, or until currentNode is the last node in the list. (Note that there is also an overloaded version of method Remove that performs a linear search for the specified value and removes the first node in the list that contains it.)

Method PrintReversedList (lines 93107) prints the list backward by navigating the nodes manually. Line 98 obtains the last element of the list via the Last property and stores it in currentNode. The while statement in lines 100104 iterates through the list backwards by moving the currentNode reference to the previous node at the end of each iteration, then exiting when we move past the beginning of the list. Note how similar this code is to lines 6472, which iterated through the list from the beginning to the end.