C# Collections

Array Collections File String Windows VB.NET Algorithm ASP.NET Cast Class Compression Convert Data Delegate Directive Enum Exception If Interface Keyword LINQ Loop Method .NET Number Regex Sort StringBuilder Struct Switch Time Value

At its simplest, an object holds a single value. At its most complex, it holds references to many other objects. The .NET Framework provides collections, including List and Dictionary. Collections contain many references or values. They are easier to use in C# programs than arrays.

Overview: This C# page outlines the collection types available. It points to in-depth coverage.

List

First, the List type provides you with an efficient and dynamically-allocated array. It does not provide fast lookup in the general case, which you will want to use Dictionary for. It is excellent when used in loops.

Program that uses List type [C#]

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	// Use the List type.
	List<string> list = new List<string>();
	list.Add("cat");
	list.Add("dog");

	foreach (string element in list)
	{
	    Console.WriteLine(element);
	}
    }
}

Output

cat
dog

Built-in methods. Continuing on, there are many different built-in methods on the List type. We reveal the behavior of these methods through complete examples.

Syntax. We provide further pointers for using the List type's syntax correctly in your program.

List instances. Do you need to create a specific type of List for your program? We have examples for integer Lists, string Lists, static Lists, nested Lists, null Lists, and even the List type used in other contexts.

Custom methods. The built-in methods on the List type are not sufficient for all tasks. If you need to concatenate Lists, compare Lists for equality, remove duplicates from a List, or write a List to the disk, these examples prove helpful.

Convert to strings. Some of the string methods in the C# programming language can be used with the List type. We give examples for the Concat and Join methods and the List type.

Dictionary

Next, the Dictionary type in the base class library is one of the most important ones you need to use for your C# programs. It is an implementation of a hashtable, which is an extremely efficient way to store keys for lookup. The Dictionary in .NET is well-designed.

We try to reference items in a table directly by doing arithmetic operations to transform keys into table addresses. Sedgewick, p. 587

Program that uses Dictionary [C#]

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	// Use the dictionary.
	Dictionary<string, int> dict = new Dictionary<string, int>();
	dict.Add("cat", 1);
	dict.Add("dog", 4);

	Console.WriteLine(dict["cat"]);
	Console.WriteLine(dict["dog"]);
    }
}

Output

1
4

Description. This simple program demonstrates how the Dictionary can be used with type parameters to store keys and values of specific types. You can store and then retrieve keys and values from the Dictionary collection.

Methods. There are many built-in methods on the Dictionary type. They allow you to look up keys (with ContainsKey); or search for values (with ContainsValue). Also, you can check out the ToDictionary method which creates a Dictionary from another type instance.

Sorting. How can you sort the keys or values from a Dictionary? You cannot do this directly; rather, you can acquire a List of the relevant items and then sort that. We show you how.

IEqualityComparer. The Dictionary type uses an IEqualityComparer implementation to determine the hash code for its keys. You can implement this interface with a class yourself, as demonstrated here.

Examples. Additionally, Dot Net Perls provides several examples of Dictionary instances used in different contexts. These examples may be less useful but still can reveal useful tips regarding the syntax of the Dictionary type.

Custom methods. Unfortunately, not all requirements you may have with your collections are satisfied by the built-in methods. For this reason, you will require some custom methods. These methods provide a sample of the custom routines you can construct.

Performance. How fast is the Dictionary type? Fortunately, the Dictionary is well-optimized by the .NET Framework developers, but there are still some ways you can use it that influence performance. We reveal aspects of the Dictionary's performance.

ArrayList

As shown in this program, the ArrayList is a collection found in System.Collections and it can store objects of any derived type. You don't need to worry about the type of the elements, at least until you need to know their types to use them.

Program that uses System.Collections [C#]

using System;
using System.Collections;

class Program
{
    static void Main()
    {
	ArrayList list = new ArrayList();
	list.Add("cat");
	list.Add(2);
	list.Add(false);

	foreach (var element in list)
	{
	    Console.WriteLine(element);
	}
    }
}

Output

cat
2
False

More lists. Although the List generic type is the best implementation available for its purpose on the .NET Framework, there are other versions of lists that you can use instead. We show the LinkedList, ReadOnlyCollection, and SortedList types.

Hashtable

The Hashtable is a lookup data structure that uses a hash code to find elements quickly. The newer Dictionary collection is usually more appropriate for programs when available.

Tuple

You can use the Tuple collection to store data in new versions of the .NET Framework. The Tuple enables you to use strongly typed fields instead of a custom class.

Lookup tables

There are many versions of lookup data structures other than the Hashtable and Dictionary in the .NET Framework. This section covers several of them. It also shows the implementation of a custom MultiMap data structure.

ConcurrentDictionary. The .NET Framework provides the ConcurrentDictionary collection in System.Collections.Concurrent. This type enables you to safely use a lookup table on multiple threads.

BitArray

The BitArray is an abstract data type for representing bit data. It uses an efficient representation of the underlying bits, which can make it a good choice for programs that have many boolean values.

KeyValuePair

One of the most useful data structures in the C# language is the KeyValuePair. This gives you a way to store a key and a value together in a struct. It is a simple form of a tuple. The Dictionary collection uses KeyValuePairs in some of its methods.

Stack

The Stack collection gives you the ability to push and pop elements onto its top. You can implement certain kinds of parsers with stacks. You could use an array for this, but the Stack presents a clearer interface for your code.

Queue

The Queue implements a different algorithm than the Stack. When you remove an element, the first element added is removed instead of the most recently added. The Queue can be used for certain kinds of caches.

Sets

The HashSet implements set logic in its many instance methods. You can use methods such as Union on different HashSets for your program's logic. You could use a Dictionary instead, but the HashSet may be clearer if you are familiar with set theory. Also, the SortedSet is implemented as a binary tree but also provides set logic.

System.Collections.Generic

We provide an overview of the contents of the System.Collections.Generic namespace. These generic collections are the ones you will want to focus on, because they provide superior performance and are easier to use than earlier types (like ArrayList and Hashtable).

Lazy

You can use the Lazy type to implement the lazy instantiation pattern in your programs. We demonstrate the behavior of the Lazy type here.

Note: The Lazy class has nothing to do with the Sleep method.

Capacity

An optimization you can use on your collections is to set capacities in their constructors. This will reduce the number of allocations in some programs, which further reduces the memory pressure and the burden of garbage collection.

Summary

The C# language provides all the features necessary to create your own custom collections. This is in practice rarely needed. Most algorithms can be implemented with the Dictionary and List collections, and these collections also provide some of the best performance.