There are six key sets of collection classes, and they differ from each other in terms of how data is inserted, stored, and retrieved. Each generic class is located in the System.Collections.Generic namespace, and their nongeneric equivalents are in the System.Collections namespace.
List Collections: List<T> and ArrayList
The List<T> class, and its nongeneric equivalent, ArrayList, have properties similar to an array. The key difference is that these classes automatically expand as the number of elements increases. (In contrast, an array size is constant.) Furthermore, lists can shrink via explicit calls to TRimToSize() or Capacity (see Figure 12.1 on page 422).
These classes are categorized as list collections whose distinguishing functionality is that each element can be individually accessed by index, just like an array. Therefore, you can set and access elements in the list collection classes using the index operator, where the index parameter value corresponds to the position of an element in the collection. Listing 12.1 shows an example, and Output 12.1 shows the results.
Listing 12.1. Using List<T>
C# is zero-index based; therefore, index zero in Listing 12.1 corresponds to the first element and index 6 indicates the seventh element. Retrieving elements by index does not involve a search. It involves a quick and simple "jump" operation to a location in memory.
Figure 12.1. List<> and ArrayList Class Diagrams
When you use the Add() method, elements maintain the order in which you added them. Therefore, prior to the call to Sort() in Listing 12.1, "Sneezy" is first and "Grumpy" is last. Although List<T> and ArrayList support a Sort() method, nothing states that all list collections require such a method.
There is no support for automatic sorting of elements as they are added. In other words, an explicit call to Sort() is required for the elements to be sorted (items must implement IComparable). To remove an element, you use the Remove() method.
To search either List<T> or ArrayList for a particular element, you use the Contains(), IndexOf(), LastIndexOf(), and BinarySearch() methods. The first three methods search through the array, starting at the first element (the last element for LastIndexOf()), and examine each element until the equivalent one is found. The execution time for these algorithms is proportional to the number of elements searched before a hit occurs. Be aware that the collection classes do not require that all the elements within the collection are unique. If two or more elements in the collection are the same, then IndexOf() returns the first index and LastIndexOf() returns the last index.
BinarySearch() uses a binary search algorithm and requires that the elements be sorted. A useful feature of the BinarySearch() method is that if the element is not found, a negative integer is returned. The bitwise complement (~) of this value is the index of the next element larger than the element being sought, or the total element count if there is no greater value. This provides a convenient means to insert new values into the list at the specific location so as to maintain sorting (see Listing 12.2).
Listing 12.2. Using the Bit Complement of the BinarySearch() Result
Beware that if the list is not first sorted, an element will not necessarily be found, even if it is in the list. The results of Listing 12.2 appear in Output 12.2.
Dictionary Collections: Dictionary<TKey, TValue> and Hashtable
Another category of collection classes is the dictionary classesspecifically, Dictionary<Tkey, Tvalue> and Hashtable (see Figure 12.2). Unlike the list collections, dictionary classes store name/value pairs. The name functions as a unique key that can be used to look up the corresponding element in a manner similar to that of using a primary key to access a record in a database. This adds some complexity to the access of dictionary elements, but because lookups by key are efficient operations, this is a useful collection. Note that the key may be any data type, not just a string or a numeric value.
Figure 12.2. Dictionary and Hashtable Class Diagrams
One option for inserting elements into a dictionary is to use the Add() method, passing both the key and the value, as shown in Listing 12.4.
Listing 12.4. Adding Items to a Dictionary<TKey, TValue>
Listing 12.4 inserts the string "object" using a Guid as its key. If an element with the same key has already been added, an exception is thrown.
An alternative is to use the indexer, as shown in Listing 12.5.
Listing 12.5. Inserting Items in a Dictionary<TKey, TValue> Using the Index Operator
The first thing to observe in Listing 12.5 is that the index operator does not require an integer. Instead, the index data type is specified by the first type parameter, TKey, when declaring a Dictionary<TKey, TValue> variable (in the case of Hashtable, the data type is object). In this example, the key data type used is Guid, and the value data type is string.
The second thing to notice in Listing 12.5 is the reuse of the same index. In the first assignment, no dictionary element corresponds to key. Instead of throwing an out-of-bounds exception, as an array would, dictionary collection classes insert a new object. During the second assignment, an element with the specified key already exists, so instead of inserting an additional element, the existing element corresponding to key is updated from "object" to "byte".
Accessing a value from a dictionary using the index operator () with a nonexistent key throws an exception of type System.Collections.Generic.KeyNotFoundException. The ContainsKey() method, however, allows you to check whether a particular key is used before accessing its value, thereby avoiding the exception. Also, since the keys are stored in a hash algorithm type structure, the search is relatively efficient.
By contrast, checking whether there is a particular value in the dictionary collections is a time-consuming operation with linear performance characteristics. To do this you use the ContainsValue() method, which searches sequentially through each element in the collection.
You remove a dictionary element using the Remove() method, passing the key, not the element value.
There is no particular order for the dictionary classes. Elements are arranged into a hashtable type data structure using hashcodes for rapid retrieval (acquired by calling GetHashCode() on the key). Iterating through a dictionary class using the foreach loop, therefore, accesses values in no particular order. Because both the key and the element value are required to add an element to the dictionary, the data type returned from the foreach loop is KeyValuePair<TKey, TValue> for Dictionary<TKey, TValue>, and DictionaryEntry for Hashtable. Listing 12.6 shows a snippet of code demonstrating the foreach loop with the Dictionary<TKey, TValue> collection class. The output appears in Output 12.3
Listing 12.6. Iterating over Dictionary<TKey, TValue> with foreach
If you want to deal only with keys or only with elements within a dictionary class, they are available via the Keys and Values properties. The data type returned from these properties is of type ICollection, and it is typed in generic or nongeneric form depending on whether a Dictionary<TKey, TValue> or Hashtable collection is used. The data returned by these properties is a reference to the data within the original dictionary collection, so changes within the dictionary are automatically reflected in the ICollection type returned by the Keys and Values properties.
Sorted Collections: SortedDictionary<TKey, TValue> and SortedList<T>
The sorted collection classes (see Figure 12.3 on page 431) differ from unsorted implementation collections in that the elements are sorted by key for SortedDictionary<TKey, TValue> and by value for SortedList<T>. (There is also a nongeneric SortedList implementation.) A foreach iteration of sorted collections returns the elements sorted in key order (see Listing 12.7).
Listing 12.7. Using SortedDictionary<TKey, TValue>
The results of Listing 12.7 appear in Output 12.4.
Note that the elements in the key are in alphabetical rather than numerical order, because the data type of the key is a string, not an integer.
Figure 12.3. SortedList<> and SortedDictionary<> Class Diagrams
When inserting or removing elements from a sorted dictionary collection, maintenance of order within the collection slightly increases execution time when compared to the straight dictionary classes described earlier. Behaviorally, there are two internal arrays, one for key retrieval and one for index retrieval. On a System.Collections.Sorted sorted list, indexing is supported via the GetByIndex() and SetByIndex() methods. With System.Collections.Generic.SortedList<TKey, TValue>, the Keys and Values properties return IList<TKey> and IList<TValue> instances, respectively. These methods enable the sorted list to behave both as a dictionary and as a list type collection.
Stack Collections: Stack<T> and Stack
Chapter 11 discussed the stack collection classes (see Figure 12.4). The stack collection classes are designed as last in, first out (LIFO) collections. The two key methods are Push() and Pop().
To access the elements on the stack without modifying the stack, you use the Peek() and Contains() methods. The Peek() method returns the next element that Pop() will retrieve.
As with most collection classes, you use the Contains() method to determine whether an element exists anywhere in the stack. As with all collections, it is also possible to use a foreach loop to iterate over the elements in a stack. This allows you to access values from anywhere in the stack. Note, however, that accessing a value via the foreach loop does not remove it from the stack. Only Pop() provides this functionality.
Figure 12.4. Stack<T> and Stack Class Diagrams
Queue Collections: Queue<T> and Queue
Queue collection classes, shown in Figure 12.5, are identical to stack collection classes, except they follow the ordering pattern of first in, first out (FIFO). In place of the Pop() and Push() methods are the Enqueue() and Dequeue() methods. The queue collection behaves like a circular array or pipe. You place objects into the queue at one end using the Enqueue() method, and you remove them from the other end using the Dequeue() method. As with stack collection classes, the objects do not have to be unique, and queue collection classes automatically increase in size as required. When data is no longer needed, you recover the capacity using the TRimToSize() method.
Figure 12.5. Queue<T> and Queue Class Diagrams
Linked Lists: LinkedList<T>
In addition, System.Collections.Generic supports a linked list collection that enables both forward and reverse traversal. Figure 12.6 shows the class diagram. Notice there is no corresponding nongeneric type.
Figure 12.6. LinkedList<T> and LinkedListNode<T> Class Diagram