Creating Generic Classes

First start with a normal, nongeneric simplified linked list class that can contain objects of any kind, and later convert this class to a generic class.

With a linked list one element references the next one. So, you must create a class that wraps the object inside the linked list and references the next object. The class LinkedListNode contains an object named value that is initialized with the constructor, and can be read with the Value property. In addition to that, the LinkedListNode class contains references to the next and previous elements in the list that can be accessed from properties.

public class LinkedListNode
{
   private object value;
   public LinkedListNode(object value)
   {
      this.value = value;
   }

   public object Value
   {
      get { return value; }
   }


   private LinkedListNode next;
   public LinkedListNode Next
   {
      get { return next; }
      internal set { next = value; }
   }

   private LinkedListNode prev;
   public LinkedListNode Prev
   {
      get { return prev; }
      internal set { prev = value; }
   }
}

The LinkedList class includes first and last fields of type LinkedListNode that mark the begin and end of the list. The method AddLast() adds a new element to the end of the list. First, an object of type LinkedListNode is created. If the list is empty, the first and last fields are set to the new element; otherwise, the new element is added as the last element to the list. By implementing the GetEnumerator() method, it is possible to iterate through the list with the foreach statement. The GetEnumerator() method makes use of the yield statement for creating an enumerator type.

public class LinkedList : IEnumerable
{
   private LinkedListNode first;
   public LinkedListNode First
   {
      get { return first; }
   }

   private LinkedListNode last;
   public LinkedListNode Last
   {
      get { return last; }
   }

   public LinkedListNode AddLast(object node)
   {
      LinkedListNode newNode = new LinkedListNode(node);
      if (first == null)
      {
         first = newNode;
         last = first;
      }
      else
      {
         last.Next = newNode;
         last = newNode;
      }
      return newNode;
   }

   public IEnumerator GetEnumerator()
   {
      LinkedListNode current = first;
      while (current != null)
      {
         yield return current.Value;
         current = current.Next; 
      }
   }
}

Now you can use the LinkedList class with any type. With the following code segment a new LinkedList object is instantiated, and two integer types and one string type are added. As the integer types are converted to an object, boxing occurs as was discussed earlier. With the foreach statement unboxing happens. In the foreach statement the elements from the list are cast to an integer, so with the third element in the list a runtime exception occurs as casting to an int fails.

LinkedList list1 = new LinkedList();
list1.AddLast(2);
list1.AddLast(4);
list1.AddLast("6");
foreach (int i in list1)
{
   Console.WriteLine(i);
}

Now let’s make a generic version of the linked list. A generic class is defined similarly to a normal class with the generic type declaration. The generic type can then be used within the class as a field member, or with parameter types of methods. The class LinkedListNode is declared with a generic type T. The field value is now type T instead of object; the constructor and property Value are changed as well to accept and return an object of type T. A generic type can also be returned and set, so the properties Next and Prev are now of type LinkedListNode<T>:

public class LinkedListNode<T>
{
   private T value;
   public LinkedListNode(T value)
   {
      this.value = value;
   }
   
      public T Value
   {
      get { return value; }
   }
   private LinkedListNode<T> next;
   public LinkedListNode<T> Next
   {
      get { return next; }
      internal set { next = value; }
   }
   private LinkedListNode<T> prev;
   public LinkedListNode<T> Prev
   {
      get { return prev; }
      internal set { prev = value; }
   }
}

The class LinkedList is changed to a generic class as well. LinkedList<T> contains LinkedListNode<T> elements. The type T from the LinkedList defines the type T of the containing fields first and last. The method AddLast() now accepts a parameter of type T and instantiates an object of LinkedListNode<T>.

With the interface IEnumerable there’s also a generic version IEnumerable<T> available since the release of .NET 2.0. IEnumerable<T> derives from IEnumerable and adds the GetEnumerator() method that returns IEnumerator<T>. LinkedList<T> implements the generic interface IEnumerable<T>.

public class LinkedList<T> : IEnumerable<T>
{
   private LinkedListNode<T> first;
   public LinkedListNode<T> First
   {
      get { return first; }
   }
   private LinkedListNode<T> last;
   public LinkedListNode<T> Last
   {
      get { return last; }
   }
   public LinkedListNode<T> AddLast(T node)
   {
      LinkedListNode<T> newNode = new LinkedListNode<T>(node);
      if (first == null)
      {
         first = newNode;
         last = first;
      }
      else
      {
         last.Next = newNode;
         last = newNode;
      }
      return newNode;
   }
   public IEnumerator<T> GetEnumerator()
   {
      LinkedListNode<T> current = first;
      while (current != null)
      {
         yield return current.Value;
         current = current.Next;
      }
   }

   IEnumerator IEnumerable.GetEnumerator()
   {
      return GetEnumerator();
   }
}

Using the generic LinkedList<T>, you can instantiate it with an int type, and there’s no boxing. Also, you get a compiler error if you don’t pass an int with the method AddLast(). Using the generic IEnumerable<T>, the foreach statement is also type-safe, and you get a compiler error if that variable in the foreach statement is not an int.

LinkedList<int> list2 = new LinkedList<int>();
list2.AddLast(1);
list2.AddLast(3);
list2.AddLast(5);

foreach (int i in list2)
{
   Console.WriteLine(i);
}

Similarly, you can use the generic LinkedList<T> with a string type and pass strings to the AddLast() method:

LinkedList<string> list3 = new LinkedList<string>();
list3.AddLast("2");
list3.AddLast("four");
list3.AddLast("foo");

foreach (string s in list3)
{
   Console.WriteLine(s);
}