Generics Node declaration

Question

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?

1   public class GenericList<T> : System.Collections.Generic.IEnumerable<T>
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<T> 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<T> : GenericList<T> where T : System.IComparable<T>
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<T>
93                      if (current.Data.CompareTo(current.next.Data) > 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     }

Answer 1

You're assigning previous and next to null and head respectively. It's an assignment operation, just like any other. You don't need to use new unless you're actually creating a new instance of the object.

The generic parts are anything that refers to T. It's a generic type that is supplied when the class is instanciated. A good example is List<T>, which creates a list of objects of type T. You could instance this as List<string> for a list of strings, List<int> for a list of ints, etc.

Answer 2

A class type in C# can be initialized with null or a value which is of a compatible type with the declaration. Lines 76 and 77 look like so

Node previous = null;
Node current = head;

Here the value null is legal. It essentially says "I have no value". The assignment to head is also legal because head is also of type Node. The result is the two references head and current refer to the same Node object value. Modifying the Node instance through one of the references will be visible to the other.

Answer 3

These are references that could be pointing to instances of a class or can be just null.

You can assign references to other references:

Foo f1 = new Foo();
Foo f2 = f1;
Foo f3 = null;

Answer 4

No objects are being instantiated on lines 76 and 77 in that code. As you said, Node is a class. Classes in .NET are always reference types which means that:

1. The value of a variable of a reference type is a reference to an object (or nothing).
2. Variables of a reference type can be assigned the value null, which means that the variable references nothing.
3. Assigning one variable of a reference type to another variable of a reference type copies the reference, not the object.