Collections Overview

All collection classes in the .NET Framework implement some combination of the collection interfaces. These interfaces declare the operations to be performed generically on various types of collections. Figure 27.1 lists some of the interfaces of the .NET Framework collections. All the interfaces in Fig. 27.1 are declared in namespace System.Collections and have generic analogues in namespace System.Collections.Generic. Implementations of these interfaces are provided within the framework. Programmers may also provide implementations specific to their own requirements.

Figure 27.1. Some common collection interfaces.

Interface	Description
ICollection	The root interface in the collections hierarchy from which interfaces IList and IDictionary inherit. Contains a Count property to determine the size of a collection and a CopyTo method for copying a collection's contents into a traditional array.
IList	An ordered collection that can be manipulated like an array. Provides an indexer for accessing elements with an int index. Also has methods for searching and modifying a collection, including Add, Remove, Contains and IndexOf.
IDictionary	A collection of values, indexed by an arbitrary "key" object. Provides an indexer for accessing elements with an object index and methods for modifying the collection (e.g. Add, Remove). IDictionary property Keys contains the objects used as indices, and property Values contains all the stored objects.
IEnumerable	An object that can be enumerated. This interface contains exactly one method, GetEnumerator, which returns an IEnumerator object (discussed in Section 27.3). ICollection implements IEnumerable, so all collection classes implement IEnumerable directly or indirectly.

In earlier versions of C#, the .NET Framework primarily provided the collection classes in the System.Collections and System.Collections.Specialized namespaces. These classes stored and manipulated object references. You could store any object in a collection. One inconvenient aspect of storing object references occurs when retrieving them from a collection. An application normally needs to process specific types of objects. As a result, the object references obtained from a collection typically need to be downcast to an appropriate type to allow the application to process the objects correctly.

The .NET Framework 2.0 now also includes the System.Collections.Generic namespace, which uses the generics capabilities we introduced in Chapter 26. Many of these new classes are simply generic counterparts of the classes in namespace System.Collections. This means that you can specify the exact type that will be stored in a collection. You also receive the benefits of compile-time type checkingthe compiler ensures that you are using appropriate types with your collection and, if not, issues compile-time error messages. Also, once you specify the type stored in a collection, any item you retrieve from the collection will have the correct type. This eliminates the need for explicit type casts that can throw InvalidCastExceptions at execution time if the referenced object is not of the appropriate type. This also eliminates the overhead of explicit casting, improving efficiency.

In this chapter, we demonstrate six collection classesArray, ArrayList, Stack, Hashtable, generic SortedDictionary, and generic LinkedListplus built-in array capabilities. Namespace System.Collections provides several other data structures, including BitArray (a collection of true/false values), Queue and SortedList (a collection of key/value pairs that are sorted by key and can be accessed either by key or by index). Figure 27.2 summarizes many of the collection classes. We also discuss the IEnumerator interface. Collection classes can create enumerators that allow programmers to walk through the collections. Although these enumerators have different implementations, they all implement the IEnumerator interface so that they can be processed polymorphically. As we will soon see, the foreach statement is simply a convenient notation for using an enumerator. In the next section, we begin our discussion by examining enumerators and the collections capabilities for array manipulation.

Figure 27.2. Some collection classes of the .NET Framework.

Class	Implements	Description
System namespace:
Array	IList	The base class of all conventional arrays. See Section 27.3.
System.Collections namespace:
ArrayList	IList	Mimics conventional arrays, but will grow or shrink as needed to accommodate the number of elements. See Section 27.4.1.
BitArray	ICollection	A memory-efficient array of bools.
Hashtable	IDictionary	An unordered collection of keyvalue pairs that can be accessed by key. See Section 27.4.3.
Queue	ICollection	A first-in first-out collection. See Section 25.6.
SortedList	IDictionary	A generic Hashtable that sorts data by keys and can be accessed either by key or by index.
Stack	ICollection	A last-in, first-out collection. See Section 27.4.2.
System.Collections.Generic namespace:
Dictionary< K, E >	IDictionary< K, E >	A generic, unordered collection of keyvalue pairs that can be accessed by key.
LinkedList< E >	ICollection< E >	A doubly linked list. See Section 27.5.2.
List< E >	IList< E >	A generic ArrayList.
Queue< E >	ICollection< E >	A generic Queue.
SortedDictionary< K, E >	IDictionary< K, E >	A Dictionary that sorts the data by the keys in a binary tree. See Section 27.5.1.
SortedList< K, E >	IDictionary< K, E >	A generic SortedList.
Stack< E >	ICollection< E >	A generic Stack.
[Note: All collection classes directly or indirectly implement ICollection and IEnumerable (or the equivalent generic interfaces ICollection< E > and IEnumerable< E > for generic collections).]