Glossary of terms
generics: generics
type-safe: Type-safe
collection:
compiler: compiler
run time: program run time
object: object
.NET library: .Net class library
value type: value type
box: Packing
unbox: unboxing
implicity: implicit
explicitity: explicit
linked list: linear link list
node: node
indexer: indexer
What is a generic?
Many people find generics difficult to understand. I believe this is because they are usually instilled with a lot of theories and paradigms before they understand what problems generics are used to solve. The result is that you have a solution, but there is no problem with using this solution.
This article will try to change this learning process, and we will start with a simple question: What are generics used for? The answer is: Without generics, it will be difficult to create type-safe collections.
C# is a type-safe language that allows the compiler to (trustably) catch potential errors rather than discovering (untrustably!) when the program is running (not trustworthy!). Therefore, in C#, all variables have a defined type; when you assign an object to that variable, the compiler checks whether the assignment is correct, and if there is any problem, an error message will be given.
In .Net 1.1 (2003), this type safety fails when you are using collections. All the classes about collections provided by the .Net class library are used to store base types (Objects), and everything in .Net is inherited by the Object base class, so all types can be placed in a collection. Therefore, it is equivalent to no type detection at all.
Worse, every time you take an Object from the collection, you have to cast it to the correct type, which will have a performance impact and produce verbose code (if you forget to convert, an exception will be thrown). Further, if you add a value type to the set (for example, an integer variable), the integer variable is implicitly boxed (againstically reduced performance), and when you take it out of the set, it will be explicitly unboxed (against performance reduction and type conversion).
For more information about packing and unboxing, please visit Trap 4. Beware of implicit packing and unboxing.
Create a simple linear link list
To experience these issues vividly, we will create a linear list as simple as possible. For those who read this article who have never created a linear list. You can think of a linear list as a box tied together (called a node), each box contains some data and a reference to the next box on this chain (except for the last box, of course, the reference to the next box is set to NULL).
In order to create our simple linear linked list, we need the following three classes:
1. Node class, containing data and reference to the next Node.
2. The LinkedList class contains the first Node in the linked list and any additional information about the linked list.
3. Test program, used to test the LinkedList class.
To see how the link table works, we add two types of Objects to the linked list: integer and Employee type. You can think of the Employee type as a class that contains all the information about an employee in the company. For demonstration purposes, the Employee class is very simple.
public class Employee{
private string name;
public Employee (string name){
= name;
}
public override string ToString(){
return ;
}
}
This class only contains a string type that represents the employee's name, a constructor that sets the employee's name, and a ToString() method that returns the Employee's name.
The link table itself is composed of many Nodes. These Notes, as mentioned above, must contain data (integral and Employee) and references to the next Node in the linked list.
public class Node{
Object data;
Node next;
public Node(Object data){
= data;
= null;
}
public Object Data{
get { return ; }
set { data = value; }
}
public Node Next{
get { return ; }
set { = value; }
}
}
Note that the constructor sets the private data members to the passed in object and sets the next field to null.
This class also includes a method, Append, which accepts a Node type parameter, and we will add the passed Node to the last position in the list. This process is as follows: First, detect the next field of the current Node to see if it is null. If so, then the current Node is the last Node. We point the next property of the current Node to the new node passed in, so that we put the new Node to the end of the linked list.
If the next field of the current Node is not null, it means that the current node is not the last node in the linked list. Because the type of next field is also node, we call the Append method of next field (Note: recursive call), and pass the Node parameter again, so that we continue until the last Node is found.
public void Append(Node newNode){
if ( == null ){
= newNode;
}else{
(newNode);
}
}
The ToString() method in the Node class is also overwritten, used to output the value in data, and to call the ToString() method of the next Node (translation note: another recursive call).
public override string ToString(){
string output = ();
if ( next != null ){
output += ", " + ();
}
return output;
}
This way, when you call the ToString() method of the first Node, the values of Node on all linked lists will be printed out.
The LinkedList class itself only contains a reference to a Node. This Node is called HeadNode, which is the first Node in the linked list, initialized to null.
public class LinkedList{
Node headNode = null;
}
The LinkedList class does not require a constructor (the default constructor created by the compiler), but we need to create a public method, Add(), which stores data into a linear linked list. This method first checks whether the headNode is null. If so, it will use data to create a node and use this node as a headNode. If it is not null, it will create a new node containing data and call the Append method of the headNode, as shown in the following code:
public void Add(Object data){
if ( headNode == null ){
headNode = new Node(data);
}else{
(new Node(data));
}
}
To provide a little collection feel, we create an indexer for the linear linked list.
public object this[ int index ]{
get{
int ctr = 0;
Node node = headNode;
while ( node != null && ctr <= index ){
if ( ctr == index ){
return ;
}else{
node = ;
}
ctr++;
}
return null;
}
}
Finally, the ToString() method is overwritten again to call the ToString() method of the headNode.
public override string ToString(){
if ( != null ){
return ();
}else{
return ;
}
}
Test linear link table
We can add some integer values to the linked list for testing:
public void Run(){
LinkedList ll = new LinkedList();
for ( int i = 0; i < 10; i ++ ){
(i);
}
(ll);
(" Done. Adding employees...");
}
If you test this code, it will work as expected:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Done. Adding employees...
However, because this is a collection of Object types, you can also add the Employee type to the collection.
(new Employee("John"));
(new Employee("Paul"));
(new Employee("George"));
(new Employee("Ringo"));
(ll);
(" Done.");
The output results confirm that both the integer value and the Employee type are stored in the same set.
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.
Although it seems to be convenient, the negative effect is that you lose all type-safe features. Because the linear linked list requires an Object type, each integer value added to the collection is implicitly boxed, as shown in the IL code:
IL_000c: box [mscorlib]System.Int32
IL_0011: callvirt instance void ::Add(object)
Similarly, if you say above, when you take items from your list, these integers must be explicitly unboxed (cast into integers), and the Employee type must be cast into Employee type.
("The fourth integer is " + Convert.ToInt32(ll[3]));
Employee d = (Employee) ll[11];
("The second Employee is " + d);
The solution to these problems is to create a type-safe collection. An Employee linear linked list will not accept the Object type; it only accepts instances of the Employee class (or instances inherited from the Employee class). This will be type-safe and no longer requires type conversion. An integer linear linked list will no longer require boxing and unboxing operations (because it can only accept integer values).
As an example, you will create an EmployeeNode that knows that its data is of type Employee.
public class EmployeeNode {
Employee employeedata;
EmployeeNode employeeNext;
}
The Append method now accepts an argument of type EmployeeNode. You also need to create a new EmployeeLinkedList, which accepts a new EmployeeNode:
public class EmployeeLinkedList{
EmployeeNode headNode = null;
}
The () method no longer accepts an Object, but rather an Employee:
public void Add(Employee data){
if ( headNode == null ){
headNode = new EmployeeNode(data);}
else{
(new EmployeeNode(data));
}
}
Similarly, the indexer must be modified to accept EmployeeNode type, etc. This does solve the problems of packing and unboxing, and adds type safety features. You can now add Employee (but not an integer) to your new linear list, and when you take out Employee from it, you no longer need to convert the type.
EmployeeLinkedList employees = new EmployeeLinkedList();
(new Employee("Stephen King"));
(new Employee("James Joyce"));
(new Employee("William Faulkner"));
/* (5); // try to add an integer - won't compile */
(employees);
Employee e = employees[1];
("The second Employee is " + e);
How great this is, when an integer is trying to implicitly convert to the Employee type, the code cannot even pass the compiler!
But the bad thing about it is: every time you need to create a type-safe list, you need to do a lot of copy/paste. Not good enough at all, no code reuse at all. At the same time, if you are the author of this class, you cannot even know in advance what the type should be accepted by this link list, so you have to hand over the work of adding type security mechanism to the user of the class - your user.
Use generics to achieve code reuse
The solution, as you guessed, is to use generics. Through generics, you regain the code of the link list (only implement it once for all types), and when you initialize the linked list you tell the linked list what types you can accept. This implementation is very simple, let's go back to the Node class:
public class Node{
Object data;
...
Note that the type of data is Object, (in EmployeeNode, it is Employee). We will turn it into a generic (usually represented by a capital T). We also define the Node class, indicating that it can be generic to accept a T type.
public class Node <T>{
T data;
...
Read: Node of type T. T represents the type accepted by Node when Node is initialized. T can be an Object, an integer or an Employee. This can only be determined when the Node is initialized.
Note: Using T as a logo is just a convention, you can use other letter combinations instead, such as this:
public class Node <UnknownType>{
UnknownType data;
...
By using T as an unknown type, the next field (reference to the next node) must be declared as a T-type Node (meaning to accept a T-type generic Node).
Node<T> next;
The constructor accepts a simple parameter of type T:
public Node(T data)
{
= data;
= null;
}
The rest of the Node class is simple, and all the places you need to use Object, you now need to use T. The LinkedList class now accepts a T-type Node instead of a simple Node as the header node.
public class LinkedList<T>{
Node<T> headNode = null;
If you do it again, the conversion is very straightforward. Anywhere you need to use Object, now change to T, anywhere you need to use Node, now change to Node<T>. The following code initializes two link tables. One is an integer.
LinkedList<int> ll = new LinkedList<int>();
Another one is Employee type:
LinkedList<Employee> employees = new LinkedList<Employee>();
The remaining code is no different from the first version, except that it is not boxed or unboxed, and it is also impossible to save the wrong type into the collection.
LinkedList<int> ll = new LinkedList<int>();
for ( int i = 0; i < 10; i ++ )
{
(i);
}
(ll);
(" Done.");
LinkedList<Employee> employees = new LinkedList<Employee>();
(new Employee("John"));
(new Employee("Paul"));
(new Employee("George"));
(new Employee("Ringo"));
(employees);
(" Done.");
("The fourth integer is " + ll[3]);
Employee d = employees[1];
("The second Employee is " + d);
Generics allow you to implement type-safe collections without copying/pasting lengthy code. Moreover, because generics are extended to special types only at runtime. The Just In Time compiler can share code between different instances, and in the end, it significantly reduces the code you need to write.