本系列文章翻译O'Reilly 出版的《C# Cookbook》一书中的片段,仅供学习交流使用

4.6 链表的实现

问题

您需要链表数据结构，这样就可以很容易地添加和删除元素。

解决方案

使用泛型LinkedList< T>类。下面的方法创建了一个LinkedList< T>类，并往链表对象中添加节点，然后使用了几种方法从链表节点中获得信息。

 public static void UseLinkedList()
    {
        // 创建一个LinkedList 对象.
        LinkedList< TodoItem> todoList = new LinkedList< TodoItem>();
        // 创建添加到链表内的TodoItem对象.
        TodoItem i1 = new TodoItem("paint door", "Should be done third");
        TodoItem i2 = new TodoItem("buy door", "Should be done first");
        TodoItem i3 = new TodoItem("assemble door", "Should be done second");
        TodoItem i4 = new TodoItem("hang door", "Should be done last");
        // 添加项目.
        todoList.AddFirst(i1);
        todoList.AddFirst(i2);
        todoList.AddBefore(todoList.Find(i1), i3);
        todoList.AddAfter(todoList.Find(i1), i4);
        // 显示所有项目.
        foreach (TodoItem tdi in todoList)
        {
            Console.WriteLine(tdi.Name + " : " + tdi.Comment);
        }
        // 显示链表内的第二个节点的信息
        Console.WriteLine("todoList.First.Next.Value.Name == " +
                            todoList.First.Next.Value.Name);
        // 显示链表内最后一个节点的前一节点信息.
        Console.WriteLine("todoList.Last.Previous.Value.Name == " +
                            todoList.Last.Previous.Value.Name);
}

这个方法的输出结果如下：

    buy door : Should be done first

    assemble door : Should be done second

    paint door : Should be done third

    hang door : Should be done last

    todoList.First.Value.Name == buy door

    todoList.First.Next.Value.Name == assemble door

    todoList.Last.Previous.Value.Name == paint door

下面是TodoItem类，它只简单地包含了两个字符串_name和_comment。

public class TodoItem
{
    public TodoItem(string name, string comment)
    {
        _name = name;
        _comment = comment;
    }
    private string _name = "";
    private string _comment = "";
    public string Name
    {
        get { return (_name); }
        set { _name = value; }
    }
    public string Comment
    {
        get { return (_comment); }
        set { _comment = value; }
    }
}

讨论

LinkedList< T>类在.NET framework中是一个双向链表。这是因为链表中的每一个节点都包含了前一节点和后一节点的指针。图4-1演示了这种结构，图中的每个node代表了一个单独的LinkedListNode< T>对象。

注意图中链表的每个节点（方块）包含了一个指向下一节点的指针（指向右边的箭头）和一个指向前一节点的指针（指向左边的箭头）。相反，单链表只包含指向下一节点的指针，它没有指向前一节点的指针。

在LinkedList类中，前一节点通过访问Previous属性获得，后一节点通过访问Next属性获得。链表中的第一个节点的Previous属性总是返回null值。两样，最后一个节点的Next属性也是返回null值。

链表中的每个节点（图4-1中用方块表示）实际上都是一个LinkedListNode< T>对象。所以LinkedList< T>对象实际上是由一组LinkedListNode< T>对象组成，所有这些LinkedListNode< T>对象都包含了访问下一个和前一个LinkedListNode< T>对象的属性。LinkedListNode< T>中所包含的对象可以通过Value属性访问。除了这些属性外，LinkedListNode< T>对象还有一个属性叫List，可以用它来访问所属的LinkedList< T>对象。

性能是我们非常关心的一个问题，List< T>类的性能优越于LinkedList< T>类。一般情况下在List< T>内添加和删除节点要比在LinkedList< T>内进行同样的操作快。对比List< T>.Add方法和LinkedList< T>类的Add*方法（译者注：之所以是Add*方法是因为LinkedList< T>中的添加方法有：AddAfter、AddBefore、AddFirst、AddLast），导到性能上的差异并非因为添加操作本身，而是LinkedList< T>在垃圾回收时的压力。List< T>的数据本质上是存放在托管堆中的一个大容量数组之上，然而LinkedList< T>有可能会把它的节点存放在托管堆的每个角落。这使得强制垃圾回收在处理托管堆中的LinkedList< T>节点对象时需要花费更多的力气。需要注意，List< T>.Insert方法可能会比LinkedList< T>中的任一个Add*方法要慢，但这取决于对象在List< T>的哪个位置插入。当在某个点插入一人新元素时，Insert方法必须移动它后面的所有元素一个位置。如果新元素插入到List< T>的尾部，移动元素所花费的开销比起垃圾回收所花费的开销就可以忽略不计了。

List< T>另外一个胜于LinkedList< T>的地方是可以使用索引访问。在List< T>中，您可以使用索引器并通过索引值来访问指定位置的某个元素。但在LinkedList< T>中就没有这么令人愉快了。在LinkedList< T>类中，您必须使用每个LinkedListNode< T>中的Previous和Next属性进行导航，并贯穿整个链表直到找到您所指定的位置。

在搜索一个元素或节点时，List< T>类也比LinkedList< T>类有速度上的优势。使用List< T>.BinarySearch方法在List< T>内查找元素比在LinkedList< T>类中使用相应的Contains、Find、FindLast方法更快，这是因为LinkedList< T>的方法执行线性搜索而List< T>.BinarySearch方法执行二分查找法。一般条件下，二分查找法利用元素在List< T>内是按顺序排列的。这使得在进行二分查找之前必须调用Sort方法（注意：当添加新元素时，Sort方法也会在BinarySearch方法之前被调用）。利用这些，二分查找将检查列表中的中间那个元素，并询问：你查找的对象是否大于列表中的当前对象？如果是这样，可知目标对象索引值将在当前对象之前。如果不是，则对象索引值在当前索引之后。二分查找算法保持询问，直到找到对象为止。恰恰相反，线性搜索从列表中的第一个元素开始查找指定元素，如果不是，则继续搜索下一个元素，直到在列表中找到相应的元素。

阅读参考

查看MSDN文档中的“LinkedList< T> Class”主题。

4.7 创建一个可以被初始化为空的值类型

问题

您有一个数字类型的变量，用于控制从数据库中获取的数值。数据库可能为这个值返回一个null值。您需要一个简洁的方法来存储这个数值，甚至它返回为null。

解决方案

使用可空类型。有两个创建可空类型的方法。第一种方法是使用？类型修饰符：

int? myDBInt = null;

第二种方法是使用Nullable< T>泛型类型：

Nullable< int> myDBInt = new Nullable< int>();

讨论

本质上，下面两个声明是等价的：

int? myDBInt = null;

Nullable< int> myDBInt = new Nullable< int>();

两个声明中，myDBInt都被认为是可空类型并初始化为null。一个可空类型实现了InullableValue接口，它只有两个属性成员：HasValue和Value。如果把可空类型设置为null，HasValue属性将返回false，否则将返回true。如果HasValue返回true，就可以访问Value属性以获得可空数据类型里当前存放的值。如果引发了InvalidOperationException异常，这是因为此时Value属性还未被定义。

另外，测试可空类型可以有两种方法。第一，使用HasValue属性如下：

    if (myDBInt.HasValue)

        Console.WriteLine("Has a value: " + myDBInt.Value);

    else

    Console.WriteLine("Does not have a value (NULL)");

第二种方法是跟null对比：

    if (myDBInt != null)

        Console.WriteLine("Has a value: " + myDBInt.Value);

    else

    Console.WriteLine("Does not have a value (NULL)");

两种方法都可以让人接受。

当需要把可空类型转换为非可空类型时，转换操作将正常进行，如果可空类型被设置为null就会引发一个InvalidOperationException异常。当把一个非可空类型转换为可空类型时，转换操作将正常运行，不会引发InvalidOperationException异常，非可空类型永远不会为null。

需要提防的是可空类型在进行比较运算的时候。例如执行下列代码时：

    if (myTempDBInt < 100)

        Console.WriteLine("myTempDBInt < 100");

    else

        Console.WriteLine("myTempDBInt >= 100");

“myTempDBInt < 100”这句代码明显有错。为了修正它，您不得不检查myTempDBInt是否为空。如果不是，才能执行if语句里的代码块：

if (myTempDBInt != null)
     {
         if (myTempDBInt <  100)
             Console.WriteLine("myTempDBInt <  100");
         else
             Console.WriteLine("myTempDBInt >= 100");
     }
     else
     {
         // 在这里处理空值
 }

另外一个有趣的事情是您可以象使用一般数字类型一样使用可空类型，如：

     int? DBInt = 10;

     int Value = 2;

 int? Result = DBInt + Value; // Result == 12

如果表达式中的可空类型是一个null值，则表达式的结果为null，但如果没有可空类型的值为null，运算符会把它当成一般类型。如上例中的DBInt为null，则Result的结果也为null。

阅读参考

查看MSDN文档中的“Nullable< T> Generic Class”和“Using Nullable Types”主题。