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。
