c#泛型学习详解 创建线性链表

术语表

generics：泛型
type-safe：类型安全
collection: 集合
compiler：编译器
run time：程序运行时
object: 对象
.net library：.net类库
value type: 值类型
box: 装箱
unbox: 拆箱
implicity: 隐式
explicity: 显式
linked list: 线性链表
node: 结点
indexer: 索引器

泛型是什么？

很多人觉得泛型很难理解。我相信这是因为他们通常在了解泛型是用来解决什么问题之前，就被灌输了大量的理论和范例。结果就是你有了一个解决方案，但是却没有需要使用这个解决方案的问题。

这篇文章将尝试着改变这种学习流程，我们将以一个简单的问题作为开始：泛型是用来做什么的？答案是：没有泛型，将会很难创建类型安全的集合。

c# 是一个类型安全的语言，类型安全允许编译器(可信赖地)捕获潜在的错误，而不是在程序运行时才发现(不可信赖地，往往发生在你将产品出售了以后！)。因 此，在c#中，所有的变量都有一个定义了的类型；当你将一个对象赋值给那个变量的时候，编译器检查这个赋值是否正确，如果有问题，将会给出错误信息。

在 .net 1.1 版本(2003)中，当你在使用集合时，这种类型安全就失效了。由.net 类库提供的所有关于集合的类全是用来存储基类型(object)的，而.net中所有的一切都是由object基类继承下来的，因此所有类型都可以放到一 个集合中。于是，相当于根本就没有了类型检测。

更糟的是，每一次你从集合中取出一个object，你都必须将它强制转换成正确的类型，这一转换将对性能造成影响，并且产生冗长的代码(如果你忘了 进行转换，将会抛出异常)。更进一步地讲，如果你给集合中添加一个值类型(比如，一个整型变量)，这个整型变量就被隐式地装箱了(再一次降低了性能)，而 当你从集合中取出它的时候，又会进行一次显式地拆箱(又一次性能的降低和类型转换)。

关于装箱、拆箱的更多内容，请访问 陷阱4，警惕隐式的装箱、拆箱。

创建一个简单的线性链表

为了生动地感受一下这些问题，我们将创建一个尽可能简单的线性链表。对于阅读本文的那些从未创建过线性链表的人。你可以将线性链表想像成有一条链子 栓在一起的盒子(称作一个结点)，每个盒子里包含着一些数据 和 链接到这个链子上的下一个盒子的引用(当然，除了最后一个盒子，这个盒子对于下一个盒子的引用被设置成null)。

为了创建我们的简单线性链表，我们需要下面三个类：

1、node 类，包含数据以及下一个node的引用。

2、linkedlist 类，包含链表中的第一个node，以及关于链表的任何附加信息。

3、测试程序，用于测试 linkedlist 类。

为了查看链接表如何运作，我们添加objects的两种类型到链表中：整型 和 employee类型。你可以将employee类型想象成一个包含关于公司中某一个员工所有信息的类。出于演示的目的，employee类非常的简单。

public class employee{
　　private string name;
　　public employee (string name){
　　　　this.name = name;
　　}

　　public override string tostring(){
　　　return this.name;
　　}
}

这个类仅包含一个表示员工名字的字符串类型，一个设置员工名字的构造函数，一个返回employee名字的tostring()方法。

链接表本身是由很多的node构成，这些note，如上面所说，必须包含数据(整型 和 employee)和链表中下一个node的引用。

public class node{
    object data;
    node next;

    public node(object data){
       this.data = data;
       this.next = null;
    }

    public object data{
       get { return this.data; }
       set { data = value; }
    }

    public node next{
        get { return this.next; }
       set { this.next = value; }
    }
}

注意构造函数将私有的数据成员设置成传递进来的对象，并且将 next 字段设置成null。

这个类还包括一个方法，append，这个方法接受一个node类型的参数，我们将把传递进来的node添加到列表中的最后位置。这过程是这样的： 首先检测当前node的next字段，看它是不是null。如果是，那么当前node就是最后一个node，我们将当前node的next属性指向传递进 来的新结点，这样，我们就把新node插入到了链表的尾部。

如果当前node的next字段不是null，说明当前node不是链表中的最后一个node。因为next字段的类型也是node，所以我们调用next字段的append方法(注：递归调用)，再一次传递node参数，这样继续下去，直到找到最后一个node为止。

public void append(node newnode){
    if ( this.next == null ){
       this.next = newnode;
    }else{
       next.append(newnode);
    }
}

node 类中的 tostring() 方法也被覆盖了，用于输出 data 中的值，并且调用下一个 node 的 tostring()方法(译注：再一次递归调用)。

public override string tostring(){
    string output = data.tostring();

    if ( next != null ){
       output += ", " + next.tostring();
    }

    return output;
}

这样，当你调用第一个node的tostring()方法时，将打印出所有链表上node的值。

linkedlist 类本身只包含对一个node的引用，这个node称作 headnode，是链表中的第一个node，初始化为null。

public class linkedlist{
    node headnode = null;
}

linkedlist 类不需要构造函数(使用编译器创建的默认构造函数)，但是我们需要创建一个公共方法，add()，这个方法把 data存储到线性链表中。这个方法首先检查headnode是不是null，如果是，它将使用data创建结点，并将这个结点作为headnode，如 果不是null，它将创建一个新的包含data的结点，并调用headnode的append方法，如下面的代码所示：

public void add(object data){
    if ( headnode == null ){
       headnode = new node(data);
    }else{
       headnode.append(new node(data));
    }
}

为了提供一点集合的感觉，我们为线性链表创建一个索引器。

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++;
        }
    return null;
    }
}

最后，tostring()方法再一次被覆盖，用以调用headnode的tostring()方法。

public override string tostring(){
    if ( this.headnode != null ){
       return this.headnode.tostring();
    }else{
       return string.empty;
    }
}

测试线性链表

我们可以添加一些整型值到链表中进行测试：

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...");
}

如果你对这段代码进行测试，它会如预计的那样工作：

0, 1, 2, 3, 4, 5, 6, 7, 8, 9
done. adding employees...

然而，因为这是一个object类型的集合，所以你同样可以将employee类型添加到集合中。

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.");

输出的结果证实了，整型值和employee类型都被存储在了同一个集合中。

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.

虽然看上去这样很方便，但是负面影响是，你失去了所有类型安全的特性。因为线性链表需要的是一个object类型，每一个添加到集合中的整型值都被隐式装箱了，如同 il 代码所示：

il_000c:  box        [mscorlib]system.int32
il_0011:  callvirt   instance void objectlinkedlist.linkedlist::add(object)

同样，如果上面所说，当你从你的列表中取出项目的时候，这些整型必须被显式地拆箱(强制转换成整型)，employee类型必须被强制转换成 employee类型。

console.writeline("the fourth integer is " + convert.toint32(ll[3]));
employee d = (employee) ll[11];
console.writeline("the second employee is " + d);

这些问题的解决方案是创建一个类型安全的集合。一个 employee 线性链表将不能接受 object 类型；它只接受 employee类的实例(或者继承自employee类的实例)。这样将会是类型安全的，并且不再需要类型转换。一个 整型的 线性链表，这个链表将不再需要装箱和拆箱的操作(因为它只能接受整型值)。

作为示例，你将创建一个 employeenode，该结点知道它的data的类型是employee。

public class employeenode {
    employee employeedata;
    employeenode employeenext;
}

append 方法现在接受一个 employeenode 类型的参数。你同样需要创建一个新的 employeelinkedlist ，这个链表接受一个新的 employeenode：

public class employeelinkedlist{
    employeenode headnode = null;
}

employeelinkedlist.add()方法不再接受一个 object，而是接受一个employee：

public void add(employee data){
    if ( headnode == null ){
       headnode = new employeenode(data);}
    else{
       headnode.append(new employeenode(data));
    }
}

类似的，索引器必须被修改成接受 employeenode 类型，等等。这样确实解决了装箱、拆箱的问题，并且加入了类型安全的特性。你现在可以添加employee(但不是整型)到你新的线性链表中了，并且当你从中取出employee的时候，不再需要类型转换了。

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);

这样多好啊，当有一个整型试图隐式地转换到employee类型时，代码甚至连编译器都不能通过！

但它不好的地方是：每次你需要创建一个类型安全的列表时，你都需要做很多的复制/粘贴 。一点也不够好，一点也没有代码重用。同时，如果你是这个类的作者，你甚至不能提前欲知这个链接列表所应该接受的类型是什么，所以，你不得不将添加类型安 全这一机制的工作交给类的使用者---你的用户。

使用泛型来达到代码重用

解决方案，如同你所猜想的那样，就是使用泛型。通过泛型，你重新获得了链接列表的　　　代码通用(对于所有类型只用实现一次)，而当你初始化链表的时候你告诉链表所能接受的类型。这个实现是非常简单的，让我们重新回到node类：

public class node{
    object data;
    ...

注意到 data 的类型是object，(在employeenode中，它是employee)。我们将把它变成一个泛型(通常，由一个大写的t代表)。我们同样定义node类，表示它可以被泛型化，以接受一个t类型。

public class node <t>{
    t data;
    ...

读作：t类型的node。t代表了当node被初始化时，node所接受的类型。t可以是object，也可能是整型或者是employee。这个在node被初始化的时候才能确定。

注意：使用t作为标识只是一种约定俗成，你可以使用其他的字母组合来代替，比如这样：

public class node <unknowntype>{
    unknowntype data;
    ...

通过使用t作为未知类型，next字段(下一个结点的引用)必须被声明为t类型的node(意思是说接受一个t类型的泛型化node)。

node<t> next;

构造函数接受一个t类型的简单参数：

public node(t data)
{
    this.data = data;
    this.next = null;
}

node 类的其余部分是很简单的，所有你需要使用object的地方，你现在都需要使用t。linkedlist 类现在接受一个 t类型的node，而不是一个简单的node作为头结点。

public class linkedlist<t>{
node<t> headnode = null;

再来一遍，转换是很直白的。任何地方你需要使用object的，现在改做t，任何需要使用node的地方，现在改做 node<t>。下面的代码初始化了两个链接表。一个是整型的。

linkedlist<int> ll = new linkedlist<int>();

另一个是employee类型的：

linkedlist<employee> employees = new linkedlist<employee>();

剩下的代码与第一个版本没有区别，除了没有装箱、拆箱，而且也不可能将错误的类型保存到集合中。

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);

泛型允许你不用复制/粘贴冗长的代码就实现类型安全的集合。而且，因为泛型是在运行时才被扩展成特殊类型。just in time编译器可以在不同的实例之间共享代码，最后，它显著地减少了你需要编写的代码。