.NET Framework源碼研究系列之---ArrayList與LinkedList

在上一篇<.NET Framework源碼研究系列之---馬甲List>中我們一起研究了.NET中 List的源代碼,也得到一些兄弟的熱心反饋.其中一位仁兄說希望看到ArrayList與LinkedList源 代碼,所以今天就以此為話題,大家一起看一下.NET中是如何實現ArrayList和LinkedList 的.

我們先看ArrayList和LinkedList在.NET中的位置,ArrayList的命名空間是 System.Collections,LinkedList的命名空間是System.Collections.Generic,這麼看來二者同 屬於集合類,只不過LinkedList在一個分支種.然而,稍對.NET的源碼分析後,我們會發現二者有 著明顯的區別,甚至可以說有質的不同.有這些不同不是因為二者功能的不同,而是微軟對它們的 定位不同.在.NET源碼物理結構中,ArrayList所在目錄 是"redbits\ndp\clr\src\BCL\System\Collections",LinkedList所在目錄 是"redbits\ndp\fx\src\CompMod\System\Collections\Generic".由此可知,ArrayList屬於CLR 級別的,LinkedList僅僅是額外的擴展.所以說二者其實沒有比對的意義.

因為二者沒有比較的意義,我們就分成兩部分看下二者是如何實現的.先看ArrayList.

public　class　ArrayList　:　IList,　ICloneable
　　 {
　　　　 private　Object[]　_items;
　　　　 private　int　_size;
　　　　 private　int　_version;
　　　　 [NonSerialized]
　　　　 private　Object　_syncRoot;
　　　　 private　const　int　_defaultCapacity　=　4;
　　　　 private　static　readonly　Object[]　emptyArray　=　new　Object [0];

以上是ArrayList中包含的字段.看過<.NET Framework源碼研究系列之---馬甲List> 是的兄弟是不是覺得很眼熟呢?

是的,其實ArrayList與List一樣.二者同屬於CLR基礎類,實現過程幾乎一模一樣.但是二者還 是有細節的不同.

首先,ArrayList是無類型約束的,也就是說ArrayList中可以包含任何類型;而List是強類型 的.雖然二者本質上都是調用 Array的靜態方法,如Copy,但在某些方法中ArrayList需要進行裝 箱拆箱的操作,由此會帶來部分性能損失,如下代碼:

public　virtual　int　IndexOf(Object　value){
　　　　　　 return　Array.IndexOf((Array)_items,　value,　0,　_size);
　　　　 }

其次,ArrayList繼承了ICloneable接口,而List沒有.如下.

public　virtual　Object　Clone(){
　　　　　　 ArrayList　la　=　new　ArrayList(_size);
　　　　　　 la._size　=　_size;
　　　　　　 la._version　=　_version;
　　　　　　 Array.Copy(_items,　0,　la._items,　0,　_size);
　　　　　　 return　la;
　　　　 }

由上面代碼我們可以看出ArrayList實現的時淺拷貝.這裡有個疑惑就是微軟對ArrayList實 現克隆接口的初衷,為是淺拷貝而不是深拷貝.

比較ArrayList和List源代碼後,我大致總結出二者主要有以上的不同.接下來我們看 LinkedList.

仍舊先看定義:

public　class　LinkedList<T>　:　ICollection<T>,　 System.Collections.ICollection,　ISerializable,　IDeserializationCallback{
　　　　 internal　LinkedListNode<T>　head;
　　　　 internal　int　count;
　　　　 internal　int　version;
　　　　 private　Object　_syncRoot;
　　　　 //反序列化時用到的一個臨時變量
　　　　 private　SerializationInfo　siInfo;
　　　　 /*序列化名字*/
　　　　 const　String　VersionName　=　"Version";
　　　　 const　String　CountName　=　"Count";
　　　　 const　String　ValuesName　=　"Data";
　　　　 public　LinkedList(){}
　　　　 public　LinkedList(IEnumerable<T>　collection){
　　　　　　 if　(collection　==　null){
　　　　　　　　 throw　new　ArgumentNullException("collection");
　　　　　　 }
　　　　　　 foreach　(T　item　in　collection){
　　　　　　　　 AddLast(item);
　　　　　　 }
　　　　 }
　　　　 protected　LinkedList(SerializationInfo　info,　StreamingContext　 context){　　　　　　siInfo　=　info;　　　　}

LinkedList實現了ICollection接口,說明它是個集合類.實現ISerializable接口說明它默認 支持序列化,另外還隱藏實現了IEnumerable接口.最後還支持一個比較少用的接口 IDeserializationCallback,該接口使 LinkedList在完成反序列化前可以執行一定的動作.

LinkedList對ICollection,ISerializable我們並不奇怪,在實現IEnumerable時有點稍許的 不同. 與ArralyList,List相同的時,在現實IEnumerable時LinkedList一樣是使用了一個內部類 Enumerator,與 ArralyList,List不同的是Enumerator在實現IEnumerator,ISerializable時也 實現了 IDeserializationCallback接口.另外就是對IEnumerator.MoveNext方法的實現不同.這 是因為 LinkedList是雙向鏈表,集合中每個元素的分配空間並不連續,需要通過前後的引用來獲 取.我們沒向LinkedList添加一個對象的時候,LinkedList實際上會將我們添加的對象包裝為 LinkedListNode對象,而該對象就有Prev和Next兩個屬性.這點相信大家都很容易理解.

剛才我們說到LinkedList還實現了IDeserializationCallback接口,對於這點,需要有以下2 點說明.第一,就如上面介紹IEnumerable接口一樣,它這麼做是因為在反序列化的時候要維護集 合中元素的前後引用;第二,要達到此類目的也可以使用另一個方法.我們知道,其實.NET中每個 可序列化的類默認都支持以下四個方法:

OnDeserialized//反序列化完成時執行的方法
　　 OnDeserializing//反序列化時執行的方法
　　 OnSerialized//序列化完成時執行的方法
　　 OnSerializing//序列化時執行的方法

通過這4個方法,我們就可以做很多事情,比如序列化本來不可序列化的對象.LinkedList的字 段private SerializationInfo siInfo;其實就是OnDeserialized使用的.大家來看下 LinkedList是如何實現該方法的:

public　virtual　void　OnDeserialization(Object　sender){
　　　　　　 if　(siInfo　==　null){
　　　　　　　　 return;　//Somebody　had　a　dependency　on　this　Dictionary　 and　fixed　us　up　before　the　ObjectManager　got　to　it.　
　　　　　　 }
　　　　　　 int　realVersion　=　siInfo.GetInt32(VersionName);
　　　　　　 int　count　=　siInfo.GetInt32(CountName);
　　　　　　 if　(count　!=　0){
　　　　　　　　 T[]　array　=　(T[])siInfo.GetValue(ValuesName,　typeof(T []));
　　　　　　　　 if　(array　==　null){
　　　　　　　　　　 throw　new　SerializationException(SR.GetString (SR.Serialization_MissingValues));
　　　　　　　　 }
　　　　　　　　 for　(int　i　=　0;　i　<　array.Length;　i++){
　　　　　　　　　　 AddLast(array[i]);
　　　　　　　　 }
　　　　　　 }
　　　　　　 else{
　　　　　　　　 head　=　null;
　　　　　　 }
　　　　　　 version　=　realVersion;
　　　　　　 siInfo　=　null;
　　　　 }

其實用過LinkeList的人都知道LinkedList是一個雙向鏈表,也是個集合.如果讓大家各自實 現一個相同的鏈表,實現過程其實都差不多.微軟版LinkedList的實現也與大家一樣,區別的地方 也就是上面提到的地方.作為集合,LinkedList對ICollection接口的實現與ArrayList一樣;作為 鏈表,在實現ICollection接口,和其他一些獨有的方法時要著重維護鏈表中每個元素的Prev和 Next兩個屬性.實現代碼這裡就不一一列出了.

小結

經過上一篇<.NET Framework源碼研究系列之---馬甲List>和本篇,我覺得其實微軟的 東西並不神秘,做同樣一件事,不管思維過程,還是實現手法,跟我們都差不多.區別更多的在於細 節,如對IEnumerable的實現方法,對　IDeserializationCallback的選擇.在我們實際工作的,可 以參考微軟的做法,也可以按我們自己的方法來,其實沒有質的不同.