Chapter 10. Collections

The intelligent use of collections is in many ways central to building large, well-factored applications. How you store and access your data can strongly influence or even determine everything else. Thus, it is crucial to get it right. This chapter contains tips for working with collections and creating your own.

Pick the Correct Collection Class

Solution: Use Tables 10.1 and 10.2 to help you decide which collection class to use.

Note that only the basic Array type cannot grow beyond its initial size. All the others will manage their internal storage such that objects can be added to it indefinitely (limited by memory, of course).

Table 10.1 Generic Collections

Table 10.2 Nongeneric Collections with No Generic Equivalent

Use Concurrency-Aware Collections

Solution: Either protect the access yourself using thread synchronization objects (see Chapter 23, “Threading and Asynchronous Programming”) or use the collections in the System.Collections.Concurrent namespace. These include the following:

• ConcurrentBag<T> (similar to a set, but duplicates are allowed)

• ConcurrentDictionary<TKey, TValue>

• ConcurrentLinkedList<T>

• ConcurrentQueue<T>

• ConcurrentStack<T>

Initialize a Collection

Solution: You can use object initialization syntax, used for class instances (see Chapter 1, “Type Fundamentals”) and arrays (See Chapter 3, “General Coding”), as in this example:

Iterate over a Collection Independently of Its Implementation

Solution: Rather than writing loops with collection access by index or key, you can use the foreach construct to access any object that implements IEnumerable (or IEnumerable<T>).

This program produces the following output:

Create a Custom Collection

Solution: So that they can play nicely with other components, all collections in .NET should implement a subset of the collection-related interfaces. Table 10.3 briefly describes the common interfaces as they relate to collections.

Table 10.3 Collection Interfaces

Note that although not explicitly stated in the table for space purposes, any interface that inherits from another also includes the base interface’s methods in its own definition.

The example I’ll use over this and the next section implements a binary search tree, complete with three different traversals. We’ll start with the basic definition:

Because binary search trees depend on comparing items to get their ordering correct, we need to ensure that type T is comparable. We’ll implement ICollection<T> and IEnumerable<T> on this collection (neither IList<T> nor IDictionary<TKey, TValue> seem to make sense with a binary search tree).

Here are the ICollection<T> methods:

So what about the IEnumerable<T> implementation? That deserves a topic of its own.

Create Custom Iterators for a Collection

Solution: Recall that binary trees can be traversed in multiple ways: typically pre-order, in-order, and post-order. We can implement all three on our binary tree quite easily using public properties and the yield return keywords. The default will be in-order.

The yield return statement causes the magic. Under the hood, C# is generating code to track which item is the current one in the iteration. Thankfully, we can use this shorthand to avoid that mess.

Let’s look at an example, given the binary tree definition shown in Figure 10.1.

Figure 10.1 A binary search tree over which we’ll iterate in each type of order.

The following sample code will iterate over the tree in each of the three orderings:

Here is the output of this program:

Reverse an Array

Solution: Reversing an array is a fairly common procedure. You can do this yourself, as in this example:

Or you can let the Reverse extension method do it for you:

int[] array = new int[5] {1,2,3,4,5};
IEnumerable<int> reversed = array.Reverse();

This will work on any IEnumerable<T> collection, but you won’t get an array back. Instead, you will get an iterator object that will iterate through the original collection in reverse order.

What you do depends on what you need.

Reverse a Linked List

Solution: Reversing a linked list is a bit more complicated because each node points to the next. Using our own node implementation, here is a way to quickly reverse the list by making each node point to its previous.

The following is the definition for a node:

Here is a method that will reverse a linked list of these nodes:

Get the Unique Elements from a Collection

Solution: To generate a collection without the duplicate items, you need to track which items are found in the collection, and only add them to the new collection if they haven’t been seen before, as in this example:

Count the Number of Times an Item Appears

Solution: This is quite similar to the previous section.

Implement a Priority Queue

Solution: The usual way to implement a priority queue is with a heap, and you can find a lot of examples of this on the Internet. One problem with such implementations is that it is problematic to implement IEnumerable on a heap because the heap does not maintain a strict ordering.

An alternate solution is to use existing collection classes to create a sorted set of queues. It’s perhaps not as efficient, but works well for many applications.

Listing 10.1 contains the full code of a possible implementation of a priority queue.

Listing 10.1 PriorityQueue.cs

Create a Trie (Prefix Tree)

Solution: A trie structure is a good way to quickly look up data by using string prefixes. A trie is an n-ary tree where each child link represents the next part of the key and each leaf node represents the values indexed by the path to that node (see Figure 10.2).

Figure 10.2 A trie’s children represent the next part of the key, until you get to the leaf nodes where the values are stored. In this trie, the words air, aid, car, and cow are indexed.

A trie can be implemented using arrays if the key’s alphabet is known beforehand, but in general a dictionary can be used to look up the next trie node.

The first class we need is a TrieNode that holds the values associated with the node, as well as links to children nodes.

Most of the functionality is in the TrieNode, but for convenience, there is a wrapper that hides some of the complexity:

For a test program, the sample code fills the trie from a list of words and searches for some patterns. You can see this program in the TrieDemo project in this chapter’s source code. Here is the output: