The generic List<T> class is the simplest of the collection classes. You can use it much like an array—you can reference an existing element in a List<T> collection by using ordinary array notation, with square brackets and the index of the element, although you cannot use array notation to add new elements. However, in general, the List<T> class provides more flexibility than arrays and is designed to overcome the following restrictions exhibited by arrays:

The List<T> collection class provides the following features that preclude these limitations:

Here’s an example that shows how you can create, manipulate, and iterate through the contents of a List<int> collection:

using System;
using System.Collections.Generic;
...
List<int> numbers = new List<int>();
// Fill the List<int> by using the Add method
foreach (int number in new int[12]{10, 9, 8, 7, 7, 6, 5, 10, 4, 3, 2, 1})
{
    numbers.Add(number);
}
// Insert an element in the penultimate position in the list, and move the last item up
// The first parameter is the position; the second parameter is the value being inserted
numbers.Insert(numbers.Count-1, 99);
// Remove first element whose value is 7 (the 4th element, index 3)
numbers.Remove(7);
// Remove the element that's now the 7th element, index 6 (10)
numbers.RemoveAt(6);
// Iterate remaining 11 elements using a for statement
Console.WriteLine("Iterating using a for statement:");
for (int i = 0; i < numbers.Count; i++)
{
    int number = numbers[i];  // Note the use of array syntax
    Console.WriteLine(number);
}
// Iterate the same 11 elements using a foreach statement
Console.WriteLine("
Iterating using a foreach statement:");
foreach (int number in numbers)
{
    Console.WriteLine(number);
}

Here is the output of this code:

Iterating using a for statement:
10
9
8
7
6
5
4
3
2
99
1
Iterating using a foreach statement:
10
9
8
7
6
5
4
3
2
99
1

The LinkedList<T> collection class implements a doubly linked list. Each item in the list holds the value for the item together with a reference to the next item in the list (the Next property) and the previous item (the Previous property). The item at the start of the list has the Previous property set to null, and the item at the end of the list has the Next property set to null.

Unlike the List<T> class, LinkedList<T> does not support array notation for inserting or examining elements. Instead, you can use the AddFirst method to insert an element at the start of the list, moving the first item up and setting its Previous property to refer to the new item, or the AddLast method to insert an element at the end of the list, setting the Next property of the previously last item to refer to the new item. You can also use the AddBefore and AddAfter methods to insert an element before or after a specified item in the list (you have to retrieve the item first).

You can find the first item in a LinkedList<T> collection by querying the First property, whereas the Last property returns a reference to the final item in the list. To iterate through a linked list, you can start at one end and step through the Next or Previous references until you find an item with a null value for this property. Alternatively, you can use a foreach statement, which iterates forward through a LinkedList<T> object and stops automatically at the end.

You delete an item from a LinkedList<T> collection by using the Remove, RemoveFirst, and RemoveLast methods.

The following example shows a LinkedList<T> collection in action. Notice how the code that iterates through the list by using a for statement steps through the Next (or Previous) references, only stopping when it reaches a null reference, which is the end of the list:

using System;
using System.Collections.Generic;
...
LinkedList<int> numbers = new LinkedList<int>();
// Fill the List<int> by using the AddFirst method
foreach (int number in new int[] { 10, 8, 6, 4, 2 })
{
    numbers.AddFirst(number);
}
// Iterate using a for statement
Console.WriteLine("Iterating using a for statement:");
for (LinkedListNode<int> node = numbers.First; node != null; node = node.Next)
{
    int number = node.Value;
    Console.WriteLine(number);
}
// Iterate using a foreach statement
Console.WriteLine("
Iterating using a foreach statement:");
foreach (int number in numbers)
{
    Console.WriteLine(number);
}
// Iterate backwards
Console.WriteLine("
Iterating list in reverse order:");
for (LinkedListNode<int> node = numbers.Last; node != null; node = node.Previous)
{
    int number = node.Value;
    Console.WriteLine(number);
}

Here is the output generated by this code:

Iterating using a for statement:
2
4
6
8
10
Iterating using a foreach statement:
2
4
6
8
10
Iterating list in reverse order:
10
8
6
4
2

The Queue<T> class implements a first-in, first-out mechanism. An element is inserted into the queue at the back (the Enqueue operation) and is removed from the queue at the front (the Dequeue operation).

The following code is an example showing a Queue<int> collection and its common operations:

using System;
using System.Collections.Generic;
...
Queue<int> numbers = new Queue<int>();
// fill the queue
Console.WriteLine("Populating the queue:");
foreach (int number in new int[4]{9, 3, 7, 2})
{
    numbers.Enqueue(number);
    Console.WriteLine("{0} has joined the queue", number);
}
// iterate through the queue
Console.WriteLine("
The queue contains the following items:");
foreach (int number in numbers)
{
    Console.WriteLine(number);
}
// empty the queue
Console.WriteLine("
Draining the queue:");
while (numbers.Count > 0)
{
    int number = numbers.Dequeue();
    Console.WriteLine("{0} has left the queue", number);
}

Here is thee output from this code:

Populating the queue:
9 has joined the queue
3 has joined the queue
7 has joined the queue
2 has joined the queue
The queue contains the following items:
9
3
7
2
Draining the queue:
9 has left the queue
3 has left the queue
7 has left the queue
2 has left the queue

The Stack<T> class implements a last-in, first-out mechanism. An element joins the stack at the top (the push operation) and leaves the stack at the top (the pop operation). To visualize this, think of a stack of dishes: new dishes are added to the top and dishes are removed from the top, making the last dish to be placed on the stack the first one to be removed. (The dish at the bottom is rarely used and will inevitably require washing before you can put any food on it, because it will be covered in grime!) Here’s an example—notice the order in which the items are listed by the foreach loop:

using System;
using System.Collections.Generic;
...
Stack<int> numbers = new Stack<int>();
// fill the stack
Console.WriteLine("Pushing items onto the stack:");
foreach (int number in new int[4]{9, 3, 7, 2})
{
    numbers.Push(number);
    Console.WriteLine("{0} has been pushed on the stack", number);
}
// iterate through the stack
Console.WriteLine("
The stack now contains:");
foreach (int number in numbers)
{
    Console.WriteLine(number);
}
// empty the stack
Console.WriteLine("
Popping items from the stack:");
while (numbers.Count > 0)
{
    int number = numbers.Pop();
    Console.WriteLine("{0} has been popped off the stack", number);
}

Here is the output from this program:

Pushing items onto the stack:
9 has been pushed on the stack
3 has been pushed on the stack
7 has been pushed on the stack
2 has been pushed on the stack
The stack now contains:
2
7
3
9
Popping items from the stack:
2 has been popped off the stack
7 has been popped off the stack
3 has been popped off the stack
9 has been popped off the stack

The array and List<T> types provide a way to map an integer index to an element. You specify an integer index within square brackets (for example, [4]), and you get back the element at index 4 (which is actually the fifth element). However, sometimes you might want to implement a mapping in which the type from which you map is not an int but rather some other type, such as string, double, or Time. In other languages, this is often called an associative array. The Dictionary<TKey, TValue> class implements this functionality by internally maintaining two arrays, one for the keys from which you’re mapping and one for the values to which you’re mapping. When you insert a key/value pair into a Dictionary<TKey, TValue> collection, it automatically tracks which key belongs to which value and makes it possible for you to retrieve the value that is associated with a specified key quickly and easily. The design of the Dictionary<TKey, TValue> class has some important consequences:

Here is an example that associates the ages of members of my family with their names and then prints the information:

using System;
using System.Collections.Generic;
...
Dictionary<string, int> ages = new Dictionary<string, int>();
// fill the Dictionary
ages.Add("John", 47);    // using the Add method
ages.Add("Diana", 46);
ages["James"] = 20;      // using array notation
ages["Francesca"] = 18;
// iterate using a foreach statement
// the iterator generates a KeyValuePair item
Console.WriteLine("The Dictionary contains:");
foreach (KeyValuePair<string, int> element in ages)
{
    string name = element.Key;
    int age = element.Value;
    Console.WriteLine("Name: {0}, Age: {1}", name, age);
}

Here is the output from this program:

The Dictionary contains:
Name: John, Age: 47
Name: Diana, Age: 46
Name: James, Age: 20
Name: Francesca, Age: 18

The SortedList<TKey, TValue> class is very similar to the Dictionary<TKey, TValue> class in that you can use it to associate keys with values. The main difference is that the keys array is always sorted. (It is called a SortedList, after all.) It takes longer to insert data into a SortedList<TKey, TValue> object than a SortedDictionary<TKey, TValue> object in most cases, but data retrieval is often quicker (or at least as quick), and SortedList<TKey, TValue> class uses less memory.

When you insert a key/value pair into a SortedList<TKey, TValue> collection, the key is inserted into the keys array at the correct index to keep the keys array sorted. The value is then inserted into the values array at the same index. The SortedList<TKey, TValue> class automatically ensures that keys and values maintain synchronization, even when you add and remove elements. This means that you can insert key/value pairs into a SortedList<TKey, TValue> in any sequence; they are always sorted based on the value of the keys.

Like the Dictionary<TKey, TValue> class, a SortedList<TKey, TValue> collection cannot contain duplicate keys. When you use a foreach statement to iterate through a SortedList<TKey, TValue>, you receive back a KeyValuePair<TKey, TValue> item. However, the KeyValuePair<TKey, TValue> items will be returned sorted by the Key property.

Here is the same example that associates the ages of members of my family with their names and then prints the information, but this version has been adjusted to use a SortedList<TKey, TValue> object rather than a Dictionary<TKey, TValue> collection:

using System;
using System.Collections.Generic;
...
SortedList<string, int> ages = new SortedList<string, int>();
// fill the SortedList
ages.Add("John", 47);    // using the Add method
ages.Add("Diana", 46);
ages["James"] = 20;      // using array notation
ages["Francesca"] = 18;
// iterate using a foreach statement
// the iterator generates a KeyValuePair item
Console.WriteLine("The SortedList contains:");
foreach (KeyValuePair<string, int> element in ages)
{
    string name = element.Key;
    int age = element.Value;
    Console.WriteLine("Name: {0}, Age: {1}", name, age);
}

The output from this program is sorted alphabetically by the names of my family members:

The SortedList contains:
Name: Diana, Age: 46
Name: Francesca, Age: 18
Name: James, Age: 20
Name: John, Age: 47

The HashSet<T> class is optimized for performing set operations such as determining set membership and generating the union and intersect of sets.

You insert items into a HashSet<T> collection by using the Add method, and you delete items by using the Remove method. However, the real power of the HashSet<T> class is provided by the IntersectWith, UnionWith, and ExceptWith methods. These methods modify a HashSet<T> collection to generate a new set that either intersects with, has a union with, or does not contain the items in a specified HashSet<T> collection. These operations are destructive inasmuch as they overwrite the contents of the original HashSet<T> object with the new set of data. You can also determine whether the data in one HashSet<T> collection is a superset or subset of another by using the IsSubsetOf, IsSupersetOf, IsProperSubsetOf, and IsProperSupersetOf methods. These methods return a Boolean value and are nondestructive.

Internally, a HashSet<T> collection is held as a hash table, enabling fast lookup of items. However, a large HashSet<T> collection can require a significant amount of memory to operate quickly.

The following example shows how to populate a HashSet<T> collection and illustrates the use of the IntersectWith method to find data that overlaps two sets:

using System;
using System.Collections.Generic;
...
HashSet<string> employees = new HashSet<string>(new string[] {"Fred","Bert","Harry","John"});
HashSet<string> customers = new HashSet<string>(new string[] {"John","Sid","Harry","Diana"});
employees.Add("James");
customers.Add("Francesca");
Console.WriteLine("Employees:");
foreach (string name in employees)
{
    Console.WriteLine(name);
}
Console.WriteLine("
Customers:");
foreach (string name in customers)
{
    Console.WriteLine(name);
}
Console.WriteLine("
Customers who are also employees:");
customers.IntersectWith(employees);
foreach (string name in customers)
{
    Console.WriteLine(name);
}

This code generates the following output:

Employees:
Fred
Bert
Harry
John
James
Customers:
John
Sid
Harry
Diana
Francesca
Customers who are also employees:
John
Harry

In the next exercise, you will convert the card game that is developed in Chapter 10 to use collections rather than arrays.