Let's look at an example to see how generics work. Suppose that you need to implement your own custom stack class. A stack is a last-in, first-out (LIFO) data structure that enables you to push items into and pop items out of the stack. One possible implementation is:

public class MyStack
{
    private int[] _elements;
    private int _pointer;

    public MyStack(int size)
    {
        _elements = new int[size];

_pointer = 0;
    }

    public void Push(int item)
    {
        if (_pointer > _elements.Length - 1)
        {
            throw new Exception("Stack is full.");
        }
        _elements[_pointer] = item;
        _pointer++;
    }

    public int Pop()
    {
        _pointer--;
        if (_pointer < 0)
        {
            throw new Exception("Stack is empty.");
        }
        return _elements[_pointer];
    }
}

In this case, the MyStack class allows data of int type to be pushed into and popped out of the stack. The following statements show how to use the MyStack class:

MyStack stack = new MyStack(3);
            stack.Push(1);
            stack.Push(2);
            stack.Push(3);

            Console.WriteLine(stack.Pop()); //---3---
            Console.WriteLine(stack.Pop()); //---2---
            Console.WriteLine(stack.Pop()); //---1---

As you can see, this stack implementation accepts stack items of the int data type. To use this implementation for another data type, say String, you need to create another class that uses the string type. Obviously, this is not a very efficient way of writing your class definitions because you now have several versions of essentially the same class to maintain.

A common way of solving this problem is to use the Object data type so that the compiler will use late-binding during runtime:

public class MyStack
{
    private object[] _elements;
    private int _pointer;

    public MyStack(int size)

{
        _elements = new object[size];
        _pointer = 0;
    }

    public void Push(object item)
    {
        if (_pointer > _elements.Length - 1)
        {
            throw new Exception("Stack is full.");
        }
        _elements[_pointer] = item;
        _pointer++;
    }

    public object Pop()
    {
        _pointer--;
        if (_pointer < 0)
        {
            throw new Exception("Stack is empty.");
        }
        return _elements[_pointer];
    }
}

One problem with this approach is that when you use the stack class, you may inadvertently pop out the wrong data type, as shown in the following highlighted code:

MyStack stack = new MyStack(3);
            stack.Push(1);
            stack.Push(2);
            stack.Push("A");

            //---invalid cast---
            int num = (int) stack.Pop();

Because the Pop() method returns a variable of Object type, IntelliSense cannot detect during design time if this code is correct. It is only during runtime that when you try to pop out a string type and try to typecast it into an int type that an error occurs. Besides, type casting (boxing and unboxing) during runtime incurs a performance penalty.

To resolve this inflexibility, you can make use of generics.

Generic Classes

Using generics, you do not need to fix the data type of the items used by your stack class. Instead, you use a generic type parameter (<T>) that identifies the data type parameter on a class, structure, interface, delegate, or procedure. Here's a rewrite of the MyStack class that shows the use of generics:

public class MyStack<T>
{
    private T[] _elements;
    private int _pointer;

    public MyStack(int size)
    {
        _elements = new T[size];
        _pointer = 0;
    }

    public void Push(T item)
    {
        if (_pointer > _elements.Length - 1)
        {
            throw new Exception("Stack is full.");
        }
        _elements[_pointer] = item;
        _pointer++;
    }

    public T Pop()
    {
        _pointer--;
        if (_pointer < 0)
        {
            throw new Exception("Stack is empty.");
        }
        return _elements[_pointer];
    }
}

As highlighted, you use the type T as a placeholder for the eventual data type that you want to use for the class. In other words, during the design stage of this class, you do not specify the actual data type that the MyStack class will deal with. The MyStack class is now known as a generic type.

When declaring the private member array _element, you use the generic parameter T instead of a specific type such as int or string:

private T[] _elements;

In short, you replace all specific data types with the generic parameter T.

You can use any variable name you want to represent the generic parameter. T is chosen as the generic parameter for illustration purposes.

If you want the MyStack class to manipulate items of type int, specify that during the instantiation stage (int is called the type argument):

MyStack<int> stack = new MyStack<int>(3);

The stack object is now known as a constructed type, and you can use the MyStack class normally:

stack.Push(1);
            stack.Push(2);
            stack.Push(3);

A constructed type is a generic type with at least one type argument.

In Figure 9-1 IntelliSense shows that the Push() method now accepts arguments of type int.

Figure 9.1. Figure 9-1

Trying to push a string value into the stack like this:

stack.Push("A");  //---Error---

generates a compile-time error. That's because the compiler checks the data type used by the MyStack class during compile time. This is one of the key advantages of using generics in C#.

To use the MyStack class for String data types, you simply do this:

MyStack<string> stack = new MyStack<string>(3);
            stack.Push("A");
            stack.Push("B");
            stack.Push("C");

Figure 9-2 summarizes the terms used in a generic type.

Figure 9.2. Figure 9-2

public T Pop()
    {
        _pointer--;
        if (_pointer < 0)
        {
            throw new Exception("Stack is empty.");
        }
        return _elements[_pointer];
    }

public T Pop()
    {
        _pointer--;
        if (_pointer < 0)
        {
            return default(T);
        }
        return _elements[_pointer];
    }

MyStack<int> stack = new MyStack<int>(3);
            stack.Push(1);
            stack.Push(2);
            stack.Push(3);

            Console.WriteLine(stack.Pop()); //---3---
            Console.WriteLine(stack.Pop()); //---2---
            Console.WriteLine(stack.Pop()); //---1---
            Console.WriteLine(stack.Pop()); //---0---

MyStack<string> stack = new MyStack<string>(3);
            stack.Push("A");
            stack.Push("B");
            stack.Push("C");

            Console.WriteLine(stack.Pop()); //---"C"---
            Console.WriteLine(stack.Pop()); //---"B"---
            Console.WriteLine(stack.Pop()); //---"A"---
            Console.WriteLine(stack.Pop()); //---""---

Using Constraints in a Generic Type

Using the MyStack class, suppose that you want to add a method called Find() that allows users to check if the stack contains a specific item. You implement the Find() method like this:

public class MyStack<T>
{
    private T[] _elements;
    private int _pointer;

    public MyStack(int size)
    {
        _elements = new T[size];
        _pointer = 0;
    }

    public void Push(T item)
    {
        if (_pointer > _elements.Length - 1)
        {
            throw new Exception("Stack is full.");
        }
        _elements[_pointer] = item;
        _pointer++;
    }

    public T Pop()
    {
        _pointer--;
        if (_pointer < 0)
        {
            return default(T);
            //throw new Exception("Stack is empty.");
        }

return _elements[_pointer];
    }

    public bool Find(T keyword)
    {
        bool found = false;
        for (int i=0; i<_pointer; i++)
        {
            if (_elements[i] == keyword)
            {
                found = true;
                break;
            }
        }
        return found;
    }
}

But the code will not compile. This is because of the statement:

if (_elements[i] == keyword)

That's because the compiler has no way of knowing if the actual type of item and keyword (type T) support this operator (see Figure 9-3). For example, you cannot by default compare two struct objects.

Figure 9.3. Figure 9-3

A better way to resolve this problem is to apply constraint to the generic class so that only certain data types can be used. In this case, because you want to perform comparison in the Find() method, the data type used by the generic class must implement the IComparable<T> interface. This is enforced by using the where keyword:

public class MyStack<T> where T : IComparable<T>
{
    private T[] _elements;
    private int _pointer;

    public MyStack(int size)
    {
        _elements = new T[size];
        _pointer = 0;
    }

    public void Push(T item)

{
        if (_pointer > _elements.Length - 1)
        {
            throw new Exception("Stack is full.");
        }
        _elements[_pointer] = item;
        _pointer++;
    }

    public T Pop()
    {
        _pointer--;
        if (_pointer < 0)
        {
            return default(T);
        }
        return _elements[_pointer];
    }

    public bool Find(T keyword)
    {
        bool found = false;
        for (int i=0; i<_pointer; i++)
        {
            if (_elements[i].CompareTo(keyword) == 0)
            {
                found = true;
                break;
            }
        }
        return found;
    }
}

For the comparison, you use the CompareTo() method to compare two items of type T (which must implement the IComparable interface). The CompareTo() method returns 0 if the two objects are equal. You can now search for an item by using the Find() method:

MyStack<string> stack = new MyStack<string>(3);
            stack.Push("A");
            stack.Push("B");
            stack.Push("C");

            if (stack.Find("B"))
                Console.WriteLine("Contains B");

In this case, the code works because the string type implements the IComparable interface. Suppose that you have the following Employee class definition:

public class Employee
{
    public string ID { get; set; }
    public string Name { get; set; }
}

When you try to use the MyStack class with the Employee class, you get an error:

MyStack<Employee> stack = new MyStack<Employee>(3);  //---Error---

That's because the Employee class does not implement the IComparable<T> interface. To resolve this, simply implement the IComparable<Employee> interface in the Employee class and implement the CompareTo() method:

public class Employee : IComparable<Employee>
{
    public string ID { get; set; }
    public string Name { get; set; }

    public int CompareTo(Employee obj)
    {
        return this.ID.CompareTo(obj.ID);
    }
}

You can now use the Employee class with the generic MyStack class:

MyStack<Employee> stack = new MyStack<Employee>(2);
            stack.Push(new Employee() { ID = "123", Name = "John" });
            stack.Push(new Employee() { ID = "456", Name = "Margaret" });

            Employee e1 = new Employee() { ID = "123", Name = "John" };

            if (stack.Find(e1))
                Console.WriteLine("Employee found.");

Specifying Multiple Constraints

You can specify multiple constraints in a generic type. For example, if you want the MyStack class to manipulate objects of type Employee and also implement the Icomparable interface, you can declare the generic type as:

public class MyStack<T> where T : Employee,  IComparable<T>
{
    //...
}

Here, you are constraining that the MyStack class must use types derived from Employee and they must also implement the IComparable interface.

Note

The base class constraint must always be specified first, before specifying the interface.

Assuming that you have the following Manager class deriving from the Employee class:

public class Manager : Employee, IComparable<Manager>
{
    public int CompareTo(Manager obj)
    {
        return base.CompareTo(obj);
    }
}

The following statement is now valid:

MyStack<Manager> stackM = new MyStack<Manager>(3);

Multiple Type Parameter

So far you have seen only one type parameter used in a generic type, but you can have multiple type parameters. For example, the following MyDictionary class uses two generic type parameters — K and V:

public class MyDictionary<K, V>
{
    //...
}

To apply constraints on multiple type parameters, use the where keyword multiple times:

public class MyDictionary<K, V>
    where K : IComparable<K>
    where V : ICloneable
{
    //...
}

Generic Interfaces

Generics can also be applied on interfacesa. The following example defines the IMyStack interface:

interface IMyStack<T> where T : IComparable<T>
{
    void Push(T item);
    T Pop();
    bool Find(T keyword);
}

A class implementing a generic interface must supply the same type parameter as well as satisfy the constraints imposed by the interface.

The following shows the generic MyStack class implementing the generic IMyStack interface:

public class MyStack<T> : IMyStack<T> where T : IComparable<T>
{
    //...
}

Figure 9-4 shows the error reported by Visual Studio 2008 if the generic MyStack class does not provide the constraint imposed by the generic interface.

Figure 9.4. Figure 9-4

public struct Coordinate
{
    public int x, y, z;
}

public struct Coordinate<T>
{
    public T x, y, z;
}

Coordinate<int> pt1;
            pt1.x = 5;
            pt1.y = 6;
            pt1.z = 7;

Coordinate<float> pt2;
            pt2.x = 2.0F;
            pt2.y = 6.3F;
            pt2.z = 2.9F;

public class SomeClass
{
    public void DoSomething<T>(T t)
    {
    }
}

SomeClass sc = new SomeClass();
            sc.DoSomething<int>(3);

sc.DoSomething("This is a string"); //---T is String---

public class SomeClass
{
    public void DoSomething<T>(T t) where T : IComparable<T>
    {
    }
}

public class SomeClass<T> where T : IComparable<T>
{
    public void DoSomething(T t)
    {
    }
}

SomeClass<int> sc = new SomeClass<int>();
            sc.DoSomething(3);

public class SomeClass
{
    public static void DoSomething<T>(T t) where T : IComparable<T>
    {
    }
}

SomeClass.DoSomething(3);
            //---or---
            SomeClass.DoSomething<int>(3);

MyStack<string> stack1 = new MyStack<string>(4);
            stack1.Push("A");
            stack1.Push("B");

            MyStack<string> stack2 = new MyStack<string>(2);
            stack2.Push("C");
            stack2.Push("D");

            stack1 += stack2;

public class MyStack<T> where T : IComparable<T>
{
    private T[] _elements;
    private int _pointer;

    public MyStack(int size)
    {
        _elements = new T[size];
        _pointer = 0;
    }

    public void Push(T item)
    {
        if (_pointer > _elements.Length - 1)
        {
            throw new Exception("Stack is full.");
        }
        _elements[_pointer] = item;
        _pointer++;
    }

    public T Pop()
    {
        _pointer--;
        if (_pointer < 0)
        {
            return default(T);
        }
        return _elements[_pointer];
    }

public bool Find(T keyword)
    {
        bool found = false;
        for (int i = 0; i < _pointer; i++)
        {
            if (_elements[i].CompareTo(keyword) == 0)
            {
                found = true;
                break;
            }
        }
        return found;
    }

    public bool Empty
    {
        get{
            return (_pointer <= 0);
        }
    }

    public static MyStack<T> operator +
        (MyStack<T> stackA, MyStack<T> stackB)
    {
        while (!stackB.Empty)
        {
            T item = stackB.Pop();
            stackA.Push(item);
        }
        return stackA;
    }
}

stack1 += stack2;
            while (!stack1.Empty)
                Console.WriteLine(stack1.Pop());

C
D
B
A

public class SomeClass<T>
{
    public delegate void MethodDelegate(T t);
    public void DoSomething(T t)
    {
    }
}

SomeClass<int> sc = new SomeClass<int>();
            SomeClass<int>.MethodDelegate del;
            del = new SomeClass<int>.MethodDelegate(sc.DoSomething);

del = sc.DoSomething;

The .NET Framework class library contains a number of generic classes that enable users to create strongly typed collections. These classes are grouped under the System.Collections.Generic namespace (the nongeneric versions of the classes are contained within the System.Collections namespace). The following tables show the various classes, structures, and interfaces contained within this namespace.

The following table provides a look at the classes contained within the System.Collections.Generic namespace.

The structures contained within the System.Collections.Generic namespace are described in the following table.

Following are descriptions of the interfaces contained within the System.Collections.Generic namespace.

Prior to .NET 2.0, all the data structures contained in the System.Collection namespace are object-based. With .NET 2.0, Microsoft has released generic equivalents of some of these classes. The following table shows the mapping of these classes in the two namespaces.

One of the new classes in the System.Collection.Generic namespace is the LinkedList<T> generic class. A linked list is a data structure containing a series of interconnected nodes. Linked lists have wide usage in computer science and are often used to store related data.

There are several types of linked lists:

Figure 9-5 shows a singly linked list. Every node has a field that "points" to the next node. To move from one node to another (known as list traversal), you start from the first node and follow the links leading to the next node.

Figure 9.5. Figure 9-5

Figure 9-6 shows a doubly linked list. Doubly linked list nodes contains an additional field to point to the previous node. You can traverse a doubly linked list in either direction. The LinkedList<T> class implements a doubly linked list.

Figure 9.6. Figure 9-6

Figure 9-7 shows a circularly linked list. A circularly linked list has its first and last node linked together. A circularly linked list can either be a singly linked list (as shown in Figure 9-5) or a doubly linked list.

Figure 9.7. Figure 9-7

The next example shows how to use the LinkedList<T> class available in the .NET Framework to store a list of random numbers. As each random number is generated, it is inserted into the linked list in numeric sorted order (from small to big). The end result is a list of sorted random numbers. Specifically, the example uses the LinkedList<T> class members shown in the following table.

Each node in the LinkedList<T> class is an object of type LinkedListNode<T>. The following table shows the properties in the LinkedListNode<T> that are used in this example.

Now for the example, first create an instance of the LinkedList<T> class using the int type:

LinkedList<int> Numbers = new LinkedList<int>();

Define the InsertNumber() function, which accepts an int parameter:

private void InsertNumber(int number)
        {
            //---start from first node---
            LinkedListNode<int> currNode = Numbers.First;
            LinkedListNode<int> newNode = new LinkedListNode<int>(number);

            if (currNode == null)
            {
                Numbers.AddFirst(newNode);
                return;
            }
            while (currNode != null)
            {
                if (currNode.Value > number)
                {
                    if (currNode.Previous != null)
                        //---Case 1 - add the node to the previous node---
                        Numbers.AddAfter(currNode.Previous, newNode);

else
                        //--- Case 2 - the current node is the first node---
                        Numbers.AddBefore(currNode, newNode);
                    break;
                }
                else if (currNode.Next == null)
                {
                    //--- Case 3 - if last node has been reached---
                    Numbers.AddAfter(currNode, newNode);
                    break;
                }
                //---traverse to the next node---
                currNode = currNode.Next;
            }
        }

The InsertNumber() function initially creates a new node to contain the random number generated. It then traverses the linked list to find the correct position to insert the number. Take a look at the different possible cases when inserting a number into the linked list.

Figure 9-8 shows the case when the node to be inserted (11) is between two nodes (9 and 15, the current node). In this case, it must be added after node 9.

Figure 9.8. Figure 9-8

Figure 9-9 shows the case when the node to be inserted (11) is smaller than the first node (current node) in the linked list. In this case, it must be added before the current node.

Figure 9.9. Figure 9-9

Figure 9-10 shows the case when the node to be inserted is larger than the last node (current node) in the linked list. In this case, it must be added after the current node.

Figure 9.10. Figure 9-10

To insert a list of random numbers into the linked list, you can use the following statements:

Random rnd = new Random();
            for (int i = 0; i < 20; i++)
                InsertNumber(rnd.Next(100)); //---random number from 0 to 100---

To print out all the numbers contained within the linked list, traverse the link starting from the first node:

//---traverse forward---
            LinkedListNode<int> node = Numbers.First;
            while (node != null)
            {
                Console.WriteLine(node.Value);
                node = node.Next;
            }

The result is a list of 20 random numbers in sorted order.

Alternatively, you can traverse the list backward from the last node:

//---traverse backward---
            LinkedListNode<int> node = Numbers.Last;
            while (node != null)
            {
                Console.WriteLine(node.Value);
                node = node.Previous;
            }

The result would be a list of random numbers in reverse-sort order.

The System.Collections.ObjectModel namespace in the .NET class library contains several generic classes that deal with collections. These classes are described in the following table.

Let's take a look at Collection<T>, one of the classes available. It is similar to the generic List<T> class. Both Collection<T> and List<T> implement the IList<T> and ICollection<T> interfaces. The main difference between the two is that Collection<T> contains virtual methods that can be overridden, whereas List<T> does not have any.

The following code example shows how to use the generic Collection<T> class:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections.ObjectModel;

namespace CollectionEg1
{
    class Program
    {
        static void Main(string[] args)
        {
            Collection<string> names = new Collection<string>();
            names.Add("Johnny");
            names.Add("Michael");
            names.Add("Wellington");
            foreach (string name in names)
            {
                Console.WriteLine(name);
            }
            Console.ReadLine();
        }
    }
}

Here's the example's output:

Johnny
Michael
Wellington

To understand the usefulness of the generic Collection<T> class, consider the following example where you need to write a class to contain the names of all the branches a company has:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Collections.ObjectModel;

namespace CollectionEg2
{
    class Program
    {
        static void Main(string[] args)
        {
        }
    }

    public class Branch
    {
        private List<string> _branchNames = new List<string>();
        public List<string> BranchNames
        {
            get
            {
                return _branchNames;
            }
        }
    }
}

In this example, the Branch class exposes a public read-only property called BranchNames of type List<T>. To add branch names to a Branch object, you first create an instance of the Branch class and then add individual branch names to the BranchNames property by using the Add() method of the List<T> class:

static void Main(string[] args)
        {
            Branch b = new Branch();
            b.BranchNames.Add("ABC");
            b.BranchNames.Add("XYZ");
        }

Suppose now that your customers request an event for the Branch class so that every time a branch name is deleted, the event fires so that the client of Branch class can be notified. The problem with the generic List<T> class is that there is no way you can be informed when an item is removed.

A better way to resolve this issue is to expose BranchName as a property of type Collection<T> instead of List<T>. That's because the generic Collection<T> type provides four overridable methods — ClearItems(), InsertItem(), RemoveItem(), and SetItem() — which allow a derived class to be notified when a collection has been modified.

Here's how rewriting the Branch class, using the generic Collection<T> type, looks:

public class Branch
    {
        public Branch()
        {
            _branchNames = new BranchNamesCollection(this);
        }

        private BranchNamesCollection _branchNames;
        public Collection<string> BranchNames
        {
            get
            {
                return _branchNames;
            }
        }

        //---event raised when an item is removed---
        public event EventHandler ItemRemoved;

        //---called from within the BranchNamesCollection class---
        protected virtual void RaiseItemRemovedEvent(EventArgs e)
        {
            if (ItemRemoved != null)
            {
                ItemRemoved(this, e);
            }
        }

        private class BranchNamesCollection : Collection<string>
        {
            private Branch _b;
            public BranchNamesCollection(Branch b)
            {
                _b = b;
            }

            //---fired when an item is removed---
            protected override void RemoveItem(int index)
            {
                 base.RemoveItem(index);
                _b.RaiseItemRemovedEvent(EventArgs.Empty);
            }
        }
    }

There is now a class named BranchNamesCollection within the Branch class. The BranchNamesCollection class is of type Collection<string>. It overrides the RemoveItem() method present in the Collection<T> class. When an item is deleted from the collection, it proceeds to remove the item by calling the base RemoveItem() method and then invoking a function defined in the Branch class: RaiseItemRemovedEvent(). The RaiseItemRemovedEvent() function then raises the ItemRemoved event to notify the client that an item has been removed.

To service the ItemRemoved event in the Branch class, modify the code as follows:

static void Main(string[] args)
        {
            Branch b = new Branch();
            b.ItemRemoved += new EventHandler(b_ItemRemoved);

            b.BranchNames.Add("ABC");
            b.BranchNames.Add("XYZ");
            b.BranchNames.Remove("XYZ");

            foreach (string branchName in b.BranchNames)
            {
                Console.WriteLine(branchName);
            }
            Console.ReadLine();
        }

        static void b_ItemRemoved(object sender, EventArgs e)
        {
            Console.WriteLine("Item removed!");
        }

And here's the code's output:

Item removed!

Generics allow you define type-safe data structures without binding to specific fixed data types at design time. The end result is that your code becomes safer without sacrificing performance. In addition to showing you how to define your own generic class, this chapter also examined some of the generic classes provided in the .NET Framework class library, such as the generic LinkedList<T> and Collection<T> classes.