.NETFramework源码研究系列之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的选择.在我们实际工作的,可以参考微软的做法,也可以按我们自己的方法来,其实没有质的不同.