WindowsDevCenter.com
oreilly.comSafari Books Online.Conferences.

advertisement


AddThis Social Bookmark Button

C# Generics
Pages: 1, 2

The LinkedList class needs no constructor (relying on the default constructor provided by the compiler), but we will provide a public method, Add, that will take data to store in the linked list. This method will check to see if the headNode is null; if so, it will create the headNode with that data. If not, it will create a new Node and pass that Node, with the data, to the headNode's Append method, which works as described above.

public void Add(Object data)
{
  if ( headNode == null )
  {
    headNode = new Node(data);
  }
  else
  {
    headNode.Append(new Node(data));
  }
}

To provide a bit of collection semantics, we'll create an indexer for the linked list:


public object this[ int index ]
{
  get
  {
    int ctr = 0;
    Node node = headNode;
    while ( node != null  && ctr <= index )
    {
      if ( ctr == index )
      {
        return node.Data;
      }
      else
      {
        node = node.Next;
      }
      ++ctr;
    } // end while
    return null;
  }    // end get
}      // end indexer
Finally, ToString is overridden to invoke the headNode's ToString method.

public override string ToString()
{
  if ( this.headNode != null )
  {
    return this.headNode.ToString();
  }
  else
  {
    return string.Empty;
  }
}
We can test our linked list by adding integers to the list:

public void Run()
{
  LinkedList ll = new LinkedList();
  for ( int i = 0; i < 10; i ++ )
  {
    ll.Add(i);
  }
  Console.WriteLine(ll);
  Console.WriteLine("  Done. Adding employees...");
If you test just this portion of the code, it works as expected.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9
  Done. Adding employees...
However, since this is a collection of objects, you are equally free to add Employee objects to the collection:

ll.Add(new Employee("John"));
ll.Add(new Employee("Paul"));
ll.Add(new Employee("George"));
ll.Add(new Employee("Ringo"));

Console.WriteLine(ll);
Console.WriteLine("  Done.");

The output shows that both the integers and the Employees are stored in the same collection:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9
  Done. Adding employees...
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, John, Paul, George, Ringo
  Done.
While this seems quite convenient, the downside is that you've lost all type safety. Furthermore, since the linked list expects objects, each integer that is added is silently boxed, as shown in the IL code:

IL_000c:  box        [mscorlib]System.Int32
IL_0011:  callvirt   instance void ObjectLinkedList.LinkedList::Add(object)
Also, as noted above, when you want to retrieve the items from your list, the integers must be explicitly unboxed (cast to integers) and the Employees must be cast to Employee objects.

Console.WriteLine("The fourth integer is " + Convert.ToInt32(ll[3]));
Employee d = (Employee) ll[11];
Console.WriteLine("The second Employee is " + d);

The solution to all of these problems is to create type-specific collections. An Employee LinkedList would not take Objects; it would take Employee instances (or instances of types derived from Employee). This would add type safety, and remove the need for casting. An integer LinkedList would have the advantage of not requiring boxing and unboxing (since the collection would not expect Objects).

As an example, you could create an EmployeeNode that would know that its data is of type Employee:


public class EmployeeNode 
{
  Employee employeedata;
  EmployeeNode employeeNext;

Append now takes an EmployeeNode. You also need to create a new EmployeeLinkedList that takes the new EmployeeNode:


public class EmployeeLinkedList
{
  EmployeeNode headNode = null;

The EmployeeLinkedList.Add method does not take an object, but rather takes an Employee:

public void Add(Employee data)
{
  if ( headNode == null )
  {
    headNode = new EmployeeNode(data);
  }
  else
  {
    headNode.Append(new EmployeeNode(data));
  }
}

Similarly, the indexer must be modified to take EmployeeNodes, etc. This does solve the problems of casting and boxing, and adds type safety. You can now add Employees (but not integers!) to this new linked list, and when you take Employees out, no cast is required:


EmployeeLinkedList employees = new EmployeeLinkedList();
employees.Add(new Employee("Stephen King"));
employees.Add(new Employee("James Joyce"));
employees.Add(new Employee("William Faulkner"));
/* employees.Add(5);  // try to add an integer - won't compile */
Console.WriteLine(employees);
Employee e = employees[1];
Console.WriteLine("The second Employee is " + e);

What is particularly nice is that unless there is an implicit conversion from integer to Employee, the code that tries to add an integer will not even compile!

What is not so nice is that each time you want to create a type-specific list, you have a lot of cutting and pasting to do. Not good, not reusable. Also, if you are the creator of the class, you can not anticipate in advance what types might be stored in the linked list, and so you force your user to do the work of adding type safety. Yuck.

Generics To The Rescue

The solution, as you have probably guessed by now, is to use Generics. With Generics, you retain the generic quality of the linked list (one implementation for all types), but you add type safety by defining the type of objects you'll add to the list when you instantiate it. The implemenation is frighteningly simple. Return to your original Node class:


public class Node
{
  Object data;

Notice the type of the data it holds is Object (in the EmployeeNode, it was Employee). We'll change this to a generic type (typically indicated by a single letter, in this case T). We'll also define the Node class to indicate that it is being used generically to take a type T:


public class Node <T>
{
    T data;

You read this as "class Node of T." The T stands for the type to be declared when the Node is instantiated. T might turn out to be type Object, or it might be integer or Employee. That will be decided when the Node is instantiated.

Note: the use of T is arbitrary; it is a mnemonic to remind you that it stands for a generic type. You could just as easily have defined this


public class Node <UnknownType>
{
    UnknownType data;

Having used T for the unknown type, the next member (the reference to the next Node) must refer to a Node of T (that is, a generic Node that takes a type T):

Node<T> next;
The constructor takes a single argument, of type T:

public Node(T data)
{
    this.data = data;
    this.next = null;
}

The rest of the Node class is similar; everywhere you had Object, you now put T (see the complete code listing). The LinkedList now takes a Node of T rather than a simple Node as its headNode:


 public class LinkedList<T>
 {
     Node<T> headNode = null;

Once again, the transformation is pretty straightforward. Anywhere you would have had Object, you have T, and anywhere you would have had Node, you now have Node<T>. The test code instantiates two linked lists. One is a linked list of integers:


LinkedList<int> ll = new LinkedList<int>();
And the second is a linked list of Employee objects:

LinkedList<Employee> employees = new LinkedList<Employee>();
The rest of the code is unchanged from the first version, except that there no longer is any boxing of the integer, there is no need to cast the Employees, and it is not possible to put the wrong type into the collection!

LinkedList<int> ll = new LinkedList<int>();
for ( int i = 0; i < 10; i ++ )
{
    ll.Add(i);
}


Console.WriteLine(ll);
Console.WriteLine("  Done.");

LinkedList<Employee> employees = new LinkedList<Employee>();
employees.Add(new Employee("John"));
employees.Add(new Employee("Paul"));
employees.Add(new Employee("George"));
employees.Add(new Employee("Ringo"));

Console.WriteLine(employees);            
Console.WriteLine("  Done.");
Console.WriteLine("The fourth integer is " + ll[3]);
Employee d = employees[1];
Console.WriteLine("The second Employee is " + d);

Generics thus allow you to create type-safe collections without having to duplicate code. Even better, because the generic types are expanded to their specific types at run time, the Just In Time compiler is able to share code among different instances, dramatically reducing the code bloat that you see, for example, in C++.

As a final tip to using Generics, my general approach is to write my generic class first using a specific type (e.g., Employee) and get it working. Once it is fully debugged, I then genericize it, converting the type from the specific Object or Employee to the generic T.

Jesse Liberty is a senior program manager for Microsoft Silverlight where he is responsible for the creation of tutorials, videos and other content to facilitate the learning and use of Silverlight. Jesse is well known in the industry in part because of his many bestselling books, including O'Reilly Media's Programming .NET 3.5, Programming C# 3.0, Learning ASP.NET with AJAX and the soon to be published Programming Silverlight.


Return to ONDotnet.com