Section 26.5. Generic Collections

26.5. Generic Collections

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

26.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. 26.1). The application in Fig. 26.8 is a modification of Fig. 26.7 that uses the generic class SortedDictionary. Generic class SortedDictionary stores its keyvalue pairs in a binary search tree. We discuss binary trees in depth in Section 24.7. 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. Note 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. 26.8 looks remarkably similar to Fig. 26.7. That is the beauty of object-oriented programming.

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

  1  ' Fig. 26.8: SortedDictionaryTest.vb  2  ' Application counts the number of occurrences of each word in a String  3  ' and stores them in a generic sorted dictionary.  4  Imports System.Text.RegularExpressions  5  Imports System.Collections.Generic  6  7  Module StoredDictionaryTest  8     Sub Main()  9        ' create sorted dictionary based on user input 10        Dim dictionary As SortedDictionary(Of String, Integer) = _ 11           CollectWords() 12 13        ' display sorted dictionary content 14        DisplayDictionary(dictionary) 15     End Sub ' Main 16 17     ' create sorted dictionary from user input 18     Private Function CollectWords() As SortedDictionary(Of String, Integer) 19        ' create a new sorted dictionary 20        Dim dictionary As New SortedDictionary(Of String, Integer)() 21 22        Console.WriteLine("Enter a string: ") ' prompt for user input 23       Dim input As String = Console.ReadLine() ' get input 24 25        ' split input text into tokens 26        Dim words As String() = Regex.Split(input, "\s+") 27 28        ' processing input words 29        For Each word As String In words 30           Dim wordKey As String = word.ToLower() ' get word in lowercase 31 32           ' if the dictionary contains the word 33           If dictionary.ContainsKey(wordKey) Then 34              dictionary(wordKey) += 1 35           Else 36              ' add new word with a count of 1 to the dictionary 37              dictionary.Add(wordKey, 1) 38           End If 39        Next 40 41        Return dictionary 42     End Function' CollectWords 43 44     ' display dictionary content 45     Private Sub DisplayDictionary(Of K, V)( _         46        ByVal dictionary As SortedDictionary(Of K, V)) 47 48        Console.WriteLine(vbCrLf & "Sorted dictionary contains:"_ 49           & vbCrLf & "{0,-12}{1,-12}", "Key:", "Value:") 50 51        ' generate output for each key in the sorted dictionary 52        ' by iterating through the Keys property with a For Each statement 53        For Each key As K In dictionary.Keys 54           Console.WriteLine("{0,-12}{1,-12}", key, dictionary(key)) 55        Next 56 57        Console.WriteLine(vbCrLf & "size: {0}", dictionary.Count) 58     End Sub ' DisplayDictionary 59  End Module ' StoredDictionaryTest 

 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 5 contains an Imports statement 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., Integer). We replaced the word Hashtable in lines 10, 18 and 20 with SortedDictionary(Of String, Integer) to create a dictionary of Integer 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 Integer values, there is no longer any need for the downcast in line 34. This allows line 34 to use the much more concise += notation.

Method DisplayDictionary (lines 4558) has been modified to be completely generic. It takes type parameters K and V. These parameters are used in line 46 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 53 as the type of the iteration variable. 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(Of Char, Integer) without modification.

Common Programming Error 26.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 Nothing.

26.5.2. Generic Class LinkedList

Chapter 24 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 Nothing if the node is the first in the list). Similarly, the Next property gets a reference to the subsequent reference in the linked list (or Nothing if the node is the last in the list). We demonstrate a few linked list manipulations in Fig. 26.9.

Figure 26.9. Using LinkedLists.

  1  ' Fig. 26.9: LinkedListTest.vb  2  ' Using LinkedLists.  3  Imports System.Collections.Generic  4  5  Module LinkedListTest  6     Private colors As String() = _  7        {"black", "yellow", "green", "blue", "violet", "silver"}  8     Private colors2 As String() = _  9        {"gold", "white", "brown", "blue", a"gray"} 10 11     ' set up and manipulate LinkedList objects 12     Sub Main() 13        Dim list1 As New LinkedList(Of String)() 14 15        ' add elements to first linked list 16        For Each color As String In colors 17           list1.AddLast(color) 18        Next 19 20        ' add elements to second linked list via constructor 21        Dim list2 As New LinkedList(Of String)(colors2) 22 23        Concatenate(list1, list2) ' concatenate list2 onto list1 24        PrintList(list1) ' print list1 elements 25 26        Console.WriteLine(vbCrLf & _ 27           "Converting strings in list1 to uppercase" & vbCrLf) 28        ToUppercaseStrings(list1) ' convert to uppercase string 29        PrintList(list1) 'print list1 elements 30 31        Console.WriteLine(vbCrLf& _ 32           "Deleting strings between BLACK and BROWN" & vbCrLf) 33        RemoveItemsBetween(list1, "BLACK", "BROWN") 34 35        PrintList(list1) ' print list1 elements 36        PrintReversedList(list1) ' print list in reverse order 37     End Sub ' Main 38 39     ' output list contents 40     Private Sub PrintList(Of E)(ByVal list As LinkedList(Of E)) 41        Console.WriteLine("Linked list: ") 42 43        For Each value As E In list     44           Console.Write("{0} ", value) 45        Next value                      46 47        Console.WriteLine() 48     End Sub ' PrintList 49 50     ' concatenate the second list on the end of the first list 51     Private Sub Concatenate(Of E)(ByVal list1 As LinkedList(Of E), _ 52        ByVal list2 As LinkedList(Of E)) 53        ' concatenate lists by copying element values     54        ' in order from the second list to the first list 55        For Each value As E In list2                      56           list1.AddLast(value) ' add new node            57        Next value                                        58     End Sub ' Concatenate 59 60     ' locate string objects and convert to uppercase 61     Private Sub ToUppercaseStrings(ByVal list As LinkedList(Of String)) 62        ' iterate over the list by using the nodes                       63        Dim currentNode As LinkedListNode(Of String) = list.First        64      65        While currentNode IsNot Nothing                                  66           currentNode.Value = _                                         67              currentNode.Value.ToUpper() ' convert to uppercase         68           currentNode = currentNode.Next ' get next node                69        End While                                                        70     End Sub ' ToUppercaseStrings                                        71 72     ' delete list items between two given items 73     Private Sub RemoveItemsBetween(Of E)(ByVal list As LinkedList(Of E), _ 74        ByVal startItem As E, ByVal endItem As E) 75        ' get the nodes corresponding to the start and end item 76        Dim currentNode As LinkedListNode(Of E) = list.Find(startItem) 77        Dim endNode As LinkedListNode(Of E) = list.Find(endItem)       78 79        ' remove items after the start item 80        ' until we find the last item or the end of the linked list 81        WhilecurrentNode.Next IsNot Nothing And_ 82           Not currentNode.Next.Equals(endNode) 83           ' remove next node            84           list.Remove(currentNode.Next) 85        End While 86     End Sub ' RemoveItemsBetween 87 88     ' print reversed list 89     Private Sub PrintReversedList(Of E)(ByVal list As LinkedList(Of E)) 90        Console.WriteLine("Reversed List:" 91 92        ' iterate over the list by using the nodes 93        Dim currentNode As LinkedListNode(Of E) = list.Last       94         95        While currentNode IsNot Nothing                           96           Console.Write("{0} " , currentNode.Value)              97           currentNode = currentNode.Previous ' get previous node 98        End While                                                 99 100       Console.WriteLine() 101     End Sub 'PrintReversedList 102  End Module ' LinkedListTest 

[View full width]
 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 

Line 3 Imports the LinkedList class. Lines 1321 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 13 and 21). We demonstrate two ways to fill the lists. In lines 1618, we use the For Each statement and method AddLast to fill list1. The AddLast method creates a new LinkedListNode and appends it to the end of the list. There is also an AddFirst method that inserts a node at the beginning of the list. Line 21 invokes the LinkedList constructor that takes a parameter of type IEnumerable(OfString). 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(OfString). The type parameter of this generic IEnumerable matches the type parameter of the generic LinkedList object. This constructor call (line 21) copies the contents of the array colors2 to list2.

Line 23 calls generic method Concatenate (lines 5158) to append all elements of list2 to the end of list1. Line 24 calls method PrintList (lines 4048) to output list1's contents. Line 28 calls method ToUppercaseStrings (lines 6170) to convert each String element to uppercase, then line 29 calls PrintList again to display the modified Strings. Line 33 calls method RemoveItemsBetween (lines 7386) 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 89101) to print the list in reverse order.

Generic method Concatenate (lines 5158) iterates over list2 with a For Each statement and calls method AddLast to append each value to the end of list1. The loop uses the LinkedList class's enumerator to obtain the values of the nodes. The loop 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) also uses a For Each statement to iterate over the values in a LinkedList and output them. Method ToUppercaseStrings (lines 6170) takes a linked list of Strings and converts each String to uppercase. This method replaces the Strings stored in the list, so we cannot use an enumerator (via a For Each statement) as in the previous two methods. Recall that enumerators cannot be used to modify the values of elements in a collection. Instead, we obtain the first LinkedListNode via the First property (line 63), then loop through the list (lines 6569). Each iteration of the loop obtains and updates the contents of currentNode via property Value, using String method ToUpper to create an uppercase version of color. At the end of each iteration, we move the current node to the next node in the list by assigning to currentNode the node obtained by its own Next property (line 68). The Next property of the last node of the list returns Nothing, so when the loop iterates past the end of the list, the loop exits.

Note 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 7386) removes a range of items between two nodes. Lines 7677 obtain the two "boundary" nodes of the range by using method Find. This method performs a linear search, and returns the first node that contains a value equal to the passed argument. Method Find returns Nothing 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 loop in lines 8185 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 84). Method Remove takes a LinkedListNode, deletes that node from the LinkedList and fixes the references of the surrounding nodes. During the Remove call, currentNode's Next property is assigned the node following the removed node, and that node's Previous property is assigned currentNode. The loop continues until there are no nodes left between currentNode and endNode, or until currentNode is the last node in the list. (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 89101) prints the list backwards by navigating the nodes manually. Line 93 obtains the last element of the list via the Last property and stores it in currentNode. The loop in lines 9598 iterates through the list backwards by moving the currentNode reference to the previous node at the end of each iteration, then exits when it moves past the beginning of the list. Note how similar this code is to lines 6569, which iterated through the list from the beginning to the end.