.NET,你忘记了么？（三）——关于Array和List的使用

　　Array和List都属于顺序表。

　　Array是一段连续的存储结构，如int[] i=new int[3]，i其实记录的是数组的首地址，而i[1]其实相当于在i的地址的基础上加上1个整数的地址偏移，然后再取这块地址中的值。也就是相当于*(&i[0]+4);

　　而List则是不连续的存储结构，List的每个节点都有着一个Next属性，这个属性则记录着他的下一个节点的地址。也就是说当我们想找第100个节点的时候，他还是需要从第一个节点，然后做99次Next操作，才能找到list[99]节点。这是个蛮痛苦的过程。

　　很多人会说，那无论是List还是Array，不都是一个索引么！让我们来请出IL:

　　先来看Array查找某个元素的IL:

　　IL_0020:　 ldloc.0

　　IL_0021:　 ldc.i4.3

　　IL_0022:　 ldelem.i4

　　IL_0023:　 stloc.2

　　然后让我们来看下List查找某个元素的IL:

　　IL_0022:　 ldloc.0

　　IL_0023:　 ldc.i4.3

　　IL_0024:　 callvirt　　 instance !0 class [mscorlib]System.Collections.Generic.List`1<int32>::get_Item(int32)

　　IL_0029:　 stloc.2

　　我们可以发现，虽然他们的写法是一样的，但是在IL中却有着很大的差别。

　　通过这两段IL，我只是希望证明List和Array对索引元素的方式是不同的。当然，我们无从知道Microsoft对List方法get_Item的实现。但是我们不难想象：

　　因为List是一个链表，所以我需要从第一个元素开始逐个Next到所需索引的元素。这是一个耗时的过程。

　　因此，在使用洗牌算法时，使用List是个很差劲的做法。再进一步说，当我们需要大量的索引步骤时，使用List是个很差劲的做法。

　　那List和Array各自应该用在什么情况下呢？我来做个简单的总结：

评论总数：0 条 [ 查看全部 ] 网友评论