title: Generics Node declaration
body: <p>Microsoft gives this as an Bubble sort example for learning generics.  It makes sense until I get to lines 76 and 77.  How are those declarations possible?  Node is a class.  Don't you have to instantiate it with new?
  How would you optimize the sort?  Which is part is generic and which is non-generic?</p>
  
  <pre><code>1   public class GenericList&lt;T&gt; : System.Collections.Generic.IEnumerable&lt;T&gt;
  2       {
  3           protected Node head;
  4           protected Node current = null;
  5   
  6           // Nested class is also generic on T
  7           protected class Node
  8           {
  9               public Node next;
  10              private T data;  //T as private member datatype
  11   
  12              public Node(T t)  //T used in non-generic constructor
  13              {
  14                  next = null;
  15                  data = t;
  16              }
  17  
  18              public Node Next
  19              {
  20                  get { return next; }
  21                  set { next = value; }
  22              }
  23  
  24              public T Data  //T as return type of property
  25              {
  26                  get { return data; }
  27                  set { data = value; }
  28              }
  29          }
  30  
  31          public GenericList()  //constructor
  32          {
  33              head = null;
  34          }
  35  
  36          public void AddHead(T t)  //T as method parameter type
  37          {
  38              Node n = new Node(t);
  39              n.Next = head;
  40              head = n;
  41          }
  42  
  43          // Implementation of the iterator
  44          public System.Collections.Generic.IEnumerator&lt;T&gt; GetEnumerator()
  45          {
  46              Node current = head;
  47              while (current != null)
  48              {
  49                  yield return current.Data;
  50                  current = current.Next;
  51                  
  52              }
  53          }
  54  
  55          System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
  56          {
  57              return GetEnumerator();
  58          }
  59      }
  60  
  61      public class SortedList&lt;T&gt; : GenericList&lt;T&gt; where T : System.IComparable&lt;T&gt;
  62      {
  63          // A simple, unoptimized sort algorithm that 
  64          // orders list elements from lowest to highest:
  65  
  66          public void BubbleSort()
  67          {
  68              if (null == head || null == head.Next)
  69              {
  70                  return;
  71              }
  72              bool swapped;
  73  
  74              do
  75              {
  76                  Node previous = null;
  77                  Node current = head;
  78  
  79                  
  80                  //Console.WriteLine(previous.GetType());
  81                  //Console.ReadLine();
  82  
  83                  swapped = false;
  84                  
  85                   
  86                  //Debug.WriteLine(p);
  87                  //Debug.WriteLine("Testing " + current.ToString());
  88  
  89                  while (current.next != null)
  90                  {
  91                      //  Because we need to call this method, the SortedList
  92                      //  class is constrained on IEnumerable&lt;T&gt;
  93                      if (current.Data.CompareTo(current.next.Data) &gt; 0)
  94                      {
  95                          Node tmp = current.next;
  96                          current.next = current.next.next;
  97                          tmp.next = current;
  98  
  99                          if (previous == null)
  100                         {
  101                             head = tmp;
  102                         }
  103                         else
  104                         {
  105                             previous.next = tmp;
  106                         }
  107                         previous = tmp;
  108                         swapped = true;
  109                     }
  110                     else
  111                     {
  112                         previous = current;
  113                         current = current.next;
  114                     }
  115                 }
  116             } while (swapped);
  117         }
  118     }
  </code></pre>